http://www.cnr.it/ontology/cnr/individuo/prodotto/ID83619

The Myriad Virtues of Wavelet Trees (Contributo in atti di convegno)

Type

Label

Anno

Alternative label

[1] Manzini G., [2] Ferragina P., [3] Giancarlo R. (2006)
The Myriad Virtues of Wavelet Trees
in 33rd International Colloquium on Automata, Languages and Programming (ICALP '06), Venice, Italy, 10-14 July 2006
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Pagina inizio

Pagina fine

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#volumeInCollana

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

Note

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

[1] CNR-IIT, Pisa, Italy; [2] Dipartimento di Informatica, Università di Pisa, Pisa, Italy; [3] Dipartimento di Matematica ed Applicazioni, Università di Palermo, Palermo, Italy (literal)

Titolo

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn

Abstract

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. (literal)

Editore