Prefix Codes for Power Laws

Abstract — In prefix coding over an infinite alphabet, methods that consider specific distributions generally consider those that decline more quickly than a power law (e.g., a geometric distribution for Golomb coding). Particular power-law distri-butions, however, model many random variables encountered in practice. Estimates of expected number of bits per input symbol approximate compression performance of such random variables and can thus be used in comparing such methods. This paper introduces a family of prefix codes with an eye towards near-optimal coding of known distributions, precisely estimating compression performance for well-known probability distributions using these new codes and using previously known prefix codes. One application of these near-optimal codes is an improved representation of rational numbers. I