Universal coding method achieves near optimal data compression rates
Universal coding with the exhaustive peres transform
Information Theory
Summary
Data compression works best when it can extract all the randomness from a source without losing information. The authors complete and refine a coding procedure that fully uses all input bits to produce perfectly fair (random) bits and a small residue carrying source information. For simple sources like biased coin flips, their method compresses close to the theoretical limit by separating random and structured parts efficiently. They also adapt this approach for more complex, memory-dependent data using the Burrows–Wheeler transform, building codes that adjust to different patterns automatically.
What this means in practice
- •For data compression engineers: Build compression algorithms that nearly reach entropy limits by separating random and residual bits efficiently for skewed and memory-dependent sources.
- •For storage system developers: Improve space efficiency in storing large datasets by incorporating universal codes that adapt to source statistics and reduce overhead across diverse input sizes.
Authors
Aur{é}lien Garivier
Abstract
Peres's iteration of von Neumann's procedure is completed into a bijection of $\bits^N$: the recursion runs to exhaustion, nothing is discarded, and every input splits into fair bits and residual bits. The residual strings form a complete prefix code that determines the number of ones of the input, so the fair bits are exactly uniform given the residual for every exchangeable law. For a Bernoulli source the likelihood factorises exactly, in decoding order, into a factor $1/2$ per fair bit and a Bernoulli factor per residual bit, with biases obtained by iterating two explicit maps. The number of fair bits per input symbol tends to the entropy almost surely, also on larger alphabets. Code B stores the fair bits and codes only the residual with an arithmetic coder; its ideal length is that of the two-part code, at most $\log\_2(N+1)+1$ bits above $-\log\_2\Pr\_θ(s)$ for every input $s$ and bias $θ$. Code C uses Rice codes instead. In experiments up to $N=2^{20}$ its mean regret stays below $200$ bits, where a Rice coder on the raw input loses a fixed fraction of the entropy on skewed sources. For sources with memory, the Burrows--Wheeler transform of the reversed string arranges all context orders in one tree of intervals; coding the leaves of a pruned tree as Bernoulli strings adapts to every Markov order up to its depth, and on suffix-closed trees the leaf weights determine the split points.