Unit 9: Huffman Coding and Data Compression

I. Foundations of Lossless Compression

Data compression represents information using fewer bits than its original representation. Huffman coding, developed by David A. Huffman (1952), is a lossless compression method that assigns short variable-length codewords to frequent symbols and longer codewords to rare symbols. Its governing principle is that compression improves when code lengths reflect symbol probabilities while preserving unique decodability.

• Defining properties:
  • Lossless reconstruction: Decoding reproduces the original data exactly; no symbol or bit of source information is discarded.
  • Statistical modeling: A source alphabet (\Sigma={s_1,s_2,\ldots,s_n}) is associated with frequencies (f_i) or probabilities (p_i), where (p_i=f_i/\sum_j f_j).
  • Variable-length representation: Different source symbols may receive codewords of different lengths; frequent symbols generally receive shorter codewords.
  • Prefix-free convention: No valid codeword is a prefix of another. Thus a decoder can recognize each symbol without separators or look-ahead ambiguity.
  • Binary-tree interpretation: Every symbol is stored at a leaf; a left edge is conventionally labeled (0), and a right edge (1).
  • Optimization objective: For codeword length (li), the expected number of bits per source symbol is
    [
    L=\sum{i=1}^{n}p_i l_i
    ]
    where (L) is average code length, (p_i) is the probability of (s_i), and (l_i) is its codeword length.
  • Algorithmic strategy: Huffman coding uses a greedy choice—repeatedly combining the two least-frequent items—and implements it efficiently with a min-priority queue.
  • Compression boundary: The encoded payload may be smaller than the input, but practical storage must also account for metadata such as the coding tree, frequencies, or code lengths.

II. Huffman Coding — Greedy Construction of an Optimal Prefix Code

A. Definition and Governing Principle

Huffman coding constructs a minimum-weight binary prefix tree for symbols whose frequencies or probabilities are known.

• Input: A collection of (n) symbols, each with a positive weight (w_i), normally its occurrence frequency (f_i) or probability (p_i).
• Output: A prefix-free binary code in which the weighted external path length is minimized:
  [
  C=\sum_{i=1}^{n} w_i d_i
  ]
  where (C) is total coding cost and (d_i) is the depth—and therefore codeword length—of symbol (s_i).
• Greedy choice: The two nodes with the smallest weights are made siblings at the greatest currently constructed depth.
• Optimal substructure: If the two least-frequent symbols (x) and (y) are replaced by one pseudo-symbol of weight (w_x+w_y), an optimal code for the reduced alphabet can be expanded into an optimal code for the original alphabet.
• Prefix condition: Because symbols occur only at leaves, reaching a leaf completes exactly one codeword; no leaf’s path can continue to another leaf.
• Non-uniqueness: Equal frequencies can permit different tree shapes or bit assignments. These alternatives may produce different codewords but the same optimal weighted cost.

B. Huffman Coding

Huffman coding repeatedly merges the two least-frequent nodes until one root remains, then derives each codeword from its root-to-leaf path.

• Tree construction:
  1. Create one leaf node for each symbol and insert all leaves into a min-priority queue keyed by frequency.
  2. Remove the two nodes (x) and (y) with minimum weights.
  3. Create an internal node (z) with (w_z=w_x+w_y), making (x) and (y) its children.
  4. Insert (z) into the queue and repeat until only the root remains.
• Pseudocode:
  
  TEXT

    HUFFMAN(symbols):
        Q = min-priority-queue(symbols)
        while Q.size > 1:
            x = Q.extractMin()
            y = Q.extractMin()
            z = new internal node
            z.weight = x.weight + y.weight
            z.left = x
            z.right = y
            Q.insert(z)
        return Q.extractMin()

  
  Here, (Q) is the min-priority queue; (x) and (y) are minimum-weight nodes; and (z) is their combined parent.
• Code generation: Traverse from the root, appending (0) on a left edge and (1) on a right edge. The accumulated bit string at leaf (s_i) is its codeword.
• Worked example: Consider frequencies (A:5), (B:9), (C:12), (D:13), (E:16), and (F:45).
  • Merge (A(5)+B(9)=14).
  • Merge (C(12)+D(13)=25).
  • Merge (14+E(16)=30).
  • Merge (25+30=55).
  • Merge (F(45)+55=100).
  • One valid assignment is (F=0), (C=100), (D=101), (A=1100), (B=1101), and (E=111).
  • Its total cost is
    [
    C=45(1)+12(3)+13(3)+5(4)+9(4)+16(3)=224
    ]
    For (100) source symbols, the average is (L=224/100=2.24) bits per symbol, compared with (3) bits per symbol for a fixed-length code over six symbols.
• Encoding: Replace each source symbol with its codeword and concatenate the results. For the code above, (FACE) becomes (0\,1100\,100\,111).
• Decoding: Begin at the root and follow one edge per input bit. Emit a symbol upon reaching a leaf, return to the root, and continue with the next unread bit.
• Correctness basis:
  • Sibling property: In some optimal prefix tree, the two least-weight symbols can be placed as sibling leaves at maximum depth.
  • Reduction step: Replacing those siblings by their parent reduces the problem from (n) symbols to (n-1).
  • Inductive conclusion: Solving each reduced problem optimally and expanding the merged nodes yields an optimal binary prefix code.
