The myriad virtues of wavelet trees

Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

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.

Lingua originaleInglese
Titolo della pubblicazione ospiteAutomata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings
EditoreSpringer Verlag
Pagine560-571
Numero di pagine12
ISBN (stampa)3540359044, 9783540359043
DOI
Stato di pubblicazionePubblicato - 2006
Pubblicato esternamente
Evento33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 - Venice, Italy
Durata: 10 lug 200614 lug 2006

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4051 LNCS
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???33rd International Colloquium on Automata, Languages and Programming, ICALP 2006
Paese/TerritorioItaly
CittàVenice
Periodo10/07/0614/07/06

Fingerprint

Entra nei temi di ricerca di 'The myriad virtues of wavelet trees'. Insieme formano una fingerprint unica.

Cita questo