Introduced about thirty years ago in the field of data compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of efficient self-indexing compressed data structures. Finding other string transformations with the same remarkable properties of BWT has been a challenge for many researchers for a long time. In this paper, we introduce a whole class of new string transformations, called local orderings-based transformations, which have all the “myriad virtues” of BWT. As a further result, we show that such new string transformations can be used for the construction of the recently introduced r-index, which makes them suitable also for highly repetitive collections. In this context, we consider the problem of finding, for a given string, the BWT variant that minimizes the number of runs in the transformed string.

Giancarlo R., Manzini G., Restivo A., Rosone G., Sciortino M. (2023). A new class of string transformations for compressed text indexing. INFORMATION AND COMPUTATION, 294(October 2023) [10.1016/j.ic.2023.105068].

A new class of string transformations for compressed text indexing

Giancarlo R.;Restivo A.;Sciortino M.
2023-01-01

Abstract

Introduced about thirty years ago in the field of data compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of efficient self-indexing compressed data structures. Finding other string transformations with the same remarkable properties of BWT has been a challenge for many researchers for a long time. In this paper, we introduce a whole class of new string transformations, called local orderings-based transformations, which have all the “myriad virtues” of BWT. As a further result, we show that such new string transformations can be used for the construction of the recently introduced r-index, which makes them suitable also for highly repetitive collections. In this context, we consider the problem of finding, for a given string, the BWT variant that minimizes the number of runs in the transformed string.
2023
Giancarlo R., Manzini G., Restivo A., Rosone G., Sciortino M. (2023). A new class of string transformations for compressed text indexing. INFORMATION AND COMPUTATION, 294(October 2023) [10.1016/j.ic.2023.105068].
File in questo prodotto:
File Dimensione Formato  
A new class of string transformations for compressed text indexing.pdf

accesso aperto

Tipologia: Versione Editoriale
Dimensione 635.84 kB
Formato Adobe PDF
635.84 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/620074
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact