In this paper we study the number rbwt of equal-letter runs produced by the Burrows-Wheeler transform (BWT) when it is applied to purely morphic finite words, which are words generated by iterating prolongable morphisms. Such a parameter rbwt is very significant since it provides a measure of the performances of the BWT, in terms of both compressibility and indexing. In particular, we prove that, when BWT is applied to whichever purely morphic finite word on a binary alphabet, rbwt is O(logn), where n is the length of the word. Moreover, we prove that rbwt is Θ(logn) for the binary words generated by a large class of prolongable binary morphisms. These bounds are proved by providing some new structural properties of the bispecial circular factors of such words.
Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words / Frosini A.; Mancini I.; Rinaldi S.; Romana G.; Sciortino M.. - ELETTRONICO. - 13257 LNCS:(2022), pp. 139-151. (Intervento presentato al convegno Developments in Language Theory) [10.1007/978-3-031-05578-2_11].
Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words
Frosini A.;Mancini I.
;Rinaldi S.;Romana G.
;Sciortino M.
2022
Abstract
In this paper we study the number rbwt of equal-letter runs produced by the Burrows-Wheeler transform (BWT) when it is applied to purely morphic finite words, which are words generated by iterating prolongable morphisms. Such a parameter rbwt is very significant since it provides a measure of the performances of the BWT, in terms of both compressibility and indexing. In particular, we prove that, when BWT is applied to whichever purely morphic finite word on a binary alphabet, rbwt is O(logn), where n is the length of the word. Moreover, we prove that rbwt is Θ(logn) for the binary words generated by a large class of prolongable binary morphisms. These bounds are proved by providing some new structural properties of the bispecial circular factors of such words.File | Dimensione | Formato | |
---|---|---|---|
BWT_on_morphic_words.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
322.06 kB
Formato
Adobe PDF
|
322.06 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.