huffman trees

SICP §2.3.4 builds a Huffman tree by keeping a list of trees ordered by weight (make-leaf-set, adjoin-set) and repeatedly merging the two lightest trees into one, re-inserting the merge in order (successive-merge), until a single tree remains. Encoding walks root-to-leaf, at each branch testing whether the next symbol is a member of the left branch's symbol set (encode-symbol, ex. 2.68); decoding walks the bits back down, restarting at the root each time a leaf is reached. Every comparison, insertion, merge, emitted bit, and decoded symbol below is a recorded step – move the timeline to any step, or edit the weights, message, or toggles and the whole trace recomputes.

A merge-rule toggle swaps the real Huffman rule (merge the two lightest trees) for a deliberately suboptimal one (merge the two heaviest, "for contrast") so the cost table below can show, concretely, that Huffman's choice is not arbitrary. A tie-order toggle controls where a newly adjoined tree lands among equal-weight trees – SICP's own adjoin-set puts it after existing ties; putting it before produces a different but equally optimal tree, which the cost table also verifies (same total weighted length, sometimes different per-symbol lengths). The cost table compares four codes for the same weights – Huffman ties-after, Huffman ties-before, merge-two-heaviest, and fixed-length – against the Shannon entropy lower bound, both per unit of weight and applied to the message's own symbol frequencies.

The pure trace/replay model lives in wal-sh.tools.huffman-trees.core (host-neutral .cljc, tested on the JVM with test.check: encode then decode reproduces the original message, no code in the table is ever a prefix of another, Huffman's weighted length never exceeds fixed-length's, both tie orders agree on total length, and merging the two heaviest is never better than real Huffman). The browser adapter is wal-sh.tools.huffman-trees.browser. Build: gmake tools-cljs; debug in isolation: gmake dev-tool TOOL=huffman-trees.