0000000000723557

AUTHOR

Rosone G.

showing 2 related works from this author

An extension of the Burrows-Wheeler Transform to k words

2005

researchProduct

A New Class of Searchable and Provably Highly Compressible String Transformations

2019

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 direc…

Settore ING-INF/05 - Sistemi Di Elaborazione Delle InformazioniFOS: Computer and information sciences050101 languages & linguisticsBurrows-wheeler transformation; Combinatorics on words; Data indexing and compression000 Computer science knowledge general worksSettore INF/01 - InformaticaCombinatorics on words05 social sciences02 engineering and technologyData_CODINGANDINFORMATIONTHEORYComputer ScienceBurrows-wheeler transformationComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processing0501 psychology and cognitive sciencesData Structures and Algorithms (cs.DS)Data indexing and compressionCombinatorics on word
researchProduct