3 ms·
I 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
by pohl 16y ago
I 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?
- 16y ago
- SeveredCross 16y agoIndeed, though as the OP points out just below, if you have fixed frequencies, you don't have to sort. That said, you generally have fixed frequencies with a predetermined set of constraints on the data, and you can determine the most common character frequency (or it's already known). I'm not sure how common this is in real-world applications of Huffman coding. Seeing as you should only be building the tree once though, you're right--you'd be hard-pressed to tell the difference between the two approaches, barring implementation mistakes. Designing an implementation mistake that would cause noticeable differences is an exercise left to the reader.