6 ms·
An In-Depth Look At Huffman Encoding
- pohl 16y agoI recently went through the exercise of implementing a Huffman codec. Instead of the heap (or priority queue) I used the method that uses two queues to build the tree. See the second algorithm given here: http://en.wikipedia.org/wiki/Huffman_coding#Basic_technique http://en.wikipedia.org/wiki/Huffman_coding#Basic_technique Even though I was writing it in Java, it was a lot of fun. I ended up with something that I could use on the server side, or compiled down to javascript in the client with GWT.
- eru 16y agoNice. Doing arithmetic encoding might be a good continuation.
- SeveredCross 16y agoI found the two-queue technique to be much more intuitive than the binary heap technique, which definitely resulted in it being more fun to code. As an aside, the two-queue technique is also more performant, as you can build the tree in O (n) time instead of O (n log n) time.
- deleted 16y ago[deleted]
- eru 16y agoYou still have to sort to build the queues. So you won't get below O(n log n) for the whole algorithm. If you squint just about right, you can probably see the equivalence between sorting plus queues and the tree based techniques. Especially if you use a tree-structured sorting algorithm.
- pohl 16y agoIn my particular case, the character frequencies are (more or less) fixed and the sorting could be done ahead-of-time before feeding the leaf nodes into the first queue. So I really did get O(n) at instantiation time. However, my n is so small that it didn't matter much.
- eru 16y agoYou can also get fix your whole encoding then.
- pohl 16y agoYou can if it's absolutely fixed. But what about when it's only "more-or-less-fixed"? :-)
- eru 16y agoThen you need the sorting, again. You can't have your cake and eat it, too.
- pohl 16y agoBeing able to relegate the cost of sorting to be a one-time cost on a server and allowing clients to build the tree they need for decoding in O(n) allows the client to [something about cake].
- eru 16y agoI don't get it. If the probabilities are fixed, you might as well do the complete prepocessing on the server side.
- pohl 16y agoI guess I chose to build the tree on the client side because the list of character frequencies is a fairly compact representation of the encoding, and I didn't want to serialize the whole tree and send it across the wire to the client. Are you suggesting that the client doesn't need the tree at all? If so, how would the client do the decoding? I confess I'm doing the naive crawling down the tree to the left or right as a 0 or 1 is read. Is there some other way the client could be doing this?
- eru 16y agoSomebody should tell the author not to use JPEG for diagrams. There are ugly artefacts. How do you comment on that site?
- xtacy 16y agoRelated: Arithmetic coding, which achieves compression rates much closer to the theoretical limit. http://en.wikipedia.org/wiki/Arithmetic_coding http://en.wikipedia.org/wiki/Arithmetic_coding EDIT: Note that in all cases, we assume that the symbol occurrences are independent. LZW outperforms Huffman because it doesn't make any such assumption.
- sqrt17 16y agoArithmetic coding is patent-encumbered, and a bit harder to implement. The point where arithmetic coding outperforms Huffman coding is when you have very frequent symbols (i.e. less than two bit or so); you can circumvent this if you apply Huffman coding to larger units such as words or tokens (i.e., instead of characters '4','2', have a single integer token "42"). Another thing that's fun to implement is the Burrows-Wheeler transform which is at the heart of bzip2 (and you then need another compressor for the BW-transformed text, but still...)
- eru 16y agoShouldn't the patents on arithmetic coding be at the end of their live by now? You can probably view Huffman-coding as a very special case of arithmetic coding.
- dalke 16y agoYep. The original paper was in 1979 or so, and pretty much all the US patents have expired.
- sqrt17 16y agoI haven't penetrated the whole patent mess, but I guess the patents on the basic idea have expired now whereas special techniques to make arithmetic coding faster (i.e., nearly as fast as Huffman coding) are the ones where the patents are still valid because those are younger.
- pohl 16y agoI'm sorry for the accidental down-mod. I meant to bump you up. I'm pretty sure the patents have expired by now, though.