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 asymp- totic 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, Huff- man and Arithmetic encoders) and Wavelet Trees of properly-designed shapes. As a corollary, we prove high-order entropy bounds for the chal lenging combination of Burrows-Wheeler Transform and Wavelet Trees.

FERRAGINA, P., GIANCARLO, R., MANZINI, G. (2006). The Myriad Virtues of Suffix Trees. In LECTURE NOTES IN COMPUTER SCIENCE (pp. 560-571) [10.1007/11786986_49].

The Myriad Virtues of Suffix Trees

GIANCARLO, Raffaele;
2006-01-01

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 asymp- totic 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, Huff- man and Arithmetic encoders) and Wavelet Trees of properly-designed shapes. As a corollary, we prove high-order entropy bounds for the chal lenging combination of Burrows-Wheeler Transform and Wavelet Trees.
2006
FERRAGINA, P., GIANCARLO, R., MANZINI, G. (2006). The Myriad Virtues of Suffix Trees. In LECTURE NOTES IN COMPUTER SCIENCE (pp. 560-571) [10.1007/11786986_49].
File in questo prodotto:
File Dimensione Formato  
Giancarlo_ICALP_06.pdf

Solo gestori archvio

Dimensione 543.44 kB
Formato Adobe PDF
543.44 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/27205
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact