The {em Burrows-Wheeler transform} (BWT) is a popular method used for text compression. It was proved that BWT has optimal performance on standard words, i.e. the building blocks of Sturmian words. In this paper, we study the application of BWT on more general morphic words: the Thue-Morse word and to generalizations of the Fibonacci word to alphabets with more than two letters; then, we study morphisms obtained as composition of the Thue-Morse morphism with a Sturmian one. In all these cases, the BWT efficiently clusters the iterates of the morphisms generating prefixes of these infinite words, for which we determine the compression clustering ratio.
Burrows-wheeler transform of words defined by morphisms / Brlek S.; Frosini A.; Mancini I.; Pergola E.; Rinaldi S.. - STAMPA. - 11638:(2019), pp. 393-404. (Intervento presentato al convegno INTERNATIONAL WORKSHOP ON COMBINATORIAL ALGORITHM tenutosi a ita nel 2019) [10.1007/978-3-030-25005-8_32].
Burrows-wheeler transform of words defined by morphisms
BRLEK, SRECKO;Frosini A.;Pergola E.;Rinaldi S.
2019
Abstract
The {em Burrows-Wheeler transform} (BWT) is a popular method used for text compression. It was proved that BWT has optimal performance on standard words, i.e. the building blocks of Sturmian words. In this paper, we study the application of BWT on more general morphic words: the Thue-Morse word and to generalizations of the Fibonacci word to alphabets with more than two letters; then, we study morphisms obtained as composition of the Thue-Morse morphism with a Sturmian one. In all these cases, the BWT efficiently clusters the iterates of the morphisms generating prefixes of these infinite words, for which we determine the compression clustering ratio.File | Dimensione | Formato | |
---|---|---|---|
BWT.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
231.87 kB
Formato
Adobe PDF
|
231.87 kB | Adobe PDF | Richiedi una copia |
BWT-morphism_ Last.pdf
accesso aperto
Tipologia:
Altro
Licenza:
Tutti i diritti riservati
Dimensione
285.12 kB
Formato
Adobe PDF
|
285.12 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.