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.
Yep. The original paper was in 1979 or so, and pretty much all the US patents have expired.
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.
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.
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...)