Building a data compression utility in Haskell using Huffman codes

For all readers, arithmetic codes are better in nearly all ways. They can be implemented in less RAM and code, they compress and decompress to a better ratio, and the probabilities of different symbols appearing can be dynamically updated during the stream far more easily.

The only reason Huffman codes are used is they were invented first and arithmetic codes were patented. That patent has now expired, so we should use the better design.

Re: Building a data compression utility in Haskell using Huffman codes

#6

Post by londons_explore » Thu, Jul 04, 2024, 7:21 AM UTC

londons_explore wrote: post #5

For all readers, arithmetic codes are better in nearly all ways. They can be implemented in less RAM and code, they compress and decompress to a better ratio, and the probabilities of different symbols appearing can be dynamically updated during the stream far more easily. The only reason Huffman codes are used is they were invented first and arithmetic codes were patented. That patent has now expired, so we should u…

Two slight benefits of Huffman codes over arithmetic:

* They usually self synchronize when some data is corrupted (but not guaranteed, does not apply where the Huffman table is dynamic)

* Neither Huffman nor arithmetic codes are easy to parallelize the decoding of, but Huffman is slightly easier.

Re: Building a data compression utility in Haskell using Huffman codes

#7

Post by kqr » Thu, Jul 04, 2024, 7:46 AM UTC

londons_explore wrote: post #5

For all readers, arithmetic codes are better in nearly all ways. They can be implemented in less RAM and code, they compress and decompress to a better ratio, and the probabilities of different symbols appearing can be dynamically updated during the stream far more easily. The only reason Huffman codes are used is they were invented first and arithmetic codes were patented. That patent has now expired, so we should u…

I was under the impression that arithmetic codes are guaranteed to be at least one bit less efficient than Huffman codes per input block. What makes you say they have better compression ratio?

Are you thinking of pre-defined Huffman tables that aren't adapted to the input? Because the latter ought to be as good as it gets.

(I agree with the other benefits. Since arithmetic coding tables are built in a streaming fashion rather than constructing the codebook up front, they are more memory-efficient while working.)

Re: Building a data compression utility in Haskell using Huffman codes

#8

Post by mrkeen » Thu, Jul 04, 2024, 7:49 AM UTC

There exists an array-based, in-place algorithm for this, reducing the need to allocate trees and chase pointers.

I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well.

While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays, since the situations when you care most about compression are probably the situations when you have a lot of data and want to run fast.

  In-Place Calculation of Minimum-Redundancy Codes
  Moffat, Katajainen.  1995.
  http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

Re: Building a data compression utility in Haskell using Huffman codes

#9

Post by lifthrasiir » Thu, Jul 04, 2024, 7:56 AM UTC

mrkeen wrote: post #8

There exists an array-based, in-place algorithm for this, reducing the need to allocate trees and chase pointers. I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well. While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays…

> In-Place Calculation of Minimum-Redundancy Codes

Or in general, refer to "On the Implementation of Minimum Redundancy Prefix Codes" by Moffat and Turpin (1997), as strongly recommended and later explained by Charles Bloom [1].

[1] https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...

Re: Building a data compression utility in Haskell using Huffman codes

#10

Post by lifthrasiir » Thu, Jul 04, 2024, 7:58 AM UTC

londons_explore wrote: post #5

For all readers, arithmetic codes are better in nearly all ways. They can be implemented in less RAM and code, they compress and decompress to a better ratio, and the probabilities of different symbols appearing can be dynamically updated during the stream far more easily. The only reason Huffman codes are used is they were invented first and arithmetic codes were patented. That patent has now expired, so we should u…

If you do have an option to switch from Huffman, rANS is now the way to go, not a clasical arithmetic coding.