Compressing a list of integers
Brian
I'm a complete beginner and could use some help. Go easy on me,
I'm likely to not understand indepth mathematical explanations.
I have a long list of 80 bit integers stored in a 10 byte array.
The data is sorted. The only relationship between values is
N(x) < N(x-1). The data is unique. It's fairly dense.
A hex dump might look like this:
00 00 00 00 00 00 00 00 08 20
00 00 00 00 00 00 00 1C 53 43
00 00 00 00 00 00 00 1C 82 22
etc...
One obvious way of compressing this data is to store the differences.
Only three bytes change between the first and second array. Only
two bytes change between the second and third.
That would compress the data to 25% of its original size depending
on framing and whatnot. Simple. Fast. Single pass.
Am I missing some obvious far superior approach?
For framing, I was thinking a single leading byte could have a
bitmask of valid/invalid bytes. Something like 0x00 would say
the current array shares no common bytes with the previous.
0x01 would say the current array and previous array have the
ls byte in common. 0x03 ... both the first and second LSB
in common, and so forth.
For easier random access, I thought that I could force the bitmask
to 0 every 1000th data value. That is, the data would be something
like an incremental backup. So I could be guaranteed some minimal
scanning time to get to solid, fully defined values.
Thanks for reading. I appeciate any help.
toby
> ...
> I have a long list of 80 bit integers stored in a 10 byte array.
> The data is sorted. The only relationship between values is
>
> One obvious way of compressing this data is to store the differences.
Just some thoughts off the top of my head. I agree that differences is
a fruitful starting point. Recently I was thinking about a similar
problem, and considered this approach: store a variable number of bytes
for each difference, where each byte uses 7 significant bits and the
high bit set indicates the end of an entry. So a difference of 0-127
would be stored in one byte, 128-16383 in two bytes, 16384-2097151 in
three bytes, etc. Depending on the nature of the data, this could be a
significant compression (up to 10:1).
It's the form of the data that will dictate the best solution. For
instance, if the differences only represent a small number of different
values, these could be encoded as variable length bit strings chosen
using a Huffman-type algorithm. This might work even for a large
population of values, if the distribution is highly skewed. If the data
has a consistent distribution, the dictionary could be fixed.
byb...@rocketmail.com
> Just some thoughts off the top of my head. I agree that differences is
> a fruitful starting point. Recently I was thinking about a similar
> problem, and considered this approach: store a variable number of bytes
> for each difference, where each byte uses 7 significant bits and the
> high bit set indicates the end of an entry. So a difference of 0-127
> would be stored in one byte, 128-16383 in two bytes, 16384-2097151 in
> three bytes, etc. Depending on the nature of the data, this could be a
> significant compression (up to 10:1).
http://citeseer.ist.psu.edu/williams99compressing.html
I've used that method you mention before with good results and it's in
the paper listed above. It especially helps if you feed the data to
another compressor like gzip/bzip as there is less dead space between
numbers.
-t
nightlight
> this data is to store the differences....
>
> Am I missing some obvious far superior approach?
There are several improvements, depending on additional info you may
have about the source of the numbers.
1) The most obvious improvement would apply to monotonically
(de)increasing integer sequences which have additional regularity, such
as linear or quadratic increase (or via any simple to compute monotonic
function). To detect such regularity you could continue with taking
differences of differences. For the linearly increasing sequence these
second order differences will become zero. For quadratically increasing
functions, the third order differences will become zero.... etc. Even
if the higher order differences don't become exactly zero, they may
become much smaller numbers than those in the original sequence, which
would help the compression.
2) You may examine the statistics of the first (or higher) order
differences. If the differences are not uniformly distributed, then
they are compressable (e.g. via Huffman or Arithmetic coding). For
example, for naturally occuring sequences, the small differences are
often more frequent than the large differences. The case (1) is a
special case of this type of regularity (when value 0 is highly
overrepresented).
3) If none of the above applies (or after the regularities above have
been extracted), you will have a sequence of integers uniformly filling
the range from some minimum to some maximum value. This can always be
remapped to a sequence from 0 to some max value M, again uniformly
filling this range [0,M]. At this point storing the numbers separately
as fixed length bitstrings will generally waste space, depending on the
value M:
a) If M is an integer of the form 2^s - 1 (such as 3, 7, 15, 31..) then
the plain binary storage with fixed number of s bits per integer will
be optimal.
b) If M is not of the form 2^s-1, then it always satisfies the
inequality of the form:
A = 2^(s-1)-1 < M < 2^s - 1 = B .... (1)
Here you have two ways to proceed, one slighlty suboptimal but quick
and the other fully optimal but slower.
i) === Quick Suboptimal Method (slice codes) ===
Here you will encode integers not via the fixed length of s bits (which
you could certainly do) but some integers via (s-1) bits per integer
and the rest via s bits per integer. Specifically, using the
definitions of A and B from eq (1), you will encode the first B-M
integers (which is, by (1), always a positive number) using (s-1) bits
and encode M+1-(B-M) = 2M-B+1 remaining integers using s bits.
Example: let M=5, i.e. there are 6 distinct integers 0,1,2,3,4,5. Then
the value B in (1) will be 7=2^3-1 and value A: 3=2^(3-1)-1, and s=3.
By the rule given above you would encode B-M=7-5=2 lowest integers 0
and 1 in (s-1)=3-1=2 bits and encode the 2M-B+1=10-7+1=4 remaining
integers in 3 bits. The encoding table is thus:
0 00
1 01
2 100
3 101
4 110
5 111
The plain encoding of method (a) uses 3 bits per integer, while method
(i) uses (2*2 + 4*3)/6 = 16/6 = 2.66... bits per integer, which is 89%
of the plain encoding size. While clearly an improvement over the
simple method (a), the theoretically optimal value is log2(M+1) =
log2(6) = 2.58 bits per integer.
ii) === Optimal Method (radix codes) ===
You encode the integer sequence as a sequence of digits of some number
X given in radix R=M+1. For example for M=5, you would encode integers
as if they represent digits of a single number X in radix 6. If your n
integers are D1, D2, ... Dn and for each Di you have 0 <= Di < R, then
you compute X as:
X = D1 + R*D2 + R^2 * D3 + ... + R^(n-1) * Dn ....
(2)
or quicker via Horner scheme as:
X = ((... ((Dn*R + D[n-1])*R + D[n-2])*R +...+ D2)*R + D1 ....
(3)
Using (2) you can often store powers of R in a table. Note that both
expressions (2) or (3) require arithmetic precision for multiplies and
adds which is of the size (in bits) of the output, the number X. You
can trade off some compression optimality for speed by breaking
sequence of integers into fixed size blocks of just few integers, say Q
integers, so that (2) or (3) are computed for each block separately and
the arithmetic fits in, say 32 or 64 bits. To select good values of Q
you can expand log2(R) into continuous fractions and select Q from the
denominators of 1st, 3rd, 5th... and other fractions of odd order.
For example for our earlier R=6 case, L = log2(R) = 2.584962... which
gives you cointinuous fractions approximating L as 3/1, 5/2, 13/5,
31/12, 106/41, 137/53, 791/306, ... etc. The first one 3/1=3 is the
fixed 3 bit encoding of individual integers. The 3rd one 13/5 tells us
to use blocks of 5 integers, in which case X<6^5=7776 which uses 13
bits to represnt X (encoding the 5 integers via eq (2)), thus yields
13/5=2.6 bits per integer which is already better than the 2.666.. bits
for method (i) and is nearly as quick. The next useful block size would
be Q=41 integers (from 106/41). Here the X<6^41 uses 106 bits for 41
integers, yielding 106/41=2.58536... bits per integer, which is a
further improvement over the 2.6 bits we get for Q=5, but erquiring now
106 bits of arithmetic precision. The next block size Q=306 from the
fraction 791/306 yields encoding with 791/306 = 2.58490... bits per
integer but requires 791 bits of arithmetic precision.
There is still a faster way than doing (2) and (3) directly, which is
more optimal than the blocking. The method (invented by Boris Ryabko)
is described in references [61] and [62], which are available at the
web page:
http://www.1stworks.com/ref/tr/tr05-0625r.htm
There is finally an even faster and more optimal method than Ryabko's,
called "Quantized Indexing" (QI) which will be published (along with
the source code for encoder & decoder) at the site above in November
this year. The QI is more general algorithm than the methods discussed
above since it works as a general entropy coder and an optimal data
structures (such as trees, graphs, self-delimiting sequences, etc)
encoder. It is based on a recently discovered highly accelerated (about
an order of magnitude faster than the fastest arithmetic coders) form
of conventional enumerative/combinatorial coding (which is described in
references 1, 11, 12, 13, 23 on the page above; the radix codes of eq's
(2) and (3) above are a special case of the enumerative coding).
nightlight
> you can expand log2(R) into continuous fractions
should be
> you can expand log2(R) into continued fractions
and
> which gives you cointinuous fractions
should be
> which gives you continued fractions