• Time complexity: Building a heap takes (O(n)); the algorithm performs (n-1) merges, each involving priority-queue operations of (O(\log n)), giving (O(n\log n)) total time.
• Space complexity: A full binary Huffman tree has (n) leaves and (n-1) internal nodes, so tree and queue storage are (O(n)).
• Important qualification: Huffman coding is optimal among binary prefix codes for the supplied symbol weights; it does not necessarily achieve the best compression possible among every conceivable coding scheme.

C. Variants, Applications, and Limitations

Huffman coding is adapted to practical formats by changing how the tree is represented or how source statistics are obtained.

• Static Huffman coding: Frequencies are counted before encoding, and one fixed tree encodes the complete input; the decoder must receive sufficient tree information.
• Adaptive Huffman coding: Encoder and decoder update the tree as symbols arrive, avoiding an initial frequency table but increasing implementation complexity.
• Canonical Huffman coding: Only code lengths need to be stored; codewords are reconstructed in a standard order, producing compact metadata and efficient table-based decoding.
• Applications: Huffman coding appears as an entropy-coding stage in formats and systems such as DEFLATE, where repeated strings are first represented through dictionary matching and resulting symbols are then Huffman-coded.
• Advantages: It is lossless, conceptually simple, fast, and guaranteed to find an optimal prefix code for the given independent symbol weights.
• Limitations:
  • At least one whole bit is normally assigned per encoded symbol, so highly probable symbols cannot receive fractional-bit code lengths.
  • If source frequencies are nearly uniform, variable-length coding provides little advantage over fixed-length coding.
  • A mismatched or outdated frequency model can increase encoded size.
  • Tree or codebook metadata may outweigh savings for short inputs.
  • Symbol-by-symbol coding ignores dependencies such as common pairs, words, or repeated substrings unless the source alphabet or earlier processing captures them.

III. Data Compression Problems — Models, Measures, and Design Trade-offs

A. Problem Definition and Classification

A data compression problem asks how to represent a source compactly while satisfying a required level of reconstructability, efficiency, and resource usage.

• Formal view: An encoder maps source data (X) to a bit string (E(X)), while a decoder maps that representation to (\hat X=D(E(X))).
• Lossless condition:
  [
  D(E(X))=X
  ]
  Every source value must be recovered exactly; examples include program files, database records, and source code.
• Lossy condition:
  [
  D(E(X))=\hat X,\qquad \hat X\approx X
  ]
  Approximation is permitted under a distortion criterion; image, audio, and video systems commonly exchange some fidelity for a lower bitrate.
• Core challenge: Compression depends on finding redundancy—predictable, repeated, or statistically uneven structure—without spending more bits describing the model than the model saves.

B. Data Compression Problems

Data compression problems are solved by matching a source model and coding method to the data’s redundancy and the application’s constraints.

• Redundancy types:
  • Statistical redundancy: Symbols have unequal probabilities; Huffman coding exploits this by assigning lengths according to frequency.
  • Repetition redundancy: Strings recur within the data; dictionary methods replace repeated strings with references.
  • Contextual redundancy: A symbol’s probability depends on preceding symbols; context or predictive models exploit these dependencies.
  • Perceptual redundancy: Some signal details have limited human perceptual importance and can be discarded only in lossy compression.
• Compression ratio:
  [
  R=\frac{S{\text{original}}}{S{\text{compressed}}}
  ]
  where (S{\text{original}}) and (S{\text{compressed}}) are sizes measured in the same unit. A (10\text{ MB}) file reduced to (4\text{ MB}) has (R=2.5).
• Space saving:
  [
  \text{Saving}=\left(1-\frac{S{\text{compressed}}}{S{\text{original}}}\right)\times100\%
  ]
  The same (10\text{ MB})-to-(4\text{ MB}) result saves (60\%).
• Entropy benchmark: For symbol probabilities (pi), source entropy is
  [
  H(X)=-\sum{i=1}^{n}p_i\log_2 p_i
  ]
  where (H(X)) is measured in bits per symbol. For binary Huffman coding, the expected length satisfies (H(X)\le L<H(X)+1).
• Major trade-offs:
  1. Compression effectiveness: Richer models may reduce output size by capturing more structure.
  2. Computational efficiency: Richer models may require more encoding time, decoding time, memory, and metadata.
• Edge cases: Already compressed, encrypted, or near-random data contains little exploitable redundancy; added headers can make the compressed result larger than the input.
• Evaluation criteria: A sound solution considers compressed size, encode/decode speed, memory use, random-access needs, error sensitivity, implementation complexity, and—only for lossy methods—acceptable distortion.
• Role of Huffman coding: Huffman coding addresses the entropy-coding part of the problem. Practical compressors often combine transformation, prediction, run-length encoding, or dictionary matching with Huffman coding rather than relying on it alone.