Pubblicazioni

Bit Catastrophes for the Burrows-Wheeler Transform  (2025)

Autori:
Giuliani, Sara; Inenaga, Shunsuke; Lipták, Zsuzsanna; Romana, Giuseppe; Sciortino, Marinella; Urbina, Cristian
Titolo:
Bit Catastrophes for the Burrows-Wheeler Transform
Anno:
2025
Tipologia prodotto:
Articolo in Rivista
Tipologia ANVUR:
Articolo su rivista
Lingua:
Inglese
Formato:
A Stampa
Referee:
Nome rivista:
Theory of Computing Systems
ISSN Rivista:
1432-4350
N° Volume:
69
Numero o Fascicolo:
2
Editore:
Springer Verlag
Intervallo pagine:
1-37
Parole chiave:
Burrows-Wheeler transform; Equal-letter run; Repetitiveness measure; Sensitivity
Breve descrizione dei contenuti:
A bit catastrophe, loosely defined, is when a change in just one character of a string causes a significant change in the size of the compressed string. We study this phenomenon for the Burrows-Wheeler Transform (BWT), a string transform at the heart of several of the most popular compressors and aligners today. The parameter determining the size of the compressed data is the number of equal-letter runs of the BWT, commonly denoted r. We exhibit infinite families of strings in which insertion, deletion, resp. substitution of one character increases r from constant to Theta(log n), where n is the length of the string. These strings can be interpreted both as examples for an increase by a multiplicative or an additive Theta(log n)-factor. As regards the multiplicative factor, they attain the upper bound given by Akagi, Funakoshi, and Inenaga [Inf & Comput. 2023] of O(log n log r), since here r = O(1). We then give examples of strings in which insertion, deletion, resp. substitution of a character increases r by a Theta(\sqrt(n)) additive factor. These strings significantly improve the best known lower bound for an additive factor of Omega(log n) [Giuliani et al., SOFSEM 2021].
Pagina Web:
https://link.springer.com/article/10.1007/s00224-024-10212-9
Id prodotto:
145578
Handle IRIS:
11562/1161651
ultima modifica:
10 maggio 2025
Citazione bibliografica:
Giuliani, Sara; Inenaga, Shunsuke; Lipták, Zsuzsanna; Romana, Giuseppe; Sciortino, Marinella; Urbina, Cristian, Bit Catastrophes for the Burrows-Wheeler Transform «Theory of Computing Systems» , vol. 69 , n. 22025pp. 1-37

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo IRIS

<<indietro

Attività

Strutture

Condividi