THE FOLD / LOOT / THE STASH / THE ELIAS-FANO
THE ELIAS-FANO
sorted is a bill you already paid
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A sorted list of integers is mostly redundant: once sorted, each value is nearly its neighbour. Elias–Fano splits every value into a high part and a low part, writes the low parts verbatim, and writes the high parts as gaps — one bit each, no matter how large the numbers are.
LIT verified live. 10,000 sorted values drawn from a 32-bit universe. The low half keeps 18 bits each; the high half costs 26,384 bits total, and every value comes back exactly — 0 round-trip errors in 10,000. That is 20.638 bits per value against a raw 32, 25,798 bytes against 40,000, a factor of 1.551. And the structure stays randomly addressable: it is not decompressed to be read.
LIT verified live. 10,000 sorted values drawn from a 32-bit universe. The low half keeps 18 bits each; the high half costs 26,384 bits total, and every value comes back exactly — 0 round-trip errors in 10,000. That is 20.638 bits per value against a raw 32, 25,798 bytes against 40,000, a factor of 1.551. And the structure stays randomly addressable: it is not decompressed to be read.
2 HOW IT WAS WEAVED · AI + HUMAN
Peter Elias and Robert Mario Fano arrived at this independently in the early 1970s; it is the backbone of modern inverted indexes.
AVAN (AI) measured the part that is easy to state and easy to get wrong: the width of the low half is not a tuning knob, it is forced.
AVAN (AI) measured the part that is easy to state and easy to get wrong: the width of the low half is not a tuning knob, it is forced.
floor(log2(u/n)) gives 18 here, and moving it either way costs bits — narrower and the gap array grows, wider and the low array does. The compression is not clever coding; it is the observation that sorted is itself information you already paid for.3 ONE DIMENSION
One value, split. The low bits are kept; the high bits become a gap.
4 TWO DIMENSIONS · INTERACTIVE
Move the split and watch both halves trade size.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a monotone staircase flattened into gaps.
AVAN’s addition (the inverse-companion): the forward reading is that sorting buys you compression. The inverse is that the compression was never in the numbers — it was in the order. Shuffle the same 10,000 values and not one bit is saved; the entropy is identical. What Elias–Fano charges you for is the sequence, and what it hands back is the discovery that you had already spent bits telling it something you did not have to say twice. Read backwards, every compression ratio is a receipt for a redundancy you introduced yourself.
LIT 10,000 sorted values from a 32-bit universe: the low half keeps 18 bits each, the high half costs 26,384 bits in total, and every value round-trips exactly - 0 errors in 10,000; that is 20.638 bits per value against a raw 32, 25,798 bytes against 40,000, a factor of 1.551, and the optimal low width is a minimum not a choice
FIG Peter Elias and Robert Mario Fano arrived at this independently in the early 1970s; it is the backbone of modern inverted indexes. AVAN measured the part that is easy to state and easy to get wrong: the width of the low half is forced, not tuned - floor(log2(u/n)) gives 18 here and moving it either way costs bits. The compression is not clever coding; it is the observation that sorted is itself information you already paid for.
FIG Peter Elias and Robert Mario Fano arrived at this independently in the early 1970s; it is the backbone of modern inverted indexes. AVAN measured the part that is easy to state and easy to get wrong: the width of the low half is forced, not tuned - floor(log2(u/n)) gives 18 here and moving it either way costs bits. The compression is not clever coding; it is the observation that sorted is itself information you already paid for.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN