Huffman coding: building the tree, codes, total bits

Huffman coding compresses a text by giving each character a bit string of variable length: a frequent character gets a short code, a rare one gets a long code. The algorithm is greedy: at each step it merges the two smallest frequencies. Almost always the same question comes in the exam: “Build the Huffman tree with these frequencies, write the codes, compute the total bits.” Sometimes “decode this bit string” or “what is the saving compared with a fixed-length code?” is added after it.

Golden rules:

1. At each step, merge the two smallest nodes in the queue. The weight of the new node is the sum of the two.
2. The new node goes back into the queue and competes like a leaf in the following steps.
3. Left 0, right 1. Which one goes to the left depends on the rule in the question; write it down and follow it.
4. Total bits = Σ (frequency × code length).
5. The tie rule can change the codes, never the total bits.

Fixed length and variable length

Think of a 50-character text with 6 different characters. In a fixed-length code each character needs $\lceil \log_2 6 \rceil = 3$ bits: 50 × 3 = 150 bits. But the characters are not all equally frequent:

If we give C a short code and E a long code, the total goes down. The only condition: decodability. For this the code must be a prefix code. No code can be the beginning of another code. If you put the codes on the leaves of a binary tree, this is satisfied automatically: the path to one leaf cannot be the beginning of the path to another leaf, because there is no other node below a leaf.

The algorithm

1. A leaf for each character, all into a min-PQ
2. While there is more than one node in the PQ:
     x = deleteMin   (left child)
     y = deleteMin   (right child)
     z = new node: weight x+y, children x, y
     add z to the PQ
3. The one remaining node is the root

For n characters exactly n−1 merges are made. With a heap each operation is $O(\log n)$: the total is $O(n \log n)$.

Worked example

Frequencies E=2, B=4, D=7, A=10, F=12, C=15. In each row write the sorted state of the queue; this is the safest way not to make mistakes in the exam.

queue (sorted)               merge
E2 B4 D7 A10 F12 C15         E2 + B4   = 6
6 D7 A10 F12 C15             6 + D7    = 13
A10 F12 13 C15               A10 + F12 = 22
13 C15 22                    13 + C15  = 28
22 28                        22 + 28   = 50
50                           root

  merge 1: E(2) + B(4) = 6
  merge 2: (EB)(6) + D(7) = 13
  merge 3: A(10) + F(12) = 22
  merge 4: ((EB)D)(13) + C(15) = 28
  merge 5: (AF)(22) + (((EB)D)C)(28) = 50

Note step 3: 13 was just created, but A10 and F12 are smaller than it, so they were merged first. A new node does not automatically enter the next merge; it does so only if its weight is one of the two smallest.

The tree (left edge 0, right edge 1):

              (50)
            0/    \1
          (22)    (28)
         0/ \1   0/  \1
        A10 F12 (13)  C15
               0/  \1
              (6)   D7
             0/ \1
            E2   B4

Read the codes from the path from the root to the leaf:

  codes {A=00, B=1001, C=11, D=101, E=1000, F=01} total bits 119 of 50 symbols, avg 2.38

The average code length is $119 / 50 = 2.38$ bits. The fixed code took 150 bits; the saving is 31 bits, about 20.7%.

TIP · check the total bits in two ways. Add up the weights of the internal nodes: 6 + 13 + 22 + 28 + 50 = 119. The frequency of each character is counted once at each internal node on the path from the root to its leaf, that is, exactly as many times as its code length. If the two ways do not give the same number, there is a mistake in the tree.

Encoding and decoding

Encoding: write the code of each character one after another. FACE → 01 00 11 1000 = 0100111000 (10 bits).

Decoding: read the bits from the left, go down from the root in the tree (0 left, 1 right). When you reach a leaf, write that character and return to the root.

bit string: 1001001110100
1 0 0 1   → leaf B   return to the root
0 0       → leaf A
1 1       → leaf C
1 0 1     → leaf D
0 0       → leaf A
result: BACDA

  decode 1001001110100 -> BACDA
  encode FACE -> 0100111000 (10 bits)

Tie cases

If two nodes have the same weight, which one comes out first is not defined. In the exam the rule is given; if it is not, write your own rule and apply it consistently. A common rule: “first in, first out”, that is, leaves come before newly created internal nodes.

Example: a=1, b=1, c=2, d=3, e=5.

a1 b1 c2 d3 e5      a1 + b1   = 2
c2 2 d3 e5          c2 + 2    = 4 (c first)
d3 4 e5             d3 + 4    = 7
e5 7                e5 + 7    = 12

      (12)
     0/  \1
     e   (7)
        0/ \1
        d  (4)
          0/ \1
          c  (2)
            0/ \1
            a   b

  codes {a=1110, b=1111, c=110, d=10, e=0} total bits 25 of 12 symbols, avg 2.0833333333333335

When the frequencies grow like Fibonacci, the tree leans to one side and the rarest character gets a code of n−1 bits. Conversely, if all frequencies are equal (w=x=y=z=4), Huffman returns to a fixed-length code: 00, 01, 10, 11.

PITFALL · what if c and (ab) swap places? The codes change (like c=111, a=1100) but the total is 25 bits in both trees. In the exam the codes may come out different depending on the rule; the grader checks the total bits and the validity of the tree. Write your rule at the top of your answer.

Why is greedy correct here?

Two observations are enough:

1. In an optimal prefix code, the two characters with the lowest frequencies are siblings at the deepest level. If not, swapping with a character that is deeper does not increase the total.
2. If you think of these two characters as a single “combined character”, what remains is the same problem with one fewer character (optimal substructure).

So the choice “merge the two smallest frequencies” always leads to an optimal tree.

Building it in Java

static class Node {
    char ch; int freq; Node left, right;
    Node(char ch, int freq, Node left, Node right) {
        this.ch = ch; this.freq = freq; this.left = left; this.right = right;
    }
}
static Node build(char[] ch, int[] freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    for (int i = 0; i < ch.length; i++) pq.add(new Node(ch[i], freq[i], null, null));
    while (pq.size() > 1) {
        Node l = pq.poll(), r = pq.poll();
        pq.add(new Node('\0', l.freq + r.freq, l, r));
    }
    return pq.poll();
}

Common mistakes

1) E2 + B4   = 6
2) 6  + D7   = 13
3) A10 + F12 = 22
4) 13 + C15  = 28
5) 22 + 28   = 50 (root)

1) a1 + b1   = 2  (the new node goes last)
2) c2 + (ab)2 = 4 (c entered first, left)
3) d3 + 4    = 7
4) e5 + 7    = 12

static Node build(char[] ch, int[] freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    for (int i = 0; i < ch.length; i++)
        pq.add(new Node(ch[i], freq[i], null, null));
    while (pq.size() > 1) {
        Node left = pq.poll();               // the smallest
        Node right = pq.poll();              // the second smallest
        pq.add(new Node('\0', left.freq + right.freq, left, right));
    }
    return pq.poll();
}

static void printCodes(Node n, String code) {
    if (n == null) return;
    if (n.left == null && n.right == null) {
        System.out.println(n.ch + " = " + code);
        return;
    }
    printCodes(n.left, code + "0");
    printCodes(n.right, code + "1");
}