Mdthbs

This question is about how many bits are required to store a range. Or put another way, for a given number of bits, what is the maximum range that can be stored and how?

Imagine we want to store a sub-range within the range 0-255.

So for example, 45-74.

We can store the example above as two unsigned bytes, but it strikes me that there must be some redundancy of information there. We know that the second value is larger than the first, so in the case that the first value is large fewer bits is required for the second value and in the case that the second value is large fewer bits are required for the first.

I suspect that any compression technique would yield a marginal result, so it may be a better question to ask "what is the maximum range that could be stored in one byte?". This should be larger than what is achievable by storing the two numbers separately.

Are there any standard algorithms for doing this kind of thing?

Just count the number of possible ranges. There are 256 ranges with lower bound 0 (0-0, 0-1, ... 0-254, 0-255), 255 ranges with lower bound 1, ... and finally 1 range with lower bound 255 (255-255). So the total number is (256 + 255 + ... + 1) = 257 * 128 = 32,896. As this is slightly higher than 2¹⁵ = 32,768, you'll still need at least 16 bits (2 bytes) to store this information.

In general, for numbers from 0 up to n-1, the number of possible ranges is n*(n+1)/2. This is less than 256 if n is 22 or less: n = 22 gives 22*23/2 = 253 possibilities. So one byte suffices for sub-ranges of 0-21.

Another way to look at the problem is the following: storing a pair of integers in the range 0 to n-1 is almost the same as storing a subrange of 0-(n-1) plus a single bit which determines if the first number is lower or higher than the second one. (The difference comes from the case when both integers are equal, but this chance becomes increasingly smaller as n grows larger.) That's why you can only save about a single bit with this technique, and probably the main reason why it is rarely used.

For such small number of bits, it is infeasible to safe many bits as Glorfindel has pointed out.
However, if the domain you are using has a few more bits, you can achieve significant savings for the average case by encoding ranges with the start value and a delta.

Lets assume the domain is the integers, so 32 bits. With the naive approach, you need 64 bits (start, end) to store a range.

If we switch to an encoding of (start, delta), we can construct the end of the range from that. We know that in the worst case, the start is 0 and the delta has 32 bits.

2^5 is 32, so we encode the length of the delta in five bits (no zero length, always add 1), and the encoding becomes (start, length, delta). In the worst case, this costs 32*2 + 5 bits, so 69 bits. So in the worst case, if all ranges are long, this is worse then the naive encoding.

In the best case, it costs 32 + 5 + 1 = 38 bits.

This means if you have to encode a lot of ranges, and those ranges each only cover small part of your domain, you end up using less space on average using this encoding. It doesn't matter how the starts are distributed, since the start will always take 32 bits, but it does matter how the lengths of the ranges are distributed. If the more small lengths you have, the better the compression, the more ranges you have that cover the whole length of the domain, the worse this encoding will get.

However, if you have lots of ranges grouped around similar start points, (for example because you get values from a sensor), you can achieve even bigger savings. You can apply the same technique to the start value and use a bias to offset the start value.

Lets say you have 10000 ranges. The ranges are grouped around a certain value. You encode the bias with 32 bits.

Using the naive approach, you would need 32*2 * 10 000 = 640 000 bits to store all those ranges.

Encoding the bias takes 32 bits, and encoding each range takes in the best case then 5 + 1 + 5 + 1 = 12 bits, for a total of 120 000 + 32 = 120 032 bits.
In the worst case, you need 5 + 32 + 5 + 32 bits, thus 74 bits, for a total of 740 032 bits.

This means, for 10 000 values on a domain that takes 32 bits to encode, we get

• 120 032 bits with the smart delta-encoding in the best case


• 640 000 bits with the naive start, end encoding, always (no best or worst case)


• 740 032 bits with the smart delta encoding in the worst case

If you take the naive encoding as baseline, that means either savings of up to 81.25% or up to 15.625% more cost.

Depending on how your values are distributed, those savings are significant. Know your business domain! Know what you want to encode.

As an extension, you can also change the bias. If you analyse the data and identify groups of values, you can sort the data into buckets and encode each of those buckets separately, with its own bias. This means you can apply this technique not only to ranges that are grouped around a single start value, but also to ranges that are grouped around multiple values.

If your start points are distributed equally, this encoding doesn't really work that well.

This encoding is obviously extremely bad to index. You can not simply read the x-th value. It can pretty much only be read sequentially. Which is appropriate in some situations, e.g. streaming over the network or bulk storage (e.g. on tape or HDD).

Evaluating the data, grouping it and choosing the correct bias can be substantial work and might require some fine-tuning for optimal results.

To expand on the answer from @Glorfindel:

As n → ∞, (n - 1) → n. Thus, Ω(ranges) → n² / 2 and log(Ω(ranges)) → (2n - 1). Since the naive encoding takes 2n bits, the asymptotic maximal compression only saves 1 bit.

This kind of problem is the subject of Claude Shannon’s seminal paper, A Mathematical Theory of Communication, which introduced the word “bit” and more or less invented data compression.

The general idea is that the number of bits used to encode a range is inversely proportional to the probability of that range occurring. For example, suppose the range 150-160 appears about 1/4 of the time. You may say that the sequence 00 corresponds to 150-160. To encode the range 150-160, you output “00” and stop there.

Let’s also suppose that the ranges 140-155 and 145-160 each appear about 1/8 of the time. You can encode each of them with a 3 bit sequence. Any 3 bits will do as long as they don’t start with “00”, which has already been reserved for the range 140-150.

00: 140-150

010: 140-155

101: 145-160

You can continue in this manner until every possible range has an encoding. The least probable range may need over 100 bits. But that’s okay because it rarely appears.

There are algorithms to find the optimal coding. I won’t try to explain it here, but you can find more by visiting the link above or searching for “Information Theory”, “Shannon-fano coding”, or “Huffman coding”.

As others have pointed out, it’s probably better to store the start number and the difference between the start and end number. You should use one coding for the start and another for the difference, as they have different probability distributions (and I’m guessing the latter is more redundant). As polygnome suggested, the best algorithm depends on your domain.