THE FOLD / CHEAT / THE SHORTCUT / THE GOLOMB RICE
THE GOLOMB RICE
a tuned coder is a prediction nobody checks again
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Golomb–Rice coding spends a value in two parts: the high bits in unary, the low k in binary. Choose k to match the distribution and it is near-optimal. Choose it badly and it is catastrophic.
LIT verified live. 20,000 geometric values with a mean of 16, swept across every k from 0 to 8. The best is k=3 at 5.515 bits per value; theory predicts
LIT verified live. 20,000 geometric values with a mean of 16, swept across every k from 0 to 8. The best is k=3 at 5.515 bits per value; theory predicts
log₂(mean) = 4, and the measured optimum is within one. At k=0 the same data costs 16.297 bits — a 2.96× penalty for one wrong parameter on identical input.2 HOW IT WAS WEAVED · AI + HUMAN
Golomb’s 1966 code is optimal for geometric sources; Rice’s power-of-two variant is what FLAC and lossless image formats actually use.
AVAN (AI) swept every parameter and compared the winner to the prediction, rather than coding at the predicted value and reporting that it worked. Those are different claims: the second assumes the theory, the first tests it. The measured optimum landing within one of
AVAN (AI) swept every parameter and compared the winner to the prediction, rather than coding at the predicted value and reporting that it worked. Those are different claims: the second assumes the theory, the first tests it. The measured optimum landing within one of
log₂(mean) is the result, and the 2.95× penalty is what the theory is worth.3 ONE DIMENSION
Every k, and the cost of each.
4 TWO DIMENSIONS · INTERACTIVE
Pick a k, or change the source underneath it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: unary on top, binary underneath.
AVAN’s addition (the inverse-companion): the forward reading is that Golomb–Rice is near-optimal when tuned. The inverse is that the tuning is a claim about data you have not seen yet. k is fixed when the format is written and the source is free to change afterwards — so the 2.95× is not a penalty for incompetence but the standing risk of every parameter baked into a codec. Read backwards, a tuned coder is a prediction, and its compression ratio is the score on a forecast nobody checks again.
LIT 20,000 geometric values with a mean of 16 swept across every k from 0 to 8 give a best of k=3 at 5.515 bits per value against a theoretical log2(mean) of 4 - the measured optimum within one of the prediction - while k=0 costs 16.297 bits on the same data, a 2.96x penalty for one wrong parameter
FIG Golomb's 1966 code is optimal for geometric sources; Rice's power-of-two variant is what FLAC and lossless image formats actually use. AVAN swept every parameter and compared the winner to the prediction, rather than coding at the predicted value and reporting that it worked. Those are different claims: the second assumes the theory, the first tests it.
FIG Golomb's 1966 code is optimal for geometric sources; Rice's power-of-two variant is what FLAC and lossless image formats actually use. AVAN swept every parameter and compared the winner to the prediction, rather than coding at the predicted value and reporting that it worked. Those are different claims: the second assumes the theory, the first tests it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SHORTCUT · David Lee Wise (ROOT0), with AVAN