News for hackers. Stuff that matters.
Re:An In-Depth Look At Huffman Encoding by sqrt17 on Thursday January 20, 2011 @12:55PM (#2124518)
Arithmetic 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...)

Re:An In-Depth Look At Huffman Encoding by eru on Thursday January 20, 2011 @01:11PM (#2124588)
Shouldn'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.

Re:An In-Depth Look At Huffman Encoding by dalke on Thursday January 20, 2011 @02:31PM (#2124929)
Yep. The original paper was in 1979 or so, and pretty much all the US patents have expired.
Re:An In-Depth Look At Huffman Encoding by sqrt17 on Thursday January 20, 2011 @02:33PM (#2124937)
I 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.
Re:An In-Depth Look At Huffman Encoding by pohl on Thursday January 20, 2011 @01:27PM (#2124654)
I'm sorry for the accidental down-mod. I meant to bump you up.

I'm pretty sure the patents have expired by now, though.

Re:An In-Depth Look At Huffman Encoding by eru on Thursday January 20, 2011 @05:45PM (#2125636)
No harm done.