Fast Compression with a Static Model in High-Order Entropy

Abstract

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.