Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 }

share|improve this question
2  
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 at 9:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.