# Integer compression

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.

• 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 Feb 20 '13 at 8:54
• 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 Feb 20 '13 at 9:12
• Will you know the distributions in advance? – Shaull Feb 20 '13 at 9:20
• 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 Feb 20 '13 at 9:26
• 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 Feb 20 '13 at 9:29