The PAQ (official website here) compressors are very efficient (as in compressed file size). It does so at the expense of speed and memory usage (note: this is only true for some of the experimental PAQ versions).
PAQ has won the Hutter Prize and the Calgary Challenge.
NOTE: The ZPAQ Open Standard Journaling Archive is a culmination of all of the experimental PAQ Libraries.
ZPaQ uses deduplication, multi-threading, and a range of compression
algorithms (LZ77, BWT, and context mixing) for high performance.
UPDATE: There is a GUI wrapper built (using .Net) for ZPAQ called winzpaq. You can read release notes here and download the latest version directly from this site. As of this edit, it works on Windows, but from the release notes it sounds like it may work on Linux as well (because of Mono).
UPDATE: I will address the criteria list:
- Compresses files and directories (can contain an internal directory structure).
- Yes, most versions of PAQ will do this (paq8hp12any is a specialized version of PAQ8hp that specifically states that it does not compress or create directories).
- Should be designed to be efficient with input file sizes from around 1 to 200 MB.
- This benchmark shows that the different PAQ utilities were able to compress the 100 MB enwik8 text file (used in the Large Text Compression Benchmark) down to less than 20 MB (whereas the same benchmark show ZIP at level 9 compression at approx 36 MB).
- Password protection is nice, but optional.
- ZPAQ (which is really the culmination of all of the experimental PAQ libraries, put into a general purpose compression utility) supports password encrypting (there is mention of it in the History section as of version 6.44).
- Compresses text as well as media files (mp3, exe, movies, photos) without making them bigger in most cases.
- While I couldn't find mention of mp3/exe/movies directly, the Silesia Open Source Compression Benchmark tested against various file types (Windows DLL, binary, DICOM images, PDF, ASCII text) and the various PAQ libraries outperformed the various zip utilities. At a glance (there is a lot of data), the files were all smaller than the original (original file sizes found at the bottom of the list). There is also mention of being able to compress JPG files in this benchmark.
- According to the official ZPAQ website, zpaq is a free and open source (GPL v3).
- The amount of time that it takes to compress the files is not a very important criterion, as long as it completes in a "reasonable"
time (and by that I mean, a few hours on a typical desktop computer
might be OK for several hundred megs of input data, but a few hundred
years is probably not acceptable).
- The speed will depend on the version of PAQ you use. As I've been exploring these to improve this answer, I have noticed that the ZPAQ library has made great speed enhancements and still has nearly the compression ratio of some of the experimental libraries that are much slower. Based on the ZPAQ library, there is a good benchmark here:
The following comparison is from the 10 GB benchmark (10 GB in 83,437 files and directories) using default settings on a Core i7 M620, 2.66 GHz, 4 GB backup to an external USB hard drive in Ubuntu Linux.
Archiver Size Compress Extract License
-------- ------- -------- ------- -------
zip 4844 MB 1206 sec 229 sec Free, open source with specification
rar 4493 MB 1423 sec 239 sec Commercial, unrar is free and open source
7zip 3892 MB 6593 sec 472 sec Free, open source
freearc 3711 MB 1448 sec 422 sec Free, open source
zpaq 3825 MB 379 sec 249 sec Free, open source with specification