Huffman coding

Huffman coding is a lossless method that assigns variable-length bit strings to symbols according to their frequencies. Its codewords form a prefix-free code, enabling unambiguous decoding.

Prefix code: A code in which no codeword is the prefix of another codeword. Huffman codewords can be decoded immediately because no symbol’s codeword begins another’s.
Information theory: The mathematical study of information, communication, and limits on representing and transmitting data. Huffman coding is a practical source-coding method within this broader theory.
DEFLATE: A lossless compression format combining LZ77 back-references with Huffman coding. DEFLATE uses Huffman codes to encode literals, lengths, and distances.
Arithmetic coding: A lossless coding method that represents a sequence as a progressively narrowed interval of real numbers. Unlike Huffman coding, it can approach fractional-bit average costs for individual symbols.
David A. Huffman: An American electrical engineer who devised Huffman coding as a student at MIT. Huffman developed the algorithm while seeking a minimum-redundancy code for a course assignment.
Huffman tree: A binary tree whose leaves represent symbols and whose paths determine their codewords. Each left or right path from the root supplies one symbol’s bit string.
Source coding: The representation of source data as code symbols, often to reduce the number of bits required. Huffman coding is a variable-length source code.
JPEG: A family of image compression standards, commonly using lossy discrete cosine transform coding. Baseline JPEG applies Huffman coding to run-length-encoded quantized coefficients.
Shannon–Fano coding: A variable-length prefix coding method that recursively divides symbols into groups of similar total probability. It resembles Huffman coding but does not always produce an optimal prefix code.
A Method for the Construction of Minimum-Redundancy Codes: A 1952 paper by David A. Huffman presenting an algorithm for constructing minimum-redundancy codes. This paper introduced the coding method and established its original formulation.

Linked from 12 pages