What's the legal status of popular compression algorithms and transforms?

There are many popular patented compression algorithms or transforms like LZW, Arithmetic Coding, Schindler's Sort Transform (STx), MP3, probably LZX and many others. They were patented a long time ago and patents last limited time. Is that true? If so, then most of them should be now invalid and algorithms should be free.

I am implementing STx and BWT transforms in OpenCL and I'm curious if I have to pay for licence if I want to make money on it.

And what about Range Encoding? It's basically equal to Arithmetic Coding from efficiency perspective, but different in many details.

Normally, patents last 20 years (US, Europe, Japan, China at least). MP3 has long time before it's free. BWT isn't that old either. Don't know about others. Also, there might be patents on implementation smarts that are newer than an algorithm itself.

And no, it doesn't matter if you make money, if you make a program that implements patented technology and distribute it in a country where the patent is valid, you have to pay or risk being sued.

I am not a lawyer, but from a practical matter only a judge can decide if something infringes on a patent or not. Usually the judge doesn't know anything about compression technology, so it boils down to which side can hire the best expert witnesses and lawyers. If you are writing software on your own and giving it away, it is unlikely anyone will notice or care. If you are a big company and have a successful product then you can be sued by anyone for anything regardless of whether they have a valid claim or not. This is more likely to happen in the U.S., which unlike most other countries, recognizes software patents and has a lot of lawyers. Most other countries take the more enlightened attitude that software patents have the opposite of the intended effect of encouraging research.

For example, in 2004, Forgent claimed that JPEG infringed on their patent, sued 30 companies and collected $90 million in settlements on a patent that the USPTO later ruled was invalid due to prior art. The patent was on the "invention" of using a single code to represent a run length of one value followed by another value (the JPEG RS code). Forgent still got to keep the money, though. http://en.wikipedia.org/wiki/Forgent_Networks

There are, unfortunately, thousands of patents on data compression and many of them make very broad and usually overlapping claims. For example, there are over 600 patents on MPEG-2. As a practical matter, the patents you need to worry about are mostly on video and audio formats like MPEG-2, MPEG-4, MP3, AAC, etc.

Patents on LZW (Compress, GIF) and arithmetic coding have expired. Patents on CTW, ST, and Stuffit's JPEG compression have not yet expired. (I describe these in my book, http://mattmahoney.net/dc/dce.html ). There may have been patents on most of the LZ type algorithms at one time (now expired) but their owners never enforced them except for LZW. Huffman coding, BWT, PPM, DMC, symbol ranking, and context mixing were never patented as far as I know.

I made PAQ open source partly to establish prior art so that nobody else could patent it, but that hasn't stopped some people from trying. http://encode.su/threads/256-Spec-fo...ble-PAQ?p=4740 (post #20). After I wrote a letter to the USPTO, they rejected Infima's attempt to patent PAQ6 (by plagiarizing by technical report). So at least they can do something right.