bhylu.com

Advertisements

DSA Huffman Coding

Huffman coding repeatedly combines the least frequent symbols into a binary code tree. Prefix-free codes let a decoder recognize a symbol without a separator between every code.

How it works

The fixture counts symbols in an original orchard label, uses a ticket to break heap ties and builds codes from the resulting tree. It explicitly defines an empty alphabet and a single-symbol alphabet. The decoder walks the actual tree and rejects non-binary or incomplete codes. This teaches a coding method, not a complete file format: tree metadata, byte packing, original lengths and integrity information still affect a real compressed representation.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as huffman-coding.py and run python huffman-coding.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

huffman-coding.py
Try in playground

from collections import Counter
from itertools import count
import heapq

def huffman_codes(text):
    ticket = count()
    heap = [(frequency, next(ticket), symbol) for symbol, frequency in sorted(Counter(text).items())]
    heapq.heapify(heap)
    if not heap:
        return {}, None
    while len(heap) > 1:
        first_weight, _, first = heapq.heappop(heap)
        second_weight, _, second = heapq.heappop(heap)
        heapq.heappush(heap, (first_weight + second_weight, next(ticket), (first, second)))
    tree = heap[0][2]
    codes = {}

    def walk(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or "0"
        else:
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")

    walk(tree, "")
    return codes, tree

def decode_bits(bits, tree):
    if tree is None:
        if bits:
            raise ValueError("No code tree")
        return ""
    if isinstance(tree, str):
        if any(bit != "0" for bit in bits):
            raise ValueError("Invalid single-symbol code")
        return tree * len(bits)
    result, node = [], tree
    for bit in bits:
        if bit not in "01":
            raise ValueError("Binary digits required")
        node = node[int(bit)]
        if isinstance(node, str):
            result.append(node)
            node = tree
    if node is not tree:
        raise ValueError("Incomplete code")
    return "".join(result)

text = "oak oak"
codes, tree = huffman_codes(text)
bits = "".join(codes[symbol] for symbol in text)
print(decode_bits(bits, tree) == text)
print(len(bits))
single_codes, single_tree = huffman_codes("ooo")
print(decode_bits("000", single_tree))

Expected result

True
14
ooo

The text round-trips through fourteen logical code bits, and the single-symbol convention is handled deliberately. That bit count excludes the code tree and transport framing, so it is not a truthful standalone file-compression ratio. Tests check prefix-freedom and malformed streams separately.

Time, space and assumptions

Frequency counting is O(N), heap combination O(K log K) for K symbols. Code generation depends on tree height h and stored code lengths; decoding B bits is O(B) plus output. A highly skewed recursive code walk also needs bounded depth.

Consult the Python 3.12 standard-library reference for container and language contracts; an example result is not a proof of every possible input or real-world performance.

Advertisements