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)=lim_{i→∞}φ^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 f_x(n) of the infinite word x=φ^∞(a) , that counts, for each n≥0 , the number of distinct factors of x having length n .
Frosini, A., Mancini, I., Rinaldi, S., Romana, G., Sciortino, M. (2022). Burrows-Wheeler Transform on Purely Morphic Words. In Data Compression Conference 2022 (pp. 452-452). 345 E 47TH ST, NEW YORK, NY 10017 USA : IEEE [10.1109/DCC52660.2022.00063].
Burrows-Wheeler Transform on Purely Morphic Words
Romana, G;Sciortino, M
2022-01-01
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)=lim_{i→∞}φ^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 f_x(n) of the infinite word x=φ^∞(a) , that counts, for each n≥0 , the number of distinct factors of x having length n .File | Dimensione | Formato | |
---|---|---|---|
Burrows-Wheeler_Transform_on_Purely_Morphic_Words.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
82 kB
Formato
Adobe PDF
|
82 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.