Bit catastrophes for the Burrows-Wheeler Transform
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918048798081024 |
|---|---|
| author | Giuliani, Sara Inenaga, Shunsuke Lipták, Zsuzsanna Romana, Giuseppe Sciortino, Marinella Urbina, Cristian |
| author_facet | Giuliani, Sara Inenaga, Shunsuke Lipták, Zsuzsanna Romana, Giuseppe Sciortino, Marinella Urbina, Cristian |
| contents | 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 $Θ(\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 $Θ(\log n)$-factor. As regards 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 $Θ(\sqrt{n})$ additive factor. These strings significantly improve the best known lower bound for an additive factor of $Ω(\log n)$ [Giuliani et al., SOFSEM 2021]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10426 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bit catastrophes for the Burrows-Wheeler Transform Giuliani, Sara Inenaga, Shunsuke Lipták, Zsuzsanna Romana, Giuseppe Sciortino, Marinella Urbina, Cristian Data Structures and Algorithms Discrete Mathematics 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 $Θ(\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 $Θ(\log n)$-factor. As regards 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 $Θ(\sqrt{n})$ additive factor. These strings significantly improve the best known lower bound for an additive factor of $Ω(\log n)$ [Giuliani et al., SOFSEM 2021]. |
| title | Bit catastrophes for the Burrows-Wheeler Transform |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2404.10426 |