Name of binary encoding scheme for integer numbers

I once found on Wikipedia a nice technique for encoding $$k \in (2^{n-1}, 2^n)$$ uniformly distributed integer numbers with less then $$\log_2n$$ average bits/symbol, thanks to a simple to compute variable length code. Basically it used $$\log_2n$$ for some symbols and $$\log_2n - 1$$ for some others.

Unfortunately all my Googling has failed me. I recall something similar to "variable length binary", but I keep ending on VLQ which are a different beast. Since I know your memory better than mine, can you help me?

• Look for prefix code, prefix-free code, uniquely decodable code, or variable-length code. Commented Mar 25, 2020 at 16:12
• You are interested in the reverse direction of Kraft's inequality. Commented Mar 25, 2020 at 16:13

The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API

Another mention can be found in the ACM ICPC 2011–2012, Northeastern European Regional Contest, November 27, 2011.

• An answer at stackoverflow.com/questions/8885703/… calls this "logarithm approximation". Alas, I can't find an original source for that synonym either. Commented Dec 10, 2020 at 16:47

Suppose $$k = 2^{n-1} + t$$, where $$0 \leq t < 2^{n-1}$$. Use the following to encode $$z \in \{0,\ldots,k-1\}$$:

• If $$z < 2^{n-1}-t$$ then encode $$z$$ as its own $$(n-1)$$-bit encoding.
• Otherwise, write $$z = 2^{n-1}-t + 2\delta+\epsilon$$, where $$\delta \in \{0,\ldots,t-1\}$$ and $$\epsilon \in \{0,1\}$$. Encode $$z$$ at the $$(n-1)$$-bit encoding of $$2^{n-1}-t+\delta$$ followed by $$\epsilon$$.

Here is an example. Let $$k = 11 = 2^3+3$$. The encoding is as follows:

• $$0 \to 000$$.
• $$1 \to 001$$.
• $$2 \to 010$$.
• $$3 \to 011$$.
• $$4 \to 100$$.
• $$5 \to 1010$$.
• $$6 \to 1011$$.
• $$7 \to 1100$$.
• $$8 \to 1101$$.
• $$9 \to 1110$$.
• $$10 \to 1111$$.
• This is exactly the correct reasoning. I was also missing the name of this version of the encoding. It's Truncated binary encoding, according to Wikipedia. Commented Mar 25, 2020 at 18:32

Usually (a, b) is an open interval, excluding a and b, and [a, b] is a closed interval, including a and b. So $$(2^{n-1}, 2^n)$$ is the set of numbers from $$2^{n-1} + 1$$ to $$2^n-1$$.

To encode, subtract $$2^{n-1}+1$$ from a number x, leaving $$0 ≤ x < 2^{n-1}-1$$. There are $$2^{n-1}-1$$ possible numbers, each with same probability, so you can use Huffman coding for just under n-1 bits on average. To be precise, you have $$2^{n-1} - 2$$ numbers encoded in n-1 bits, and one number encoded in n-2 bits, for an average of $$n-1-1/(2^{n-1}-1)$$ bits.

You could use arithmetic coding, which would be a tiny, tiny bit shorter on average with a very good implementation, but would be much much more complicated. Not worth it in this case; possibly worth it if you had say $$1.5 \cdot 2^n$$ different numbers to store and storage size is very important to you.

• I think you didn't understand the question correctly. There are $k$ uniformly distributed numbers. These numbers are from $0$ to $k-1$. You cannot use entropy coding, because all of them have the same probability. Commented Dec 11, 2020 at 16:18