The Myriad Virtues of Suffix Trees

Raffaele Giancarlo, Paolo Ferragina, Giovanni Manzini

Risultato della ricerca: Chapter

13 Citazioni (Scopus)

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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteLECTURE NOTES IN COMPUTER SCIENCE
Pagine560-571
Numero di pagine12
Stato di pubblicazionePublished - 2006

Serie di pubblicazioni

NomeLNCS

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

Fingerprint

Entra nei temi di ricerca di 'The Myriad Virtues of Suffix Trees'. Insieme formano una fingerprint unica.

Cita questo