A new class of searchable and provably highly compressible string transformations

DOI10.4230/LIPIcs.CPM.2019.12OpenAlexW2915030822MaRDI QIDQ5088900

Giovanna Rosone, Giovanni Manzini, Marinella Sciortino, Raffaele Giancarlo

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1902.01280

zbMATH Keywords

combinatorics on wordsBurrows-Wheeler transformationdata indexing and compression

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (3)

A new class of string transformations for compressed text indexing ⋮ Unnamed Item ⋮ The alternating BWT: an algorithmic perspective

Cites Work

• Unnamed Item
• On compressing and indexing repetitive sequences
• A bijection between words and multisets of necklaces
• Counting permutations with given cycle structure and descent set
• Block sorting-based transformations on words: beyond the magic BWT
• Wheeler graphs: a framework for BWT-based data structures
• Measuring the clustering effect of BWT via RLE
• Burrows-Wheeler transform and run-length enconding
• A note on the Burrows-Wheeler transformation
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• Compressed representations of sequences and full-text indexes
• An analysis of the Burrows—Wheeler transform
• Linear work suffix array construction
• Boosting textual compression in optimal linear time
• Indexing compressed text
• Optimal Lower and Upper Bounds for Representing Sequences
• At the roots of dictionary compression: string attractors

This page was built for publication: A new class of searchable and provably highly compressible string transformations