Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Huffman trees: assign prefix codes from symbol frequencies

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A Huffman code tree starts with one leaf per training symbol and repeatedly joins the two lowest-frequency roots. The merged node's weight is their sum. A left edge contributes zero and a right edge contributes one, so every leaf receives a codeword and no leaf code is a prefix of another. This model uses a binary heap to build a fixed codebook, then encodes only symbols present in that training alphabet. The decoder walks the retained tree and emits a symbol whenever it reaches a leaf. A one-symbol alphabet gets code zero so its encoded length remains explicit. The codebook is part of the decoding contract, not an optional afterthought.

Operational case

A codebook trained on dispatch dispatch urgent has fourteen distinct symbols. Encoding dispatch urgent yields 57 bits in this run, and the decoder restores the exact phrase. Equal-frequency symbols are resolved by a serial tie value, making the output reproducible without implying a unique Huffman bit assignment across all implementations. An unknown symbol cannot be encoded through this codebook. A trailing bit sequence that ends inside an internal node is incomplete and rejected; for a one-symbol alphabet, only zero is a valid code bit.

Working Python program

python
from collections import Counter
from heapq import heappop, heappush


class CodeNode:
    def __init__(self, symbol=None, left=None, right=None):
        self.symbol, self.left, self.right = symbol, left, right


class IncidentCodebook:
    def __init__(self, training_text):
        frequencies = Counter(training_text)
        if not frequencies:
            raise ValueError("training text must contain a symbol")
        heap = []
        serial = 0
        for symbol, count in sorted(frequencies.items()):
            heappush(heap, (count, serial, CodeNode(symbol=symbol)))
            serial += 1
        while len(heap) > 1:
            left_count, _, left = heappop(heap)
            right_count, _, right = heappop(heap)
            heappush(heap, (left_count + right_count, serial, CodeNode(left=left, right=right)))
            serial += 1
        self.root = heap[0][2]
        self.codes = {}

        def assign(node, bits):
            if node.symbol is not None:
                self.codes[node.symbol] = bits or "0"
                return
            assign(node.left, bits + "0")
            assign(node.right, bits + "1")

        assign(self.root, "")

    def encode(self, text):
        return "".join(self.codes[symbol] for symbol in text)

    def decode(self, bits):
        if any(bit not in "01" for bit in bits):
            raise ValueError("nonbinary input")
        if self.root.symbol is not None:
            if any(bit != "0" for bit in bits):
                raise ValueError("invalid one-symbol code")
            return self.root.symbol * len(bits)
        output, cursor = [], self.root
        for bit in bits:
            cursor = cursor.left if bit == "0" else cursor.right
            if cursor.symbol is not None:
                output.append(cursor.symbol)
                cursor = self.root
        if cursor is not self.root:
            raise ValueError("incomplete final codeword")
        return "".join(output)


if __name__ == "__main__":
    training = "dispatch dispatch urgent"
    book = IncidentCodebook(training)
    payload = "dispatch urgent"
    bits = book.encode(payload)
    print(len(book.codes), len(bits))
    print(book.decode(bits))

Output

Output
14 57
dispatch urgent

Time, space, and tradeoff

For A distinct symbols, frequency counting takes O(N) time on N training characters and heap construction takes O(A log A) in this direct implementation. Encoding and decoding visit O(B) code bits for encoded length B, while codebook and tree storage are O(A) nodes plus the stored code strings. The output in the example is a Python string of zero and one characters, not packed bits, and it excludes any header needed to transmit the tree. A canonical codebook and bit packing would change serialization details. A frequency change after publication requires a newly agreed codebook.

Common Mistakes

  • Do not assume the bitstream is decodable without the matching codebook.
  • Do not give the single-symbol alphabet an empty codeword.
  • Do not accept a stream ending in the middle of a codeword.
  • Do not compare Python text bits with packed file bytes as if they were equal storage.

Connected lessons

Compare its query and update boundary with LZ78 phrase tries: emit dictionary index and next symbol, Segment-tree stabbing indexes: list intervals active at one point, Condensation DAGs: compress directed cycles before path queries, then complete the structure audit and decision quiz.

data structures
trees-and-heaps
Storage details