Abstract
The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007] and on the Lyndon factorization of the input string. In the original paper, the compression achieved with the BBWT was shown to be competitive with that of the BWT, and it has been gaining interest in recent years. In this work, we present the first study of the number of runs rB of the BBWT, which is a measure of its compression power. We exhibit an infinite family of strings on which rB of the string and of its reverse differ by a multiplicative factor of T(log n), where n is the length of the string.
| Original language | English |
|---|---|
| Journal | CEUR Workshop Proceedings |
| Volume | 3587 |
| Pages (from-to) | 129-142 |
| Number of pages | 14 |
| ISSN | 1613-0073 |
| Publication status | Published - 2023 |
| MoE publication type | A4 Article in conference proceedings |
| Event | Italian Conference on Theoretical Computer Science - Palermo, Italy Duration: 13 Sept 2023 → 15 Sept 2023 Conference number: 24 |
Fields of Science
- Bijective Burrows-Wheeler Transform
- BWT
- data compression
- eBWT
- Lyndon factorization
- ombinatorics on words
- 113 Computer and information sciences