5 ms·

"Naively"? Binary packing encoders are still competitive with the state of the art :) Which notably hasn't included variable-length encodings for quite a while.

by ot 5y ago

"Naively"? Binary packing encoders are still competitive with the state of the art :) Which notably hasn't included variable-length encodings for quite a while. Variable-length coding requires that each integer somehow encodes its width. That can be very wasteful. Block-based methods exploit the fact that consecutive deltas usually require a similar number of bits, so it's better to waste a bit on each integer, but amortize the block bitwidth, than having to encode each width independently.

danbruc 5y ago
So 1000, 1001, 1000, 1002, 1000, 1003, 1000, 1004 requiring 80 bits is good if you could get it to 16 bits plus a Huffman tree which would admittedly eat up the 64 bits difference in this tiny example? Storing the delta is essentially predicting that x[i + 1] = x[i] and storing the difference to that prediction. One could do better by having a better prediction, for example x[i + 1] = x[i] + median_gap_size which would bring the prediction error down to 0, 1, 0, 2, 0, 3, 0, 4 in my example, which could be encoded in 24 fixed length integers plus the median gap size. This could probably be further improved by adaptively predicting the gap size. Making the prediction errors small and independent of the gap size makes the use of short fixed length integers in the common case and switch to longer integers for outliers by reserving one short code as an escape code a much better choice. In the end the result is probably heavily dependent on the exact structure of the integer lists you want to compress but I do not see how fixed length deltas can be competitive on arbitrary inputs.
- ot 5y ago
  I would suggest you actually read the whole thread before commenting, as it started by explaining how outliers *do not* make the rest of the list encode with 4 bits per integer. > I do not see how fixed length deltas can be competitive on arbitrary inputs. I also already explained this, most lists in practical applications exhibit local properties that are exploited by blocking. Using Huffman/arithmetic coding generally doesn't work well because the cost of storing the probability tables does not break even with the savings. There was a recent line of work [1] that attempted this with ANS, a faster cousin of arithmetic coding, and the results were honestly underwhelming considering the complexity involved. [1] https://dl.acm.org/doi/abs/10.1145/3159652.3159663 https://dl.acm.org/doi/abs/10.1145/3159652.3159663 > In the end the result is probably heavily dependent on the exact structure of the integer lists Yes, I did not claim that this works with any list, for any encoding scheme you can construct adversarial cases that do not compress well, that's just information theory. But that applies also to the schemes you're floating.
  - danbruc 5y ago
    You are misunderstanding me, I am not primarily talking about outliers. I am saying if the deltas are big in magnitude but concentrated on only a few different values, then encoding the deltas directly is wasteful. Whether you then use entropy coding, which also deals with outliers for free, or whether you use something more sophisticated than deltas, for example double deltas or subtracting the minimum delta, was not really my point. Maybe it was a bit confusing that I first brought this up in the context of outliers.

by ot 5y ago

danbruc 5y ago

So 1000, 1001, 1000, 1002, 1000, 1003, 1000, 1004 requiring 80 bits is good if you could get it to 16 bits plus a Huffman tree which would admittedly eat up the 64 bits difference in this tiny example? Storing the delta is essentially predicting that x[i + 1] = x[i] and storing the difference to that prediction. One could do better by having a better prediction, for example x[i + 1] = x[i] + median_gap_size which would bring the prediction error down to 0, 1, 0, 2, 0, 3, 0, 4 in my example, which could be encoded in 24 fixed length integers plus the median gap size. This could probably be further improved by adaptively predicting the gap size. Making the prediction errors small and independent of the gap size makes the use of short fixed length integers in the common case and switch to longer integers for outliers by reserving one short code as an escape code a much better choice. In the end the result is probably heavily dependent on the exact structure of the integer lists you want to compress but I do not see how fixed length deltas can be competitive on arbitrary inputs.

ot 5y ago
I would suggest you actually read the whole thread before commenting, as it started by explaining how outliers *do not* make the rest of the list encode with 4 bits per integer. > I do not see how fixed length deltas can be competitive on arbitrary inputs. I also already explained this, most lists in practical applications exhibit local properties that are exploited by blocking. Using Huffman/arithmetic coding generally doesn't work well because the cost of storing the probability tables does not break even with the savings. There was a recent line of work [1] that attempted this with ANS, a faster cousin of arithmetic coding, and the results were honestly underwhelming considering the complexity involved. [1] https://dl.acm.org/doi/abs/10.1145/3159652.3159663 https://dl.acm.org/doi/abs/10.1145/3159652.3159663 > In the end the result is probably heavily dependent on the exact structure of the integer lists Yes, I did not claim that this works with any list, for any encoding scheme you can construct adversarial cases that do not compress well, that's just information theory. But that applies also to the schemes you're floating.
- danbruc 5y ago
  You are misunderstanding me, I am not primarily talking about outliers. I am saying if the deltas are big in magnitude but concentrated on only a few different values, then encoding the deltas directly is wasteful. Whether you then use entropy coding, which also deals with outliers for free, or whether you use something more sophisticated than deltas, for example double deltas or subtracting the minimum delta, was not really my point. Maybe it was a bit confusing that I first brought this up in the context of outliers.