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.

  • $\begingroup$ 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. $\endgroup$ – Shaull Feb 20 '13 at 8:54
  • $\begingroup$ 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). $\endgroup$ – mammetchin Feb 20 '13 at 9:12
  • $\begingroup$ Will you know the distributions in advance? $\endgroup$ – Shaull Feb 20 '13 at 9:20
  • $\begingroup$ yes, and the sequence then to be compressed will be drawn from the distribution, so the expected compression ratio can be computed up front. $\endgroup$ – mammetchin Feb 20 '13 at 9:26
  • $\begingroup$ 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. $\endgroup$ – Shaull Feb 20 '13 at 9:29

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

  • $\begingroup$ 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) $\endgroup$ – mammetchin Feb 20 '13 at 12:27

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.