I'm reading a paper entitled "Succincter" which discusses a compression scheme that involves encoding a value as a sequence of $M$ bits, along with a "spillover" value which can be recursively encoded.

The details of the encoding scheme are not really relevant for the purpose of this question. Rather, I am specifically interested in asking for some clarification regarding this following excerpt from the paper:

Assume we want to represent a value from a set $X$ . Any representation in a sequence of memory bits will use at least $\lceil \log_2|X| \rceil$ bits in the worst case, so it will have a redundancy of almost one bit if $|X|$ is not close to a power of two.

Okay, so I get the meaning here - the author is saying that if we want to represent any arbitrary element $e \in X$, then in the worst case we need at least $\lceil \log_2|X|\rceil$ bits. But why is it $\log_2|X|$ and not $\log_2 \max X$?

For example, if I have a set $X = \{1, 2, 1e10 \}$, which contains 3 elements, I need at least $\lceil \log_2 1e10\rceil$ bits in the worst case, not $\lceil \log_2 3\rceil$ bits.

Or am I somehow misinterpreting the statement? The only thing I can assume here is that the author is implicitly assuming some kind of mapping table over an alphabet $\Sigma$ which we use to map each element in the set to an increasing value starting at 0. But this is never explicitly stated, and would seem to be a large assumption.

So am I missing something here?


You can encode the set $X$ using only two bits: use $00$ to encode $1$, $01$ to encode $2$, and $10$ to encode $1e10$.

More generally, the exact identity of the elements of $X$ are not important. You can encode letters of the alphabet or even words, if you want.

You haven't defined what an encoding scheme is, so let me assume that it is a uniquely decodable code. Any uniquely decodable code for $X$ must contain a codeword whose length is at least $\log_2 |X|$ (and so at least $\lceil \log_2 |X| \rceil$). This follows from McMillan's inequality.


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.