The myriad virtues of wavelet trees

DOI10.1016/J.IC.2008.12.010MaRDI QIDQ2389347zbMATH OpenOpenAlexFDO

Authors Paolo Ferragina, R. Giancarlo, Giovanni Manzini

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

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

Recommendations

• The Myriad Virtues of Wavelet Trees
• Wavelet trees for all
• Wavelet trees for all
• On wavelet tree construction
• Practical Wavelet Tree Construction

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• An analysis of the Burrows-Wheeler transform
• Boosting textual compression in optimal linear time
• Compressed representations of sequences and full-text indexes
• Inversion Coding
• Lexical Permutation Sorting Algorithm
• Move-to-front, distance coding, and inversion frequencies revisited
• Robust transmission of unbounded strings using Fibonacci representations
• 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
• The Myriad Virtues of Wavelet Trees
• Universal codeword sets and representations of the integers
• When indexing equals compression, experiments with compressing suffix arrays and applications

Cited in

(13)

• The Haar wavelet transform of a dendrogram
• A quick tour on suffix arrays and compressed suffix arrays
• Practical Wavelet Tree Construction
• A space efficient direct access data structure
• Move-to-front, distance coding, and inversion frequencies revisited
• Wheeler graphs: a framework for BWT-based data structures
• Random access to Fibonacci encoded files
• Forty Years of Text Indexing
• On wavelet tree construction
• On optimally partitioning a text to improve its compression
• Wavelet trees for all
• The Myriad Virtues of Wavelet Trees
• Wavelet trees for all

This page was built for publication: The myriad virtues of wavelet trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389347)