Salta al contenuto principale
Passa alla visualizzazione normale.


A new class of string transformations for compressed text indexing

  • Autori: Giancarlo R.; Manzini G.; Restivo A.; Rosone G.; Sciortino M.
  • Anno di pubblicazione: 2023
  • Tipologia: Articolo in rivista
  • OA Link:


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.