Skip to main content
Definition Website Computer and Technology

Huffman Coding

Subject: Computer and Technology noun /ˈhʌf.mən ˌkoʊ.dɪŋ/ 1 definition

  1. Definition (noun)

    Entry #286 · Updated

    Huffman Coding is a greedy, lossless entropy encoding algorithm that compresses data by mapping symbols to variable-length prefix codes according to their frequency of occurrence. It builds a binary code tree bottom-up with a min-heap priority queue, repeatedly merging the two lowest-frequency nodes until a single root remains so that frequent symbols receive shorter bit strings and no codeword is a prefix of another. Because this prefix-free property removes the need for symbol delimiters while minimizing expected codeword length, Huffman coding achieves the optimal symbol-by-symbol compression bound within one bit per symbol of the source's Shannon entropy. Unlike dictionary compressors such as LZ77 or fractional-bit entropy coders like arithmetic coding, it restricts each codeword to an integer number of bits and therefore typically operates as the final encoding stage in formats such as DEFLATE, JPEG, and MP3.

    Common Forms

    • Static Huffman Coding: Scans the input in a first pass to measure exact symbol frequencies, builds a fixed code tree, and writes the codebook into a header before encoding the payload in a second pass.

    • Canonical Huffman Coding: Assigns deterministic bit sequences sorted by codeword length and symbol order so decoders can reconstruct the full codebook solely from code lengths, minimizing header metadata and enabling fast lookup-table decoding.

    • Adaptive Huffman Coding: Updates the code tree dynamically as each symbol is processed using single-pass methods like Vitter's algorithm or FGK, supporting streaming compression without a separate frequency header at the expense of per-symbol tree maintenance.

    • Length-Limited Huffman Coding: Bounds the maximum codeword bit length—such as 15 bits in DEFLATE or 16 bits in JPEG—using algorithms like package-merge so rare symbols cannot produce overly deep trees that complicate hardware or table-based decoders.

    Example

    When an NGINX server delivers a 120 KB JSON response with Content-Encoding: gzip, zlib executes DEFLATE compression by pairing LZ77 match back-references with dynamic canonical Huffman tables capped at 15-bit code lengths. Frequent symbols such as " (0x22), :, and common match lengths receive short prefix codes in the block header's code-length table, enabling the client browser to decode the continuous bitstream sequentially without separator bits.