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.
2023
Bijective Burrows-Wheeler Transform · BWT · eBWT, combinatorics on words, Lyndon factorization, compression
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1099946
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact