Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a data compression utility in Haskell using Huffman codes

lazamar.github.io

Post reply on HN
Print view View original

11–20 of 94 posts

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

#11

Post by lifthrasiir »

kqr wrote: post #7
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 fashi…

Huffman codes are conceptually isomorphic to arithmetic codes where all probabilities are 2^-k with k integer, so they have an obvious disadvantage due to more inaccurate symbol distribution.

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

#12

Post by hcs »

kqr wrote: post #7
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 fashi…

Huffman codes are less efficient per symbol since each symbol is a bit string, arithmetic coding effectively smears symbols across bits more finely. Whether you use a dynamic or static probability model is a different issue applying to either coding method. (Emotionally though I prefer Huffman codes, they're just so neat)

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

#13

Post by mjan22640 »

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…

> and I'm wondering how many of you that's true for as well

the phrasing sounds like a list comprehension

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

#14

Post by banish-m4 »

Last time I used Huffman codes, it was to run a MICMAC processor macroprogram (assembly text) in the fewest number of microcycles and to use the fewest microinstructions in the microprogram (microcode). So starting with a histogram of the macroinstructions executed (IIRC, I first wrote an interpreter in C to count how many of each were executed), I crafted a progressive decoding microcode program to implement all of the required ISA macro-operations. IIRC, the macro instruction ISA I created was bit-granular instead of byte-oriented. In the real world, it would've been slow and inconvenient. What's nice about Huffman codes is that you can vary the prefix depth based on the distribution of values, so you don't have to have lopsided codes based on 1 bit prefixes.

Also, the microprogram had to deal with branch prediction because it was a non-superscalar pipelined processor model. Guess the wrong branch, and enjoy wasting cycles on a pipeline stall while the correct branch filters forward.

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

#15

Post by lazamar »

lifthrasiir wrote: post #9
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...

Thanks for the link. I was motivated to write the post after reading Moffat’s book ‘Managing Gigabytes’. A pearl from the 90’s.

The authors mention this technique in the second edition.

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

#17

Post by lazamar »

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…

There is one way in which Huffman codes are better: they are easier to explain and simpler to implement.

I went for simplicity of exposition in the post, but arithmetic coders can indeed get arbitrarily close to the entropy, which is not quite the case with Huffman.

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

#18

Post by tromp »

> To make it unambiguous we must make sure that no code word is a prefix of another code word.

Technically, this is not quite correct. The class of so-called uniquely decodable codes is unambigous, and a superset of the prefix codes. One simple example of a uniquely decodable code is the reverse of a prefix code. For the example in the article that would be

    a 1
    b 00
    c 10
While the code for a is a prefix of the code of c, one can still unambiguously decode any code sequence by processing it in reverse order. It would be interesting to see a uniquely decodable code that is neither a prefix code nor one in reverse.

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

#19

Post by lazamar »

tromp wrote: post #18

> To make it unambiguous we must make sure that no code word is a prefix of another code word. Technically, this is not quite correct. The class of so-called uniquely decodable codes is unambigous, and a superset of the prefix codes. One simple example of a uniquely decodable code is the reverse of a prefix code. For the example in the article that would be a 1 b 00 c 10 While the code for a is a prefix of the code o…

That’s interesting. I guess this is not usually used because you may have a long string of bits that is ambiguous till you get to a disambiguating bit.

Something like

`100000000000000001`

In this case, where to know whether the first code was an `a` or a `c` you have to read all the way to where the zeroes end.

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

#20

Post by benreesman »

Haskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way.

But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good.

If Haskell sucks like all languages it’s because Haskell excels at using computers to compute something: Haskell considers data shuffling a strictly secondary concern compared to doing actual computations.

Post reply on HN