A new class of searchable and provably highly compressible string transformations

Marinella Sciortino, Raffaele Giancarlo, Giovanna Rosone, Giovanni Manzini

Risultato della ricerca: Conference contribution

1 Citazione (Scopus)

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 originaleEnglish
Titolo della pubblicazione ospiteLeibniz International Proceedings in Informatics, LIPIcs
Pagine1-12
Numero di pagine12
Stato di pubblicazionePublished - 2019

Serie di pubblicazioni

NomeLEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS

Fingerprint

Data structures
Mathematical transformations

All Science Journal Classification (ASJC) codes

  • Software

Cita questo

Sciortino, M., Giancarlo, R., Rosone, G., & Manzini, G. (2019). A new class of searchable and provably highly compressible string transformations. In Leibniz International Proceedings in Informatics, LIPIcs (pagg. 1-12). (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS).

A new class of searchable and provably highly compressible string transformations. / Sciortino, Marinella; Giancarlo, Raffaele; Rosone, Giovanna; Manzini, Giovanni.

Leibniz International Proceedings in Informatics, LIPIcs. 2019. pag. 1-12 (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS).

Risultato della ricerca: Conference contribution

Sciortino, M, Giancarlo, R, Rosone, G & Manzini, G 2019, A new class of searchable and provably highly compressible string transformations. in Leibniz International Proceedings in Informatics, LIPIcs. LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, pagg. 1-12.
Sciortino M, Giancarlo R, Rosone G, Manzini G. A new class of searchable and provably highly compressible string transformations. In Leibniz International Proceedings in Informatics, LIPIcs. 2019. pag. 1-12. (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS).
Sciortino, Marinella ; Giancarlo, Raffaele ; Rosone, Giovanna ; Manzini, Giovanni. / A new class of searchable and provably highly compressible string transformations. Leibniz International Proceedings in Informatics, LIPIcs. 2019. pagg. 1-12 (LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS).
@inproceedings{de766c4410aa4802a993176d222edf0e,
title = "A new class of searchable and provably highly compressible string transformations",
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",
author = "Marinella Sciortino and Raffaele Giancarlo and Giovanna Rosone and Giovanni Manzini",
year = "2019",
language = "English",
isbn = "978-395977103-0",
series = "LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS",
pages = "1--12",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",

}

TY - GEN

T1 - A new class of searchable and provably highly compressible string transformations

AU - Sciortino, Marinella

AU - Giancarlo, Raffaele

AU - Rosone, Giovanna

AU - Manzini, Giovanni

PY - 2019

Y1 - 2019

N2 - 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

AB - 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

UR - http://hdl.handle.net/10447/361353

UR - http://drops.dagstuhl.de/opus/institut_lipics.php?fakultaet=04

M3 - Conference contribution

SN - 978-395977103-0

T3 - LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS

SP - 1

EP - 12

BT - Leibniz International Proceedings in Informatics, LIPIcs

ER -