6533b85ffe1ef96bd12c11a1

RESEARCH PRODUCT

A New Class of Searchable and Provably Highly Compressible String Transformations

Giancarlo R.Manzini G.Rosone G.Sciortino M.

subject

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

description

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.

yearjournalcountryeditionlanguage
2019-02-04
http://arxiv.org/abs/1902.01280