The myriad virtues of wavelet trees

DOI10.1016/j.ic.2008.12.010zbMath1167.68020OpenAlexW2096575760MaRDI QIDQ2389347

Giovanni Manzini, Paolo Ferragina, Raffaele Giancarlo

Publication date: 15 July 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.12.010

zbMATH Keywords

data compression algorithmscompressed full-text indexes

Mathematics Subject Classification ID

Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information storage and retrieval of data (68P20)

Related Items

Wheeler graphs: a framework for BWT-based data structures, Practical Wavelet Tree Construction, On optimally partitioning a text to improve its compression, Wavelet trees for all, On Wavelet Tree Construction, A quick tour on suffix arrays and compressed suffix arrays, Forty Years of Text Indexing, Move-to-front, distance coding, and inversion frequencies revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Move-to-front, distance coding, and inversion frequencies revisited
• When indexing equals compression
• Compressed representations of sequences and full-text indexes
• Robust transmission of unbounded strings using Fibonacci representations
• An analysis of the Burrows—Wheeler transform
• Boosting textual compression in optimal linear time
• The Myriad Virtues of Wavelet Trees
• Universal codeword sets and representations of the integers
• Lexical Permutation Sorting Algorithm
• Inversion Coding
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression