Improving LZ77 Data Compression using Bit Recycling
Danny Dub�, Vincent Beaudoin · 2006
Many data compression techniques allow for more than one way to encode the compressed form of data. In particular, this is the case for the LZ77 technique and its derivatives, where matches can often be described in more than one way. The very existence of multiple encodings for the same data acts as a side-channel through which additional information can be conveyed from the compressor to the decompressor, and so, for free. We show that this side-channel can be used to carry parts of the compressed file itself, thereby shortening the latter, and improving compression ratios. We call our technique bit recycling and show how it applies to Huffman encoding. We present it as a way to improve LZ77 compression and demonstrate it through many experiments. One of these experiments has already been presented but the new ones take better advantage of recycling. The experiments show that we can improve compression efficiency significantly and tend to point to a method with which bit recycling is most profitable.