loading...
Fast Compression with a Static Model in High-Order Entropy
Snowbird, Utah March 23-March 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2004.1281451Data Compression Conference (DCC '04)
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Luca Foschini, Scuola Superiore Sant'Anna, Italy
Roberto Grossiy, Universit? di Pisa, Italy
Ankur Guptaz, Duke University, Durham, NC
Jeffrey Scott Vitter, Purdue University, West Lafayette, IN
We report on a simple encoding format called wzip for decompressing block-sorting transforms, such as the Burrows-Wheeler Transform (BWT). Our compressor uses the simple notions of gamma encoding and RLE, organized with a wavelet tree, to achieve a slightly better compression ratio than bzip2 in less time. In fact, our compression/decompression time is dependent on Hh, the hth order empirical entropy. This relationship of performance to the compressibility of data is a key new idea among compression algorithms. Another key contribution of our compressor is its simplicity. Our compressor can also operate as a full-text index with a small amount of data, while still preserving backward compatibility with just the compressor.
Citation:
Luca Foschini, Roberto Grossiy, Ankur Guptaz, Jeffrey Scott Vitter, "Fast Compression with a Static Model in High-Order Entropy," dcc, pp.62, Data Compression Conference (DCC '04), 2004
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions