Dense Data Compression (Delta Encoding?) 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?
 A: 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?
