<p>With <a href="http://en.wikipedia.org/wiki/Arithmetic_coding" rel="nofollow">Arithmetic Coding</a>, you can encode a series of symbols (integers in your case), each occurring independently with some probability, almost optimally. That is, if there is no correlation between the numbers, you pretty much can't do better.</p>

CC BY-SA 3.0
2013-02-20T12:27:30.987Z
I realise I might not have said this explicitly enough in the question, but my input distribution might well have very small input frequencies (i.e. the numbers are clustered, but no value repeated). I'm looking to take advantage of the redundancy in the fact that the integers' values are nearby (although there could be multiple clusters with values interleaved - so not all adjacent input values will be close in value - hence the general nature of the input)
mammetchin
CC BY-SA 3.0
2013-02-20T11:41:36.790Z
2013-02-20T11:41:36.790Z
Falk Hüffner
<p>I'm looking to devise a scheme for compressing integers which have a known sampled distribution (they might be clustered around a value, say, or have several areas of differing density). So far, I've centred my thinking around the deflate concept of encoding a value as a huffman symbol representing a (power-of-two sized) range base, followed by a number of bits to offset from the base. </p>

<p>My first question is, does this seem reasonable, or is there a more efficient scheme (I'm not sure what search terms to use to find research on this)?</p>

<p>Secondly, if the above does seem a sensible route, can anyone suggest an efficient algorithm for selecting a number of ranges, their sizes and bases (I guess the ranges might as well be allowed to overlap) which minimises the number of bits needed to encode numbers following the given arbitrary distribution.</p>

CC BY-SA 3.0
2013-02-20T08:54:59.830Z
If you use Huffman coding, you can first encode the bases in Huffman coding, and then encode the offset on top of that. This will guarantee that the bases always take a small number of bits. But if the distribution is arbitrary, this might not help at all (nor will any other heuristic).

By the way, if you don't need a partially decodable code or a prefix code, you can use other types of compressions such as Lempel-Ziv.
Shaull
CC BY-SA 3.0
2013-02-20T09:12:37.377Z
Yes, that's what I was attempting to describe. The question is really, how to find the bases to be used (which are then huffman encoded according to their frequency in the distribution) and how many bits to append (i.e. what the size of each range is). Perhaps 'arbitrary' was a bit misleading (although a reasonable output from the algorithm could be a zero-length huffman code, and 32 (say, for 4-byte ints) bits following (i.e. no compression)). The distributions I'll use are friendlier (for example two clusters around 100 (+/-50), 1000 (+/-250) say).
mammetchin
CC BY-SA 3.0
2013-02-20T09:20:34.153Z
Will you know the distributions in advance?
Shaull
CC BY-SA 3.0
2013-02-20T09:26:15.627Z
yes, and the sequence then to be compressed will be drawn from the distribution, so the expected compression ratio can be computed up front.
mammetchin
CC BY-SA 3.0
2013-02-20T09:29:02.410Z
So, strictly theoretically speaking, you can just take 10 different codes (Huffman, Lempel-Ziv, etc.), and compute the expected length of encoding, and take the best one.
Shaull
CC BY-SA 3.0
2013-02-20T09:34:45.070Z
I suppose, but I don't think applying, say, huffman, to the values would work very well, since there will be very few numbers actually duplicated - they just happen to fall typically clustered together. Hence the suggestion of using something like the zlib distance code, where you find bases which are repeated, and the different, small, offsets are transmitted tersely.
mammetchin
<ds.algorithms><optimization>
Integer compression
mammetchin
# Integer compression

(Asked by: username_0 on 2013-02-20)

I'm looking to devise a scheme for compressing integers which have a known sampled distribution (they might be clustered around a value, say, or have several areas of differing density). So far, I've centred my thinking around the deflate concept of encoding a value as a huffman symbol representing a (power-of-two sized) range base, followed by a number of bits to offset from the base.

My first question is, does this seem reasonable, or is there a more efficient scheme (I'm not sure what search terms to use to find research on this)?

Secondly, if the above does seem a sensible route, can anyone suggest an efficient algorithm for selecting a number of ranges, their sizes and bases (I guess the ranges might as well be allowed to overlap) which minimises the number of bits needed to encode numbers following the given arbitrary distribution.

**Tags:** ds.algorithms, optimization

> **Comments:**
> **username_1**: If you use Huffman coding, you can first encode the bases in Huffman coding, and then encode the offset on top of that. This will guarantee that the bases always take a small number of bits. But if the distribution is arbitrary, this might not help at all (nor will any other heuristic).  By the way, if you don't need a partially decodable code or a prefix code, you can use other types of compressions such as Lempel-Ziv.  
> **username_0**: Yes, that's what I was attempting to describe. The question is really, how to find the bases to be used (which are then huffman encoded according to their frequency in the distribution) and how many bits to append (i.e. what the size of each range is). Perhaps 'arbitrary' was a bit misleading (although a reasonable output from the algorithm could be a zero-length huffman code, and 32 (say, for 4-byte ints) bits following (i.e. no compression)). The distributions I'll use are friendlier (for example two clusters around 100 (+/-50), 1000 (+/-250) say).  
> **username_1**: Will you know the distributions in advance?  
> **username_0**: yes, and the sequence then to be compressed will be drawn from the distribution, so the expected compression ratio can be computed up front.  
> **username_1**: So, strictly theoretically speaking, you can just take 10 different codes (Huffman, Lempel-Ziv, etc.), and compute the expected length of encoding, and take the best one.  
> **username_0**: I suppose, but I don't think applying, say, huffman, to the values would work very well, since there will be very few numbers actually duplicated - they just happen to fall typically clustered together. Hence the suggestion of using something like the zlib distance code, where you find bases which are repeated, and the different, small, offsets are transmitted tersely.  

---

## 1 answers

### Answer by username_2 on 2013-02-20. Score: 1

With [Arithmetic Coding](http://en.wikipedia.org/wiki/Arithmetic_coding), you can encode a series of symbols (integers in your case), each occurring independently with some probability, almost optimally. That is, if there is no correlation between the numbers, you pretty much can't do better.

> **Comments:**
> **username_0**: I realise I might not have said this explicitly enough in the question, but my input distribution might well have very small input frequencies (i.e. the numbers are clustered, but no value repeated). I'm looking to take advantage of the redundancy in the fact that the integers' values are nearby (although there could be multiple clusters with values interleaved - so not all adjacent input values will be close in value - hence the general nature of the input)  

---

