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.
2019
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
INTERNATIONAL WORKSHOP ON COMBINATORIAL ALGORITHM
ita
2019
Brlek S.; Frosini A.; Mancini I.; Pergola E.; Rinaldi S.
File in questo prodotto:
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.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1171602
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact