2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Look for prefix code, prefix-free code, uniquely decodable code, or variable-length code. $\endgroup$ – Yuval Filmus Mar 25 '20 at 16:12
  • $\begingroup$ You are interested in the reverse direction of Kraft's inequality. $\endgroup$ – Yuval Filmus Mar 25 '20 at 16:13
3
$\begingroup$

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.

$\endgroup$
1
2
$\begingroup$

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$.
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Costantino Grana Mar 25 '20 at 18:32
-2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Costantino Grana Dec 11 '20 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.