The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism φ that admits a fixed point (denoted by φ∞(a) ) starting from a given character a belonging to the finite alphabet A , i.e. φ∞(a)=limi→∞φi(a) . Such morphisms are called prolongable on a . Here we focus on the compressibility via the Burrows-Wheeler Transform ( BWT ) of infinite families of finite sequences generated by morphisms. In particular, denoted by r(w) the number of equal-letter runs of a word w , we provide new upper bounds on r(bwt(φi(a))) , i.e. the number of equal-letter runs produced when BWT is applied on φi(a) . Such bounds depend on the factor complexity fx(n) of the infinite word x=φ∞(a) , that counts, for each n≥0 , the number of distinct factors of x having length n
Burrows-Wheeler Transform on Purely Morphic Words / Frosini, A; Mancini, I; Rinaldi, S; Romana, G; Sciortino, M. - ELETTRONICO. - 2022-March:(2022), pp. 452-452. (Intervento presentato al convegno 2022 Data Compression Conference) [10.1109/DCC52660.2022.00063].
Burrows-Wheeler Transform on Purely Morphic Words
Frosini, A;Mancini, I
;Rinaldi, S;Romana, G
;Sciortino, M
2022
Abstract
The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism φ that admits a fixed point (denoted by φ∞(a) ) starting from a given character a belonging to the finite alphabet A , i.e. φ∞(a)=limi→∞φi(a) . Such morphisms are called prolongable on a . Here we focus on the compressibility via the Burrows-Wheeler Transform ( BWT ) of infinite families of finite sequences generated by morphisms. In particular, denoted by r(w) the number of equal-letter runs of a word w , we provide new upper bounds on r(bwt(φi(a))) , i.e. the number of equal-letter runs produced when BWT is applied on φi(a) . Such bounds depend on the factor complexity fx(n) of the infinite word x=φ∞(a) , that counts, for each n≥0 , the number of distinct factors of x having length nFile | Dimensione | Formato | |
---|---|---|---|
Burrows-Wheeler_Transform_on_Purely_Morphic_Words.pdf
accesso aperto
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Open Access
Dimensione
82 kB
Formato
Adobe PDF
|
82 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.