Data compression: LZ77

In this appendix, we illustrate the LZ77 compression scheme (Ziv and Lempel, 1977). LZ77 is an adaptive compression algorithm based on the use of a dictionary. It is probably the best-known representative of the family of compressors identified by the acronym LZ (Lempel–Ziv) cite LZ77, which are all based on the same basic idea. LZ77 compresses by reading one character at a time, scrolling the file from beginning to end. Compression is accomplished by replacing a set of newly read characters with a pointer to the previous occurrence of the same set. The pointer indicates at what distance from the current reading point the sequence of characters identical to the one just encountered is located and the length of this sequence. LZ77 performs the substitution only when the previous occurrence is within a sliding window of fixed length |$l$|⁠, containing the last |$l$| characters read. The dictionary then consists of the |$l$| characters preceding the read point. LZ77 searches the dictionary for the longest possible string that matches the new characters, and there is a minimum threshold (usually three characters) for the substitution to occur.