LZ77encoderingsmethoden

LZ77 encoding is a lossless data compression technique introduced by Abraham Lempel and Jacob Ziv in 1977. It compresses data by replacing repeated phrases with references to earlier occurrences within a sliding window, rather than encoding the data again.

The encoder maintains a sliding window that consists of a search buffer containing previously decoded data and a lookahead buffer with upcoming symbols. The encoder searches for the longest match of the lookahead string in the search buffer. If a match is found, it emits a token describing the distance (offset) back to the match and the length of the match; a symbol following the match (the next symbol) may be included as part of the token or emitted separately, depending on the variant. If no sufficient match is found, the encoder outputs a literal symbol. Practical implementations usually constrain the maximum offset and length to fit the available buffers.

Decoding is straightforward: the decoder reads the tokens and copies length characters from the output at the given offset to reconstruct the original data, then appends the following symbol.

LZ77 is a foundational algorithm and serves as the basis for several modern compressors. Variants such as LZSS modify how matches are encoded to favor literals in some cases. In practice, LZ77 is combined with entropy coding (for example, Huffman or arithmetic coding) in standards such as DEFLATE, which underpins ZIP and gzip formats. The approach is efficient and streaming-friendly but its compression depends on data redundancy and the chosen window size; it performs poorly on highly random data.