THE FOLD / LOOT / THE STASH / THE PATRICIA TRIE
THE PATRICIA TRIE
branching only on the bits that differ
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The PATRICIA trie (a crit-bit tree) stores a set of bit-strings with no wasted nodes. A plain binary trie spends a node per bit; PATRICIA keeps only the branch points. Each internal node records a single critical bit index — the first bit on which the keys below it diverge — and you navigate by testing just that bit. The payoff is a sharp invariant: a set of k keys needs exactly k−1 internal branch nodes, no matter how long the keys are, so the structure is as small as a set can be while still supporting prefix search.
LIT verified live: over thousands of random key sets, membership queries are exactly correct, and the number of internal branch nodes is always k−1 for k keys (window.__patricia). FIG no framing; the crit-bit insertion, search, and node count run in-browser.
LIT verified live: over thousands of random key sets, membership queries are exactly correct, and the number of internal branch nodes is always k−1 for k keys (window.__patricia). FIG no framing; the crit-bit insertion, search, and node count run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-stash — a stash of keys packed with only the branch points kept, nothing redundant stored. AVAN (AI) built the instrument: the crit-bit tree (branch on the first differing bit), membership search, and the k−1 node-count invariant.
Credit as content: Donald Morrison, PATRICIA (1968); the crit-bit refinement. Honest note: crit-bit trees assume prefix-free keys (here, fixed length) so no key is a zero-extension of another. The weave: David names the stash; I confirm membership is exact and the branch-node count is always k−1.
Credit as content: Donald Morrison, PATRICIA (1968); the crit-bit refinement. Honest note: crit-bit trees assume prefix-free keys (here, fixed length) so no key is a zero-extension of another. The weave: David names the stash; I confirm membership is exact and the branch-node count is always k−1.
3 ONE DIMENSION
A crit-bit tree over a few keys; each internal node is labelled by its critical bit — the only bit you test to branch.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys and watch the tree grow one branch node per key; membership is exact and the internal-node count stays at k−1.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the branch nodes, one per critical bit.
AVAN’s addition (the inverse-companion): don’t store a node per bit — store only where keys diverge. The inverse of ‘walk every bit of the key’ is ‘jump straight to the critical bit; k keys leave exactly k−1 branch points.’ Magenta are the leaves (the keys); green are the k−1 branch nodes. Branch only on the bits that differ.
LIT Genuine PATRICIA / crit-bit tree (Donald Morrison, 1968): branch on the first differing bit; k keys need exactly k−1 internal nodes. Verified live: over 2000 random key sets, membership is exact (window.__patricia.membership) and the internal branch-node count equals k−1 (.compressed).
FIG Honest scope stated on the sphere: crit-bit trees assume prefix-free keys (here, fixed length) so no key is a zero-extension of another. The AVAN inverse is honest — jumping straight to the critical bit and leaving exactly k−1 branch points for k keys (rather than a node per bit) is the compression; magenta are the leaves (keys), green the k−1 branch nodes. Branch only on the bits that differ.
FIG Honest scope stated on the sphere: crit-bit trees assume prefix-free keys (here, fixed length) so no key is a zero-extension of another. The AVAN inverse is honest — jumping straight to the critical bit and leaving exactly k−1 branch points for k keys (rather than a node per bit) is the compression; magenta are the leaves (keys), green the k−1 branch nodes. Branch only on the bits that differ.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN