Wing

Compression & Coding

1950s

Huffman Coding

David A. Huffman, 1952

Builds an optimal prefix code by repeatedly merging the two least frequent subtrees, minimizing expected codeword length for given symbol frequencies.

1960s

Run-Length Encoding

Folklore (IBM), 1967

Replaces each maximal run of identical symbols with a count and the symbol, shrinking repetitive data.

1970s

LZ77

Jacob Ziv & Abraham Lempel, 1977

Compresses by replacing repeated substrings with (distance, length) references into a sliding window, plus the next literal symbol.

LZ78

Jacob Ziv & Abraham Lempel, 1978

Builds a dictionary of phrases on the fly and encodes each step as a reference to a known phrase plus the next character.

1990s

LZMA Pipeline (7z)

Igor Pavlov, 1999

Combines dictionary matching with a range coder and heavy context modeling for high compression ratios.