Fast Compression with a Static Model in High-Order Entropy

View/ Open
Issue Date
2004Author
Foschini, Luca
Grossi, Roberto
Gupta, Ankur
Vitter, Jeffrey Scott
Publisher
IEEE
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
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 ration than bzip2 in less time. In fact, our compres-
sion/decompression time is dependent on Hh, the empirical hth order entropy. Another
key contribution of our compressor is its simplicity. Our compressor can also oper-
ate as a full-text index with a small amount of data, while still preserving backward
compatibility with just the compressor.
Description
(c) 2004 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Collections
Citation
L. Foschini, R. Grossi, A. Gupta, and J. S. Vitter. “Fast Compression with a Static Model in High-Order Entropy,” Proceedings of the 2004 IEEE Data Compression Conference (DCC ’04), Snowbird, UT, March 2004, 62–71. http://dx.doi.org/10.1109/DCC.2004.1281451
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.