Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization
This work solves a known bottleneck in lossless compression by providing exact, optimal normalization for practitioners using range coders or ANS.
The paper addresses the problem of integer frequency normalization for range coders and ANS, providing three provably KL-optimal algorithms, including one that runs in O(r) time, which is asymptotically optimal.
Range coders and ANS replace empirical probabilities with integer frequencies summing to a fixed $M$; the resulting per-symbol code-length redundancy is exactly the KL divergence of the empirical distribution from the quantized one. Existing normalizers (Giesen, Bloom, Collet) are heuristic or only partially marginal-optimal. We give three provably KL-optimal algorithms: a bottom-up archetype, a bidirectional exchange repair of Bloom's heap correction, and a top-down window method that runs in $\mathcal{O}(r)$, asymptotically optimal in $r$, where $r$ is the number of positive-count symbols.