Improved LZ77 Compression
Cody Yingquan Wu · 2021
The state-of-the-art LZ77 compression replaces repeated occurrences of a string with references to a single copy of that string existing earlier in the uncompressed string stream. A match is encoded by a pair of numbers called a length-distance pair. To spot matches, the compressor must keep track of some amount of the most recent string, such as the last 4KB, 8KB, or 32KB. The structure in which this string is held is called a sliding window. In practice, searching for the longest string match is expedited by a hash table and a hash chain (it simply uses a hash table when only the first match is considered). In this paper, we present a novel technique to effectively improve the LZ77 compression. Specifically, it applies different sliding windows for each match length, each possibly equipped with different hashing functions. It effectively thwarts the dilemma of the original single-window, wherein a large window size renders short strings incompressible (e.g., a 2-byte match in a 16-bit window) whereas a small window size renders long strings (lying outside of window) incompressible.