# Sorted byte arrays with unique values - best possbile compression

I have byte arrays with following constraints:

• Length between 1 and 256
• Length median about 128, but I have to verify this on larger dataset
• Values are sorted ascending
• Values are unique

I am looking for algorithm for best compression of this data. Maximal uncompressed size for array if it is full is 256B. For median it is 128B.

For now best compression I know is to use bit-field to store if byte is in array or not, and I can omit trailing zeros. So for one array i will use ceiling("max value" / 8) B. For full array (or array containing 248) this will be 32B.

This will reduce size in general, but it is bad for sparse arrays with length < 32. I can use flag to store data compressed or uncompressed if it turns out that uncompressed array is smaller than compressed.

Is there any other trick/optimization/compression i can use to reduce size even more?

Is there any way to calculate theoretical boundary how much it is possible/not possible to compress this class of data so that I can measure quality of my approaches?

One short example of data to eliminate misunderstandings, please note that this array is shorter than expected array in data: { 0, 1, 5, 7, 88, 105, 233, 234, 235, 255 }

-
Each value of your array might be present or not, hence there are $2^{256}-1$ possible arrays (the empty array is disallowed). To recognize all of them, you need $\lceil\log_2(2^{256}-1)\rceil$ bits, which is equal to $256\mathtt{b}$, i.e. $32\mathtt{B}$. In other words, your solution is optimal in the worst case. Of course, if you know the distribution of your arrays, then it could be possible to make the expected size smaller. – dtldarek Feb 26 '14 at 9:49