News for hackers. Stuff that matters.
Re:The Elegance of Deflate by banachtarski on Monday August 22, 2016 @02:33AM (#12334475)
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.
Re:The Elegance of Deflate by HisGraceTheDuck on Monday August 22, 2016 @02:56AM (#12334552)
"it could be argued to be less efficient for certain types of data" This is true of all lossless compression.
Re:The Elegance of Deflate by banachtarski on Monday August 22, 2016 @03:11AM (#12334606)
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.
Re:The Elegance of Deflate by caf on Monday August 22, 2016 @08:26AM (#12335789)
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.
Re:The Elegance of Deflate by brian-armstrong on Monday August 22, 2016 @03:10AM (#12334601)
This comment shows a baffling level of arrogance. And it can hardly be considered a happy accident, compression methods are tested against real corpuses
Re:The Elegance of Deflate by banachtarski on Monday August 22, 2016 @03:15AM (#12334618)
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?