On the Number of Equal-Letter Runs of the Bijective Burrows-Wheeler Transform
- Autori: Biagi, E.; Cenzato, D.; Liptak, Z.; Romana, G.
- Anno di pubblicazione: 2023
- Tipologia: Contributo in atti di convegno pubblicato in volume
- OA Link: http://hdl.handle.net/10447/704399
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. 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 and srev