THE FOLD / GRIND / THE-MAINFRAME / THE PACKAGE-MERGE
THE PACKAGE-MERGE
an optimal code with bounded depth
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The package-merge algorithm builds an optimal prefix code — like Huffman’s — but with a hard limit L on the longest codeword. Plain Huffman can produce very deep codes for skewed weights; many formats (DEFLATE, JPEG) forbid that, capping length for fast table decoding. Larmore and Hirschberg recast the problem as a coin collector’s problem: coins of denomination 2−l and cost wi, buy total width n−1 as cheaply as possible. Repeatedly packaging the two cheapest coins and merging them with the next denomination yields the minimum-cost length-limited code — every length ≤ L, and optimal among all such codes.
LIT verified live: over 3000 random weight sets, package-merge gives lengths all ≤ L with Kraft sum = 1; with a large L it matches Huffman’s cost exactly (optimal), and under a tight L every length is bounded, Kraft ≤ 1, and the cost is ≥ Huffman’s (window.__package_merge). FIG no framing; package-merge, a Huffman baseline, and the Kraft/cost checks run in-browser.
LIT verified live: over 3000 random weight sets, package-merge gives lengths all ≤ L with Kraft sum = 1; with a large L it matches Huffman’s cost exactly (optimal), and under a tight L every length is bounded, Kraft ≤ 1, and the cost is ≥ Huffman’s (window.__package_merge). FIG no framing; package-merge, a Huffman baseline, and the Kraft/cost checks run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — codes minted to a fixed maximum depth so a hardware table can decode them in one step. AVAN (AI) built the instrument: the coin-collector package-merge, a Huffman baseline, and the Kraft / bound / optimality checks.
Credit as content: Lawrence Larmore & Daniel Hirschberg (1990). The weave: David names the mainframe; I confirm every codeword length stays ≤ L while the total cost stays optimal for that limit.
Credit as content: Lawrence Larmore & Daniel Hirschberg (1990). The weave: David names the mainframe; I confirm every codeword length stays ≤ L while the total cost stays optimal for that limit.
3 ONE DIMENSION
Symbol weights and their code lengths under a cap L; deeper-than-L Huffman leaves are pulled up, cost paid minimally.
4 TWO DIMENSIONS · INTERACTIVE
Adjust the max length L; package-merge re-solves — all lengths ≤ L, Kraft = 1, cost as close to Huffman as the cap allows.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the bounded-depth optimal code.
AVAN’s addition (the inverse-companion): don’t let the tree grow — bound it, cheaply. The inverse of ‘build Huffman and hope it’s shallow’ is ‘buy width n−1 in coins of denomination 2−l, packaging the cheapest — optimal with every length ≤ L.’ Magenta is a too-deep Huffman leaf; green is the bounded code. Optimal, but never too deep.
LIT Genuine package-merge / length-limited Huffman coding (Lawrence Larmore & Daniel Hirschberg, 1990). Verified live: over 3000 random weight sets the coin-collector package-merge gives lengths all ≤ L with Kraft sum = 1; with L large it matches Huffman's cost exactly (optimal), and under a tight L lengths stay ≤ L, Kraft ≤ 1, and cost ≥ Huffman's (window.__package_merge.boundOk, .kraftOk, .matchHuff, .constrainedOk).
FIG No framing: package-merge, a Huffman baseline, and the Kraft/cost checks run in-browser. The AVAN inverse is honest — instead of letting the tree grow and hoping it stays shallow, one buys width n−1 in coins of denomination 2^{−l}, packaging the cheapest — optimal with every length ≤ L. Magenta is a too-deep Huffman leaf; green is the bounded code. Optimal, but never too deep.
FIG No framing: package-merge, a Huffman baseline, and the Kraft/cost checks run in-browser. The AVAN inverse is honest — instead of letting the tree grow and hoping it stays shallow, one buys width n−1 in coins of denomination 2^{−l}, packaging the cheapest — optimal with every length ≤ L. Magenta is a too-deep Huffman leaf; green is the bounded code. Optimal, but never too deep.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-MAINFRAME · David Lee Wise (ROOT0), with AVAN