1
$\begingroup$

Let $X $ be a dense integer set such that its elements are closely knit in value.

For instance:

1 1 1 1 2 2 2 2 2 3 3 5 5 6 6 6 6 6 7 7 7 7 8 8 8 8 8 8 ...

I am looking to compress this data set in whatever means possible, currently resorting to delta encoding. Through delta encoding, I am able to store the above array with only bits of data rather than full integers, as I'm only taking the difference from one element to the next. However, as you'll notice, the above set lacks a 4. Although the data is fairly dense, there are few values (<0.1%) that are not found. I have resorted to inserting these elements like so:

1 1 1 1 2 2 2 2 2 3 3 4 5 5 6 6 6 6 6 7 7 7 7 8 8 8 8 8 ...

in order to create a delta-encoded set:

1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 ...

This results in some fuzzy data, leading to minimal but questionably negligible side-effects to the original set.

My question is, are there other methods for normalizing dense data and compressing it to reduce the space complexity revolved around it?

Improve this question
$\endgroup$
5
  • $\begingroup$ Why not just use run-length encoding? $\endgroup$
    – Neil G
    Commented Aug 8, 2012 at 19:18
  • $\begingroup$ Assuming 100 different values and 1 instance of each, that's >200 bytes (let's consider the min: 8 * 200 = 1600 bits). If we had 16 times that amount, with 16 instances of each, delta encoding would represent the difference by 1 bit each (100 * 16 = 1600 bits), taking up the same amount of space. $\endgroup$
    – user12760
    Commented Aug 8, 2012 at 19:32
  • $\begingroup$ If you actually mean "in whatever means possible", you can use gzip encoding. There is a gzip library in most languages, but your data is so scrambled that you cannot do anything with it. So do you want to actually do something with the compressed data, or you want to store it for later use? $\endgroup$
    – gui11aume
    Commented Aug 8, 2012 at 20:15
  • $\begingroup$ There are operations to be conducted on the data, so gzip compression may not be the best solution in this case. The data should easily transfer states. $\endgroup$
    – user12760
    Commented Aug 8, 2012 at 20:17
  • 3
    $\begingroup$ To get a useful answer, then, please tell us (1) what "operations" will be performed, (2) which integers might appear in the dataset, (3) how frequently they might appear, (4) how large the dataset might be, and (5) what the cost of a lossy compression scheme would be. Also, what does this question have to do with fuzzy set theory (one of your tags)? $\endgroup$
    – whuber ♦
    Commented Aug 8, 2012 at 20:25

1 Answer 1

Reset to default
1
$\begingroup$

There are quite a few precompression transforms that can be applied to the raw data that, at first, look like they make things larger, but using them results (after compressing with something like gzip) in a smaller compressed file than compressing the raw data directly (with something like gzip).

Off the top of my head, here are several different transformations I would try with raw data that looked something like:

1 1 1 1 2 2 2 2 2 3 3 5 5 6 6 6 6 6 7 7 7 7 8 8 8 8 8 8 ...

== simple delta coding ==

After simple delta coding of that raw data, we get

1 0 0 0 1 0 0 0 0 1 0 2 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 ...

which should be easy to compress further. (The "2" reflects the jump of +2 from 3 to 5).

== insert every value ==

Rather than manually insert only values that do not yet exist in the bag ("multiset"), perhaps it would be useful to add one of every value in the range of values in the bag -- i.e., add to that bag the set { 1, 2, 3, 4, 5, 6, 7, 8, ... } -- so every value in the range occurs at least once in the new bag. With the above raw data, this results in a new bag like:

1 1 1 1 1 2 2 2 2 2 2 3 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 8 8 ...

This is a lossless transform, because you can simply remove one of each unique value in that new bag to recover a bag identical to the original bag.

(Inserting only values that do not yet exist in the bag is "lossy", because when the new bag has only 1 copy of a value, it's not possible to determine if the original bag had only 1 or zero copies of that value).

After that, delta coding gives only 1s and 0s:

1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 ...

which should be even easier to compress further.

== counts ==

Using something reminiscent of the counting sort, we can make an list of "counts", compressing the above raw data to counts := { 0 4 5 2 0 2 5 4 6 ... };

which indicates that, in the original bag of data, there are zero "0" values, 4 "1" values, 5 "2" values, two "3" values, zero "4" values, two "5" values, etc.

(This is equivalent to storing, for each "1" in the above representation, only the number of 0 consecutively following it before the next 1; something like run-length encoding).

Even this could be compressed further.

Do you really need to be able to recover the original data exactly, or is only storing a "quantized counts" adequate? In other words, if you stored only a 2 bit value for each count, where that 2 bit value indicated a count of "0", "1", "2", or "more than 2", going to give you all the data you really need?

== curve fitting ==

Would it make any sense to try to fit a straight line -- or some more complex curve -- through this raw data, or through any of the preprocessed intermediate sets of data mentioned above? I.e., is the reason we're getting a lot of repeated values because we're measuring something like the position of a slowly-crawling turtle once a second, and rounding the position to the nearest 1 foot?

Improve this answer
$\endgroup$
1
  • $\begingroup$ I actually implemented a similar lossless solution to your insert every value and was just thinking (while I was brushing my teeth) about placing it on here 2 minutes ago haha. I'll accept your answer though, thanks. $\endgroup$
    – user12760
    Commented Aug 21, 2012 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.