Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910989432127488 |
|---|---|
| author | Ingels, Florian Denis, Anaïs Cazaux, Bastien |
| author_facet | Ingels, Florian Denis, Anaïs Cazaux, Bastien |
| contents | The Burrows-Wheeler Transform (BWT) is a fundamental component in many data structures for text indexing and compression, widely used in areas such as bioinformatics and information retrieval. The extended BWT (eBWT) generalizes the classical BWT to multisets of strings, providing a flexible framework that captures many BWT-like constructions. Several known variants of the BWT can be viewed as instances of the eBWT applied to specific decompositions of a word. A central property of the BWT, essential for its compressibility, is the number of maximal ranges of equal letters, named runs. In this article, we explore how different decompositions of a word impact the number of runs in the resulting eBWT. First, we show that the number of decompositions of a word is exponential, even under minimal constraints on the size of the subsets in the decomposition. Second, we present an infinite family of words for which the ratio of the number of runs between the worst and best decompositions is unbounded, under the same minimal constraints. These results illustrate the potential cost of decomposition choices in eBWT-based compression and underline the challenges in optimizing run-length encoding in generalized BWT frameworks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform Ingels, Florian Denis, Anaïs Cazaux, Bastien Data Structures and Algorithms Discrete Mathematics Formal Languages and Automata Theory The Burrows-Wheeler Transform (BWT) is a fundamental component in many data structures for text indexing and compression, widely used in areas such as bioinformatics and information retrieval. The extended BWT (eBWT) generalizes the classical BWT to multisets of strings, providing a flexible framework that captures many BWT-like constructions. Several known variants of the BWT can be viewed as instances of the eBWT applied to specific decompositions of a word. A central property of the BWT, essential for its compressibility, is the number of maximal ranges of equal letters, named runs. In this article, we explore how different decompositions of a word impact the number of runs in the resulting eBWT. First, we show that the number of decompositions of a word is exponential, even under minimal constraints on the size of the subsets in the decomposition. Second, we present an infinite family of words for which the ratio of the number of runs between the worst and best decompositions is unbounded, under the same minimal constraints. These results illustrate the potential cost of decomposition choices in eBWT-based compression and underline the challenges in optimizing run-length encoding in generalized BWT frameworks. |
| title | Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform |
| topic | Data Structures and Algorithms Discrete Mathematics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2506.04926 |