0

Suppose that we are dealing with integers drawn from a random uniform distribution, on the range $[1 , 2^{30}]$. Is it possible to effectively compress a short list of random numbers, say $2^4$ numbers in the list. Comment - The list can be assumed to be sorted, ascending. With a very long list delta encoding can be effective, but here the list is short and the deltas are expected to be huge. There is very little opportunity to exploit delta encoding of small numbers, with gap values expected to be of the order of $2^{26}$.

Nathaniel Bubis
  • 33,018
Ferenc Pushkash
  • 3
  • $2^{30}$ is not particularly large... Are you hoping to expand any result to larger numbers? In particular, it sounds like you are talking about a total of $64$ bytes worth of data, which might benefit from an RLE compression, but is otherwise rather small to begin with... – abiessu Dec 20 '13 at 03:20
  • We uses 32 bit integers but we have a very large number of lists ( > 2^31 ). The obvious compression is to use 30 bit integers, but we are looking for significantly better saving - if possible - which is the question here. Incidentally, the expected list length is 16, but it does vary (normal-ish random distribution about 16 is expected in list lengths) – Ferenc Pushkash Dec 20 '13 at 03:38

1 Answers1

2

The complexity of a list of $n$ numbers drawn uniformly from $[1,N]$ is $n \log_2 N$ bits, since you have to distinguish between $N^n$ equally likely possibilities. If the numbers have been sorted into ascending order, you can save $\log_2 (n!) \approx n \log_2 n$ bits. In your case, supposing $N=2^{30}$ and $n\approx 2^{4}$, the naive length is $2^4\cdot 30 = 480$ bits, and you can save $2^4 \cdot 4=64$ bits, or about $13\%$, by sorting before compression.

mjqxxxx
  • 41,358
  • Thanks. It confirms my analysis: We have very short lists (say 2^4) and a large range of values (say 2^30). Therefore the numbers are large and the gaps between them are still large ( 2^26 on average). Delta encoding is based on encoding the list of gaps rather than the actual numbers. On average we only need 26 bits to represent a gap and we can save 6 bits from 32. Assuming we have a suitable compression scheme that will give 18.75% compression relative to 32 bit numbers (or 13% gain relative to 30 bit numbers). – Ferenc Pushkash Dec 20 '13 at 04:43