huffman-coding · shipping · also Huffman code

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

  1. 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 (accessed 2026-11-17)
  2. RFC 1951: prefix codes and DEFLATE code descriptions, sections 3.2.1-3.2.2 and 3.2.7 (accessed 2026-11-17)
  3. Hesela: prefix decoding, Rice parameters and payload accounting (accessed 2026-11-17)
Sources & caveats
  • Source synthesis and a synthetic prefix-code illustration; not a complete DEFLATE decoder, optimal-file-size guarantee or measured corruption rate.

JSON: /data/terms/huffman-coding.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Huffman coding. Hesela. 2026-11-19. https://hesela.dev/terms/huffman-coding/