Re:The Elegance of Deflate
by Dylan16807 on Monday August 22, 2016 @03:00AM
(#12334573)
It's a good system. Though the full DEFLATE spec has quirks like storing literal blocks prefixed by their length and then the ones complement of their length.
The next step in improving a simple compression algorithm is to replace Huffman encoding with arithmetic/range encoding. Huffman encoding proceeds one bit at a time, treating everything as having a probability that's a power of 1/2. Arithmetic/range encoding uses more accurate probabilities and then packs them together, letting you save a fraction of a bit with every symbol. As an analogy, consider how to encode 3 decimal digits. You could spend 4 bits on each digit, and it would take 12 bits total. Or you could combine them into a single 10 bit number.
The next step in improving a simple compression algorithm is to replace Huffman encoding with arithmetic/range encoding. Huffman encoding proceeds one bit at a time, treating everything as having a probability that's a power of 1/2. Arithmetic/range encoding uses more accurate probabilities and then packs them together, letting you save a fraction of a bit with every symbol. As an analogy, consider how to encode 3 decimal digits. You could spend 4 bits on each digit, and it would take 12 bits total. Or you could combine them into a single 10 bit number.