History of Lossless Data Compression Algorithms
ieeeghn.org
ieeeghn.org
The article contains a lot of terms you can search for if you are interested in these things, but sadly is not very informative on its own.
I also need to see about getting some of my old (15+ years) course notes online.
Just in those two, much history and memory lost and a hit for UC Santa Cruz's computer engineering and science departments (Huffman passed a number of years back, Glen this year after a period of retirement).
Edit - the scope of the article and the title provided...a serious disconnect in terms of breadth. But, better than nothing.
The first day it didn't take long for the lecture to turn to 7-dimensional spheres, their packing, and its applications to network routing. He was a tough bastard-- lots of multiplication of large numbers on tests, with only a table of logarithms and exponentials. He loved tricky questions on the tests- for example he taught us Karnaugh maps, mentioned the sides wrapped around, then had an example on the final with 1s in all four corners (I hadn't realized maps wrap around the corners, too).
Great teacher; wonderful lecturer, hard grader. I failed the class (I was a biochem major and graduated), the only CS course I took in college.
I really wish I had kept the notes from that class.
That is, to some extent I subscribe to the compression-as-intelligence school of thought: compressors are tiny little AIs which try to predict regularities in the bitstreams they are given ( http://prize.hutter1.net/ http://mattmahoney.net/dc/dce.html http://www.danburfoot.net/research.html ).
But when we look at the state of the art like ZPAQ, the AI techniques used don't seem to be much more complex than, say, a one or two layer neural network which might as well be from the 1970s. You don't see anything fancy like deep networks or other modern staples like random forests.
So this makes me wonder: maybe compression performance has stagnated because we're not willing to provide compression algorithms extremely large amounts of data or runtime, and so simple algorithms really do perform best with the minimal resources we're willing to use for compression. (People are happy to run neural networks on thousands of GPUs with many gigabytes of data and wait weeks for training to finish; can you imagine a compression utility which required that?)
I very much believe in domain-specific intelligence, and correspondingly domain-specific compression. Here's a practical business use case for lossless compression (in-memory analytics), which I have been developing:
http://tuulos.github.io/pydata-2014/
In contrast to general-purpose encoders, this approach is extremely data-intensive, compressing terabytes per chunk.
Yes, but my point is. that we seem to be doing better at general-purpose intelligence than at compression despite the apparent equivalence of progress.
To me it simply looks like there just isn't much possibility of improvement in that field. Ultimately, you're limited by the pigeonhole principle.
Special-purpose lossy compression, i.e. video - that's where you see leaps and bounds in active research and improvement.
If we could step out of this corporate context, we would likely do better on the algos.
On the topic of video, the latest stuff is still based on decades old core technology. Its still block-based motion compensated transforms which has been around since at least MPEG-1. Don't see any leaps and bounds in what's used now. No wavelets, no fractals, no other new stuff. Just better optimized versions of the base.
There's an inherent limit at the entropy of the source, and usually it is not too hard to get within a few percent of that entropy (as near as we are able to model it). After that, you can do increasingly complex things, but for rapidly diminishing returns. For example, there are definitely lossless audio compressors that can make things smaller than FLAC, but usually only by a percent or two, and they are an order of magnitude or more slower.
To me, a lot of the interesting research at this point is exploring the compression/speed trade-off. That's what makes LZMA interesting (it dominates bzip2 on both axes). Google has also done some interesting work in this space. This matters when your goal is to save network transmission time: if you're only sending the data once, anything you do has to be faster than just sending more data on the wire.
Provably optimal, even (assuming infinite precision).
Both were quite widespread in the BBS era.
However, PAQ tends to be really* slow, largely because it tries more things. It's highly tunable, but people who aren't compression geeks tend to not want to tune their compression. Presets are available.
That's pretty much why it hasn't caught on - speed. There may be some hybrid approaches that deliver a better compromise between context mixing's effectiveness and dictionary coding's speed and memory usage: I guess you could argue LZMA, bringing a Markov-chain algorithm into the mix, is one such, in a way. Sort of.
I'm also a little antsy about ZPAQ formats containing bytecode descriptions of the decompression algorithm needed, and are, broadly speaking, executable (and in some cases, are). That seems like the kind of thing that may invite security problems if approached without due caution.
I once heard someone describe compression programs as 'expansion programs with interesting failure cases', and so, of course, the best compression program to use depends on exactly which failure cases you're interested in.
GIF looks like crap on some images because it's paletted to [2,4,8,16,32,64,128,256] colours - so many images are reduced to a palette (say, with an octree) and/or dithered (perhaps badly, as dithering tends to increase noise, if not entropy), and also sometimes because some techniques exist (one implementation can be found in Photoshop's "Save for Web") which perform lossy transforms on the data so LZW compresses it better - the result is noisier, however, because it intentionally introduces repeating patterns.