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

The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression (Contributo in atti di convegno)

Type

Prodotto della ricerca (Classe)
Contributo in atti di convegno (Classe)

Label

The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression (Contributo in atti di convegno) (literal)

Anno

2006-01-01T00:00:00+01:00 (literal)

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

10.1007/11841036_67 (literal)

Alternative label

[1] Manzini G., [2] Ferragina P., [3] Giancarlo R. (2006)
The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression
in European Symposium on Algorithms (ESA '06), Zürich, Switzerland, 11-13 Sep 2006
(literal)

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

[1] Manzini G., [2] Ferragina P., [3] Giancarlo R. (literal)

Pagina inizio

756 (literal)

Pagina fine

767 (literal)

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

Codice Puma: cnr.iit/2006-A2-034 (literal)

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

4168 (literal)

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

http://dx.doi.org/10.1007/11841036_67 (literal)

Note

ISI Web of Science (WOS) (literal)
Scopu (literal)

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 Applicazioni, Università di Palermo, Palermo, Italy (literal)

Titolo

The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression (literal)

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

3-540-38875-3 (literal)

Abstract

Data Compression is one of the most challenging arenas both for algorithm design and engineering. This is particularly true for Burrows and Wheeler Compression a technique that is important in itself and for the design of compressed indexes. There has been considerable debate on how to design and engineer compression algorithms based on the BWT paradigm. In particular, Move-to-Front Encoding is generally believed to be an \"inefficient \" part of the Burrows-Wheeler compression process. However, only recently two theoretically superior alternatives to Move-to-Front have been proposed, namely Compression Boosting and Wavelet Trees. The main contribution of this paper is to provide the first experimental comparison of these three techniques, giving a much needed methodological contribution to the current debate. We do so by providing a carefully engineered compression boosting library that can be used, on the one hand, to investigate the myriad new compression algorithms that can be based on boosting, and on the other hand, to make the first experimental assessment of how Move-to-Front behaves with respect to its recently proposed competitors. The main conclusion is that Boosting, Wavelet Trees and Move-to-Front yield quite close compression performance. Finally, our extensive experimental study of boosting technique brings to light a new fact overlooked in 10 years of experiments in the area: a fast adapting order-zero compressor is enough to provide state of the art BWT compression by simply compressing the run length encoded transform. In other words, Move-to-Front, Wavelet Trees, and Boosters can all be by-passed by a fast learner. (literal)

Editore