Huffman Coding

The problem, simply

You get some letters and how often each one appears in a message. You want to write every letter as a code of 0s and 1s so the whole message uses as few bits as possible.

One rule: no code may be the start of another code. Then a reader can split a long string of bits back into letters without any spaces. Give back the code for every letter. The total bits, the sum of count * code length, is what you are making small.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep all the cards in a plain list. Every round, scan the list for the two smallest, remove them, and add their joined card.

1. Make one leaf per letter.
2. While more than one card is left: find the smallest card by scanning, remove it, find the next smallest by scanning, remove it, add a new card with both as children.
3. Walk the final tree, adding 0 when going left and 1 when going right, to read the codes.

class HuffNode {
    char ch;
    int freq;
    HuffNode left, right;
    HuffNode(char ch, int freq) { this.ch = ch; this.freq = freq; }
    HuffNode(HuffNode l, HuffNode r) { this.freq = l.freq + r.freq; this.left = l; this.right = r; }
    boolean isLeaf() { return left == null && right == null; }
}

class Solution {
    public Map<Character, String> huffmanCodes(char[] chars, int[] freq) {
        List<HuffNode> cards = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) cards.add(new HuffNode(chars[i], freq[i]));

        while (cards.size() > 1) {
            HuffNode a = cards.remove(smallest(cards));  // scan for the smallest
            HuffNode b = cards.remove(smallest(cards));  // and the next smallest
            cards.add(new HuffNode(a, b));
        }

        Map<Character, String> codes = new HashMap<>();
        if (!cards.isEmpty()) read(cards.get(0), "", codes);
        return codes;
    }

    private int smallest(List<HuffNode> cards) {
        int best = 0;
        for (int i = 1; i < cards.size(); i++) {
            if (cards.get(i).freq < cards.get(best).freq) best = i;
        }
        return best;
    }

    private void read(HuffNode node, String path, Map<Character, String> codes) {
        if (node.isLeaf()) {
            codes.put(node.ch, path.isEmpty() ? "0" : path);  // one letter alone gets "0"
            return;
        }
        read(node.left, path + "0", codes);
        read(node.right, path + "1", codes);
    }
}

How long it takes: n - 1 rounds, each scanning up to n cards, O(n^2). Extra room: the cards and the tree, O(n).

Way 2: the clever way

The only thing we ever need is "the two smallest cards". A min heap hands out the smallest item in O(log n) and takes a new one in O(log n).

1. Push every letter into a min heap keyed by its count.
2. While the heap has more than one item: pop two, join them under a new parent whose count is their sum, push the parent.
3. The last item is the root. Read the codes by walking the tree.

Why join the two rarest? In a best tree, the two rarest letters can always sit side by side at the very bottom. Joining them and treating the pair as one letter leaves the same problem, one letter smaller.

class HuffNode {
    char ch;
    int freq;
    HuffNode left, right;
    HuffNode(char ch, int freq) { this.ch = ch; this.freq = freq; }
    HuffNode(HuffNode l, HuffNode r) { this.freq = l.freq + r.freq; this.left = l; this.right = r; }
    boolean isLeaf() { return left == null && right == null; }
}

class Solution {
    public Map<Character, String> huffmanCodes(char[] chars, int[] freq) {
        PriorityQueue<HuffNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.freq, y.freq));
        for (int i = 0; i < chars.length; i++) heap.add(new HuffNode(chars[i], freq[i]));

        while (heap.size() > 1) {
            HuffNode a = heap.poll();          // smallest goes on the 0 side
            HuffNode b = heap.poll();          // next smallest on the 1 side
            heap.add(new HuffNode(a, b));
        }

        Map<Character, String> codes = new HashMap<>();
        if (!heap.isEmpty()) read(heap.poll(), "", codes);
        return codes;
    }

    private void read(HuffNode node, String path, Map<Character, String> codes) {
        if (node.isLeaf()) {
            codes.put(node.ch, path.isEmpty() ? "0" : path);
            return;
        }
        read(node.left, path + "0", codes);
        read(node.right, path + "1", codes);
    }

    // Decoding: follow the bits down the tree, print a letter at each leaf, jump back to the top.
    public String decode(HuffNode root, String bits) {
        StringBuilder out = new StringBuilder();
        HuffNode cur = root;
        for (char b : bits.toCharArray()) {
            if (!root.isLeaf()) cur = (b == '0') ? cur.left : cur.right;
            if (cur.isLeaf()) {
                out.append(cur.ch);
                cur = root;
            }
        }
        return out.toString();
    }
}

How long it takes: n - 1 rounds, each with two pops and one push at O(log n), so O(n log n). Reading the codes visits every node once. Extra room: the heap and the tree, O(n).

Watch out for

• A single letter gives a tree with no edges. Give it the code 0 by hand.
• The tree must be built bottom up. Building it from the top, by splitting letters into halves, is a different method (Shannon Fano) and is not always optimal.
• Counts can be big. If you sum count * length, use long.
• Decoding needs the same tree. Send the tree, or the code lengths, along with the bits.

What interviewers ask next

• Why is no code the start of another? Letters live only at leaves. A path that stops at one leaf cannot continue to another leaf.
• Can you build it faster when the counts come sorted? Yes, in O(n): keep two waiting lines, one for the sorted leaves and one for new parents. New parents come out in increasing order, so the two smallest are always at the fronts of the two lines.
• Join ropes or files at the least total cost? Same greedy: always join the two smallest (see Minimum Cost of Ropes).
• What if a code may use 3 symbols instead of 2? Join the 3 smallest each time, after adding dummy zero count leaves so that (n - 1) divides evenly by 2.
• Is Huffman always the best compression? It is the best when each letter gets its own whole number of bits. Arithmetic coding and methods that look at groups of letters can do better.

Remember this

Grown-up words: the cards are tree nodes, the pile that always hands you the smallest card is a min heap (priority queue), the knocks are prefix free codes, and the sum of count * code length is the weighted path length that Huffman's algorithm makes as small as possible.