Once in a while, we have to encode a series of values to memory or file, of which we know either very little about, distribution-wise, or are very clo

Harder, Better, Faster, Stronger

submited by

Style Pass

2021-07-02 16:00:02

Once in a while, we have to encode a series of values to memory or file, of which we know either very little about, distribution-wise, or are very close to being drawn from an uniform random variable: basically, they’re all equally likely to be drawn. This precludes the use of Huffman (or like) codes because the distribution is flat and Huffman code will afford no real compression despite the added complexity.

We do not want to use a fixed number of bits either because the number of possible values might be very far from the next power of two. For example say I have 11 different values. I could encode them on 4 bits each, but I would waste more than half a bit by doing so. Half a bit wasted for every code. Fortunately, there’s an easy, fast encoding that can help us achieve high efficiency: phase-in codes.

The first written reference to phase-in codes I could find is US Patent 4464650 (1984) where they are referred to as economy codes [1]. In [4], they are named as phase-in codes, and are briefly discussed but without reference to their inventor. Then they show up in the work of Yokoo [5], and of Acharya and Já Já [2,3], though I am sure they appear elsewhere with a different name.