A new class of searchable and provably highly compressible string transformations

Raffaele Giancarlo, Giovanni Manzini, Giovanna Rosone, Marinella Sciortino

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

Abstract

The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have successfully extended this transformation outside the domains of strings. However, efforts to find non-trivial alternatives of the original, now 25 years old, Burrows-Wheeler string transformation have met limited success. In this paper we bring new lymph to this area by introducing a whole new family of transformations that have all the “myriad virtues” of the BWT: they can be computed and inverted in linear time, they produce provably highly compressible strings, and they support linear time pattern search directly on the transformed string. This new family is a special case of a more general class of transformations based on context adaptive alphabet orderings, a concept introduced here. This more general class includes also the Alternating BWT, another invertible string transforms recently introduced in connection with a generalization of Lyndon words.

Lingua originaleInglese
Titolo della pubblicazione ospite30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
EditorNadia Pisanti, Solon P. Pissis
EditoreSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elettronico)9783959771030
DOI
Stato di pubblicazionePubblicato - 1 giu 2019
Pubblicato esternamente
Evento30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019 - Pisa, Italy
Durata: 18 giu 201920 giu 2019

Serie di pubblicazioni

NomeLeibniz International Proceedings in Informatics, LIPIcs
Volume128
ISSN (stampa)1868-8969

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
Paese/TerritorioItaly
CittàPisa
Periodo18/06/1920/06/19

Fingerprint

Entra nei temi di ricerca di 'A new class of searchable and provably highly compressible string transformations'. Insieme formano una fingerprint unica.

Cita questo