Slashdot Mirror

...doesn't anyone think it might be time to revisit fractal image compression and maybe look at ways of improving iterated function systems and their associated algorithms?

Considering that the best results were obtained using college grads as the compression engine, probably not.

I read the article, got shocked at the time spent comparing the compression of MP3s and DiVX, and didn't read much further.

Google's top hit turns up this site which is chock full of data on every compressor you ever & never heard of:
http://www.maximumcompression.com/index.html

Wikipedia has nice charts to quickly see features and OS support for a handful of common compressors:
http://en.wikipedia.org/wiki/Comparison_of_file_ar chivers

The newsgroup comp.compression has been around awhile, and is maintaining an excellent FAQ:
http://datacompression.dogma.net/index.php?title=C omp.compression_FAQ

Royalties would be what is accomplished.

The LZW algorithm that was patented and people had to pay royalities.

With all the other posts describing prior art, I don't think this claim will hold up.

Actually... if you want to search multiple substrings in one HUGE string, it's much faster to make a suffix tree. Recommended by genetists :)

http://www.dogma.net/markn/articles/bwt/bwt.htm

If you replace the diagonalization step with a BWT, you can merge all of the zeros together at the end. Then, since the values will be in order, you can achieve higher compression than you'd get with the existing Huffman coding. And, there is no patent problem.

...is in Mark Nelson's "The Data Compression Book".

What's especially nice is that the book walks you thru the various steps - minimum redundancy coding, adaptive huffman coding, arithmetic coding... so the improvements are introduced gradually and logically. Good stuff.

Here's that url:

http://dogma.net/markn/articles/Star/

He's talkin about MD5 hashing of small sections, as someone suggested the other day here.

If you actually have the source code, there are other fairly quick ways to find copy & pastes, eg the BWT-based method I implemented in CPD.

That method is pretty fast - it mainly depends on the file scanning time, not the sort we used to find the duplicates (eg using a suffix tree sort instead of quicksort won't gain you much here). However its a bit of a memory hog. I originally wrote the algorithm in perl, though, and it used a lot less - it would probably work on something the size of Linux.

I've come up with a new variation based on rysnc that will be quicker than the original MD5 suggestion, still requires no access to the original source, and sucks a hell of a lot less memory than the BWT method. Its also possible to do incremental checks (extremely quickly) using this method, something we couldn't do before.

There are other interesting techniques based on gzip and the like if this kind of thing interests you.

rsync doesnt use gzip, or the deflate algorithm - it uses the Burrows-Wheeler Transform, same as used in bzip2. If you read Tridge's thesis you'll see that he actually proposes an rzip algorithm based on the BWT and his work on rsync that compresses better than gzip or bzip2 on typical files.

-Baz

Nothing so interesting - I was reading a document on an algorithm that allows you to order the text such that it can be restored to it's original order - however, having it more sorted increases compression ratios dramatically. It occurred to me "hey, you could to this by hand", and it got me thinking on secure encryption by hand...

Speaking of sorting, the scientists contemporary to Galileo used it to "patent" their yet unverified ideas and hypotheses by publishing a "one-way hash" of the statement describing the idea by alphabetically sorting the letters of that statement. E.g. a hypothesis "Mars has two satellites" will be "Aaaeehillmorsssstttw". Of course, to be secure, the statement must be much longer.

Of course, there are exceptions. Obviously it doesn't take much to saturate a modem connection. But modern modems have data compression built in, so there's not a lot to be gained by compressing the data beforehand.

Another example is one I had to deal with recently. Mat Ballard started distributing Kylix help files in HTML format. This is 100 meg of data, so Mat was concerned to minimize his bandwidth costs. He found he got the best result with bzip2, which reduced his file size to a mere 7.6 meg, or twice the compression of gzip.

This caught my interest. I'd like to distribute a similar collection of documentation. But my app needs to be able to read individual files on the fly. Would bzip2 compression work equally well applied to small blocks of data?

Unless I did something wrong, the answer is no. A bzip-in-tar file doesn't seem to come out any smaller than the equivalent zip file. Perhaps I did something wrong, but it does make sense. Bzip2 gains its superior compression by combining the Burrows-Wheeler transform with old-fashioned Huffman encoding. And BW transforms are drastically more effective on big data sets. So I might as well stick with Zip format. Oh well.

Bottom line: no magic bullet for minimizing bandwidth costs through compression. You need to analyze your specific application and find out what's most effective -- and whether it's worth the trouble.

• Big claims, no demo, no papers, and it doesn't work yet.
• It's headquartered in West Palm Beach, Florida. Unclear why, but Southern Florida has been a major scam center for decades.
• They're trying to get people to invest, publicly advertising for "accredited investors". It's not usually done that way. If they went to a VC for funding, the technology would get looked at, hard. (If it worked, getting VC funding for this would be easy.) If they went for an IPO, they'd have to file disclosures with the SEC under penalty of perjury.
• They claim: "All of these traditional methods are being enhanced by ZeoSync through collaboration with top experts from Harvard University, MIT, University of California at Berkley, Stanford University, University of Florida, University of Michigan, Florida Atlantic University, Warsaw Polytechnic, Moscow State University and Nankin and Peking Universities in China, Johannes Kepler University in Lintz Austria, and the University of Arkansas, among others." Yeah, right. Let's see some names.
• The Flash animation on the web site appears to be constructed entirely with stock photography. There's no useful information in the images. (Maybe that's their approach to compression.)

Scroll down to Incredible Claims for descriptions of the last four scams like this. Remember Pixelon?

DjVu is for scanned documents. There is no major accepted file format in use for this kind of data. This will be a huge market once bureaucracies around the world start digitizing their tons of documents. OTOH, DjVu is there for quite a while already and I don't see it having succeeded. Plus, when I installed the plugin under IE 5 a year ago, it was in some dubious beta state. Not nice to work with.

Lossy / lossless image compression types. You cannot compare PNG tolossy schemes. PNG cannot beat a lossy method because the goals are different. Lossless: Compress as small as possible (but the exact original must be restoreable). Typically, the algorithms that throw more resources (CPU and memory) at it are better. Lossy: For a given file size, reach the best quality. You can easily beat PNG with a lossy scheme by simply choosing very bad quality.

Open source. There are a few programs out there. Try TIC. It's GPL'd and beats JBIG-1 by about 40 percent on scanned images, according to the website.

Resources: Image Compression Resources, The Data Compression Library.