LZ-77
Main features
- dictionary compression method
- one-pass compression method
- adaptive compression method
- asymetric compression method
- suitable for compressing once and decompressing often
- used in gzip, zip, pkzip
History
Original method of sliding window was designed in 1977 by Abrahamem Lempel and Jacob Ziv. It forms a basis for LZ variations.
Description
This method uses window divided to search buffer and look-ahead buffer. Size of the search buffer is usually 8 192 bits and size of the look-ahead buffer about 10 to 20 bits. In demonstration both parameters can be set.
The algorithm can be described as follows. First the longest prefix of a look-ahead buffer that starts in search buffer is found. This prefix is encoded as triplet (i, j, X) where i is the distance of the begining of the found prefix from the end of the search buffer, j is the length of the found prefix and X is the first character after the prefix in look-ahead buffer. The following applet visualizes this algorithm. The number of bits written to the output depends on used encoding of numbers.
Pseudo-code
1: begin
2: fill view from input
3: while (view not empty) do
4: begin
5: find longest prefix p of view starting in coded part
6: i := position of p in window
7: j := length of p
8: X := first char after p in view
9: output(i,j,X)
10: add j+1 chars
11: end
12: end
References
- LZ77. Wikipedia, the free encyclopedia.
- Aplications using LZ77
- Story, a little humorous, about compression algorithms, mainly algorithms of the family LZ, and its patents
- Michael Dipperstein: LZSS (LZ77) Discussion and Implementation.