4 ms·
Arithmetic coding is patent-encumbered, and a bit harder to implement. The point where arithmetic coding outperforms Huffman coding is when you have very freque
by sqrt17 16y ago
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...)
- 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.
- eru 16y agoNo harm done.