Huffman Coding — a dart

THE TECHNIQUE count · merge two smallest · read the paths

Count how often each symbol appears. Put every symbol in a priority queue keyed by frequency. Then repeatedly pull the two least-frequent nodes and merge them under a new parent whose weight is their sum — the rare symbols sink deep, the common ones stay shallow. When one node remains, the path from the root to each leaf (0 = left, 1 = right) is that symbol’s code. No code is a prefix of another, so the stream decodes with no separators. live demo

while queue has > 1 node: a = pop_min(queue) // two lowest b = pop_min(queue) // frequencies push(queue, node(a+b, a, b)) // merge under a new parent root = pop(queue) // paths to leaves = the codes

HISTORY & CREDIT credit where it is due

The credit here is clean — no famous name stole it. But there is a twist most people miss: the method is named for a student who beat his own professor. cited

1948 · Claude Shannon founds information theory; with Robert Fano comes Shannon–Fano coding — a top-down code split. Good, but not always optimal.
1951 · at MIT, Robert Fano sets his information-theory class a term paper: find the most efficient binary code. A student named David A. Huffman struggles, nearly quits to study for the final…
1951 · …then sees it: build the tree bottom-up, merging the two rarest symbols first. He proves it optimal — the very thing Shannon and Fano had not managed.
1952 · David A. Huffman publishes “A Method for the Construction of Minimum-Redundancy Codes” in the Proceedings of the IRE. The real, sole inventor — and the code carries his name to this day.

The honest note: bottom-up Huffman is provably optimal symbol-by-symbol for a known distribution — but it is not the last word in compression. Arithmetic coding (1970s–80s) and dictionary methods (LZ77/LZ78, 1977–78) beat it when symbols are not independent. Huffman is optimal within its own rules, and those rules are narrower than “best possible compression.” open / still-refined

RECOMMEND FOR I-13 what the galaxy should learn

Huffman needs three things I-13 refuses to have: symbols/bytes (a string or char type), a priority queue, and a tree. I-13 has none of them — its only value is an f64 scalar, and it has no aggregate data structure at all. I asked the real compiler; it cannot even lex a string. Proven, not asserted:

i13 check str.i13 => str.i13:1:8 E0001 unexpected character `"` (no string type) i13 check char.i13 => char.i13:1:8 E0001 unexpected character `'` (no char type) i13 check arr.i13 => arr.i13:1:16 E0001 unexpected character `[` (no array/aggregate) i13 check mod.i13 => mod.i13:2:10 E0001 unexpected character `%` (BinOp is + - * / only) i13 run run2.i13 => out = 2.6666666666666665 (f64 scalar, nothing else)

The lexer rejects ", ' and [ as unexpected characters — there is no token, let alone a type, for a byte or a collection. So the whole of Huffman — the alphabet, the queue, the tree — is off the map.

Recommend: the biggest honest gap is that I-13 has no aggregate/data-structure story whatsoever. The cheapest first step toward one is a minimal byte or char scalar (a symbol you could count) and, above it, one indexable sequence primitive. Frequencies, priority queues and trees can all be built on those two — but none can be built on an f64 alone.
Tradeoff (honest): this is expensive against I-13’s identity. The alphabet was counted, not designed — 12 verbs + I — and adding a string/collection type is a whole new plane of syntax, not a free BinOp discriminant the way % or a bit-op would be. A collection type also breaks the “every value is one f64” invariant the single-pass validator leans on. So the honest verdict is: an aggregate story is I-13’s single largest capability gap — and quite possibly out of scope by design. A counted-alphabet, scalar-only language may be right to leave compression to a host and stay a language about control and arithmetic, not data. Name the gap; do not necessarily fill it.