6533b7d0fe1ef96bd125a32b
RESEARCH PRODUCT
The Myriad Virtues of Wavelet Trees
Giovanni ManziniPaolo FerraginaRaffaele Giancarlosubject
Binary treeWeight-balanced treeWavelet transformCascade algorithmData_CODINGANDINFORMATIONTHEORYHuffman codingData CompressionTheoretical Computer ScienceComputer Science ApplicationsSet partitioning in hierarchical treessymbols.namesakeWaveletComputational Theory and Mathematicssymbolsempirical entropyBurrows-Wheeler TransformAlgorithmData compressionMathematicsInformation SystemsWavelet Treesdescription
Wavelet Trees have been introduced in [Grossi, Gupta and Vitter, SODA '03] and have been rapidly recognized as a very flexible tool for the design of compressed full-text indexes and data compressors. Although several papers have investigated the beauty and usefulness of this data structure in the full-text indexing scenario, its impact on data compression has not been fully explored. In this paper we provide a complete theoretical analysis of a wide class of compression algorithms based on Wavelet Trees. We also show how to improve their asymptotic performance by introducing a novel framework, called Generalized Wavelet Trees, that aims for the best combination of binary compressors (like, Run-Length encoders) versus non-binary compressors (like, Huffman and Arithmetic encoders) and Wavelet Trees of properly-designed shapes. As a corollary, we prove high-order entropy bounds for the challenging combination of Burrows-Wheeler Transform and Wavelet Trees.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-08-01 |