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.

Raffaele, G., Manzini, G., Restivo, A., Rosone, G., Sciortino, M. (2018). Block Sorting-Based Transformations on Words: Beyond the Magic BWT. In Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings (pp. 1-17). Springer Verlag [10.1007/978-3-319-98654-8_1].

Block Sorting-Based Transformations on Words: Beyond the Magic BWT

Raffaele, Giancarlo;Restivo, Antonio;Rosone, Giovanna;Sciortino, Marinella
2018-01-01

Abstract

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.
2018
978-3-319-98653-1
Raffaele, G., Manzini, G., Restivo, A., Rosone, G., Sciortino, M. (2018). Block Sorting-Based Transformations on Words: Beyond the Magic BWT. In Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings (pp. 1-17). Springer Verlag [10.1007/978-3-319-98654-8_1].
File in questo prodotto:
File Dimensione Formato  
giancarlo2018.pdf

Solo gestori archvio

Dimensione 390.31 kB
Formato Adobe PDF
390.31 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
GMRRS_DLT2018.pdf

accesso aperto

Tipologia: Post-print
Dimensione 357.59 kB
Formato Adobe PDF
357.59 kB 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/10447/301703
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact