Integer array compression

Giganews Newsgroups
Subject: Integer array compression
Posted by:  dbrotz…@informationmediary.com (Dean)
Date: 19 Nov 2003

Hi All,

I'm wondering if anyone can suggest an algorithm to compress an array
on 24 bit unsigned integers (of length n).

A typical set of data can be generated by the following pseudo code.

number = 0
array  = []
while(array.length() < n)
{
    number = number + gaussian(mean, sdev)
    array.append(number)
}

where the mean is mostly greater than sdev

Thus the data is mostly monatomic (can have small decreases) and
smooth.

I can think of two methods to help:

1) store nth order differences (deltas) instead of the whole values.
The differences should be less than 24 bits (especially when the
numbers get large).

2) Don't store the entire bit string.  E.g. 7 is represented as
000000000000000000000111 but can easily be reconstructed by only
storing the following bit string: 00100  0111.  The first sequence
being a length of bits to read (always 5 bits) and the second sequence
is the seed of the real number just requiring the duplication of the
first bit to the length of 24 bits in total.

Are there any other ways to compress this type of data?  If not is
there some sort of delimiter that is smaller than the 5bit length
delimiter I have and does the same sort of thing?

Thanks in Advance,
Dean

p.s. saving RAM is much more important than code size or speed

Replies