TheBijectiveBurrows-WheelerTransform(BBWT)isavari- ant 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 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 com- pression power. We exhibit an infinite family of strings on which rB of the string and of its reverse differ by a factor of Θ(log(n)), where n is the length of the string. We also present experimental results and statistics on rB(s) and rB(srev), as well as on the number of Lyndon factors in the Lyndon factorization of s.
On the number of equal-letter runs of the Bijective Burrows-Wheeler Transform
Zsuzsanna Liptak;
2023-01-01
Abstract
TheBijectiveBurrows-WheelerTransform(BBWT)isavari- ant 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 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 com- pression power. We exhibit an infinite family of strings on which rB of the string and of its reverse differ by a factor of Θ(log(n)), where n is the length of the string. We also present experimental results and statistics on rB(s) and rB(srev), as well as on the number of Lyndon factors in the Lyndon factorization of s.File | Dimensione | Formato | |
---|---|---|---|
ICTCS2023_4564.pdf
accesso aperto
Licenza:
Creative commons
Dimensione
2.35 MB
Formato
Adobe PDF
|
2.35 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.