What is the most efficient way to store a numeric range?

Question

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 are 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?

Answer 1

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.

Answer 2

For such small number of bits, it is infeasible to save 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.

Answer 3

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 45-74 appears about 1/4 of the time. You may say that the sequence 00 corresponds to 45-74. To encode the range 45-74, you output “00” and stop there.

Let’s also suppose that the ranges 99-100 and 140-155 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 45-74.

00: 45-74
010: 99-100
101: 140-155

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 them 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.

Answer 4

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.

Answer 5

There's a similar answer, but to achieve optimal compression, you need:

1. An optimal entropy encoding method (read up on Arithmetic coding and the essentially equivalent (same compression ratio, a bit faster but also harder to grasp) ANS)
2. As much information as possible about the distribution of the data. Crucially, this does not just involve "guessing" how often one number may appear, but you can often rule out certain possibilities for sure. For example, you can rule out intervals of negative size, and possibly 0 size, depending on how you define a valid interval. If you have multiple intervals to encode at once, you could sort them e.g. in order of decreasing width, or increasing start/end value, and rule out a whole lot of values (e.g. if you guarantee an order by decreasing width, the previous interval had a width of 100, and the starting value for the next one is 47, you only need to consider the possibilities up to 147 for end values).

Importantly, number 2 means you want to encode things in such a way that the most informative values (per bit encoded) come first. For example, while I suggested encoding a sorted list "as-is", it would usually be smarter to encode it as a "binary tree" -- i.e. if they're sorted by width, and you have len elements, start by encoding element len/2. Say it had width w. Now you know all elements before it have width somewhere in [0, w], and all elements after it have width somewhere in [w, max val you accept]. Repeat recursively (subdividing each half list again in half, etc) until you've covered len elements (unless it's fixed, you'll want to encode len first so you don't need to bother with ending tokens). If "max val you accept" is really open, it may be smart to first encode the highest value that actually appears in your data, i.e. the last element, and then do the binary partitioning. Again, whatever is most informative per bit first.

Also, if you're encoding the width of the interval first, and you know the max possible value you're dealing with, obviously you can rule out all starting values that would make it overflow... you get the idea. Transform and order your data in such a way that you can infer as much as possible about the rest of the data as you decode it, and an optimal entropy encoding algorithm will make sure you're not wasting bits encoding info you "already know".