Paper Info
Title
The engineering of a compression boosting library: theory vs practice in BWT compression
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.
Year
DOI
Venue
2006
10.1007/11841036_67
ESA
Keywords
Field
DocType
compression boosting,myriad new compression algorithm,move-to-front encoding,art bwt compression,burrows-wheeler compression process,move-to-front yield,wavelet trees,compression performance,theory vs practice,data compression,engineer compression,compression algorithm,algorithm design,run length encoding,indexation
Algorithm design,Computer science,Compression ratio,Boosting (machine learning),Engineering design process,Artificial intelligence,Data compression,Machine learning,Lossless compression,Wavelet,Encoding (memory)
Conference
Volume
ISSN
ISBN
4168
0302-9743
3-540-38875-3
Citations 
PageRank 
References 
16
0.83
15
Authors
3
Name
Order
Citations
PageRank
Paolo Ferragina12220130.64
Raffaele Giancarlo21112107.23
Giovanni Manzini31584111.42