TY - GEN
T1 - Block Sorting-Based Transformations on Words
T2 - 22nd International Conference on Developments in Language Theory, DLT 2018
AU - Giancarlo, Raffaele
AU - Manzini, Giovanni
AU - Restivo, Antonio
AU - Rosone, Giovanna
AU - Sciortino, Marinella
N1 - Publisher Copyright:
© 2018, Springer Nature Switzerland AG.
PY - 2018
Y1 - 2018
N2 - The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression and later results have contributed to make it a fundamental tool for the design of self-indexing compressed data structures. The Alternating Burrows-Wheeler Transform (ABWT) is a more recent transformation, studied in the context of Combinatorics on Words, that works in a similar way, using an alternating lexicographical order instead of the usual one. In this paper we study a more general class of block sorting-based transformations. The transformations in this new class prove to be interesting combinatorial tools that offer new research perspectives. In particular, we show that all the transformations in this class can be used as booster for memoryless compressors and we provide an upper bound on the number of equal-letter runs in their output. Moreover, we introduce the notion of rank-invertibility, a property related to the implementation of an efficient inversion procedure. We show that the BWT and the Alternating BWT are the only rank-invertible transformations in the class we have defined.
AB - The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression and later results have contributed to make it a fundamental tool for the design of self-indexing compressed data structures. The Alternating Burrows-Wheeler Transform (ABWT) is a more recent transformation, studied in the context of Combinatorics on Words, that works in a similar way, using an alternating lexicographical order instead of the usual one. In this paper we study a more general class of block sorting-based transformations. The transformations in this new class prove to be interesting combinatorial tools that offer new research perspectives. In particular, we show that all the transformations in this class can be used as booster for memoryless compressors and we provide an upper bound on the number of equal-letter runs in their output. Moreover, we introduce the notion of rank-invertibility, a property related to the implementation of an efficient inversion procedure. We show that the BWT and the Alternating BWT are the only rank-invertible transformations in the class we have defined.
UR - https://www.scopus.com/pages/publications/85053889837
U2 - 10.1007/978-3-319-98654-8_1
DO - 10.1007/978-3-319-98654-8_1
M3 - Conference contribution
AN - SCOPUS:85053889837
SN - 9783319986531
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 17
BT - Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings
A2 - Hoshi, Mizuho
A2 - Seki, Shinnosuke
PB - Springer Verlag
Y2 - 10 September 2018 through 14 September 2018
ER -