3 ms·

Using additional bits to encode lengths isn't really that different from having a marker indicating if the payload is a match vector or not. In fact, it could b

Using additional bits to encode lengths isn't really that different from having a marker indicating if the payload is a match vector or not. In fact, it could be argued to be less efficient for certain types of data depending on the huffman distribution since all "words" are larger than a byte. It also prevents you from encoding longer matches. I treat the decision as a compromise between the two extremes that "worked" for the majority of types of data "good enough" for some definition of both quoted words. The entire idea works well enough but I wouldn't go out of the way to declare it a marvel of engineering or anything.

HisGraceTheDuck 10y ago
"it could be argued to be less efficient for certain types of data" This is true of all lossless compression.
- banachtarski 10y ago
  You're invoking a stronger "technically correct" interpretation of the statement I'm making. Let me qualify. In a blob with many short repeated sequences, the algorithm as presented is better. In a blob with many long repeated sequences, a marking bit is better. Honestly, neither example is that farfetched.
brian-armstrong 10y ago
This comment shows a baffling level of arrogance. And it can hardly be considered a happy accident, compression methods are tested against real corpuses
- banachtarski 10y ago
  I never said happy accident. Like most algorithms (the reallocation size of a vector when it reaches capacity, the widths of slots in a timer wheel, the hierarchical sizes of a generational gc, etc.) the "correct" answer is determined experimentally. My point is that the choice of encoding small lengths is just a decision, like every other decision and is no more or less elegant than encoding a payload determining marking bit, and shouldn't be celebrated independently. Calling me "bafflingly arrogant" though is a bit perplexing. Can we disagree without resorting to petty jabs at character?
caf 10y ago
The single-bit method can actually be seen as an instance of the huffman-coded method, where the match lengths are all assigned equal entropy estimates and the probability of "match vector" versus "literal character" is hard-wired to 0.5.

HisGraceTheDuck 10y ago

"it could be argued to be less efficient for certain types of data" This is true of all lossless compression.

banachtarski 10y ago
You're invoking a stronger "technically correct" interpretation of the statement I'm making. Let me qualify. In a blob with many short repeated sequences, the algorithm as presented is better. In a blob with many long repeated sequences, a marking bit is better. Honestly, neither example is that farfetched.

brian-armstrong 10y ago

This comment shows a baffling level of arrogance. And it can hardly be considered a happy accident, compression methods are tested against real corpuses

banachtarski 10y ago
I never said happy accident. Like most algorithms (the reallocation size of a vector when it reaches capacity, the widths of slots in a timer wheel, the hierarchical sizes of a generational gc, etc.) the "correct" answer is determined experimentally. My point is that the choice of encoding small lengths is just a decision, like every other decision and is no more or less elegant than encoding a payload determining marking bit, and shouldn't be celebrated independently. Calling me "bafflingly arrogant" though is a bit perplexing. Can we disagree without resorting to petty jabs at character?

caf 10y ago

The single-bit method can actually be seen as an instance of the huffman-coded method, where the match lengths are all assigned equal entropy estimates and the probability of "match vector" versus "literal character" is hard-wired to 0.5.