Huffman coding
Huffman coding constructs a prefix code that minimizes average codeword length for given symbol frequencies.
Optimality: The 1952 construction repeatedly combines the two least likely messages. Its guarantee minimizes expected codeword length for the specified probabilities under the prefix-code model and equal cost per coding digit; it does not minimize every file or its metadata. Equal-frequency choices can yield different optimal codes. [1]
Decoding: The symbol-to-code mapping and stream boundaries remain necessary. The lengths 1,2,3,3 alone do not distinguish swapping the codewords assigned to C and D; canonical reconstruction also needs symbol order and the format rules. DEFLATE describes canonical codes using ordered code lengths; length zero means an unused symbol. Its single used distance symbol still has a one-bit code. These are format rules, not a universal single-symbol policy. [2]
Accounting: A shorter symbol payload need not yield a smaller file after codebook and framing costs. The linked four-symbol example uses 28 payload bits instead of 32 fixed-width bits. [3]
Integrity: A changed bit can still form valid codewords with unchanged decoded length; prefix validity is not an integrity check. The linked exact example decodes ABCD as ABCC after one bit changes. [3]
Relations
- related
- Prefix-free code, DEFLATE, Finite State Entropy, Lossless compression, Rice coding, Wavelet tree, Wavelet matrix, Tunstall coding, Comma-free code, Entropy coding, Arithmetic coding
Citations
- David A. Huffman (1952), A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE 40(9), 1098-1101; DOI 10.1109/JRPROC.1952.273898
- RFC 1951: prefix codes and DEFLATE code descriptions, sections 3.2.1-3.2.2 and 3.2.7
- Hesela: prefix decoding, Rice parameters and payload accounting
Sources & caveats
- Source synthesis and a synthetic prefix-code illustration; not a complete DEFLATE decoder, optimal-file-size guarantee or measured corruption rate.