Open-Source Articles
Compression Programs for Chess Programmers and Tournament Directors
by Ron Murawski © 2006
Introduction
Chess is a hobby which invariably leads to mountains of data. Larger-sized PGN collections tend to be in multi-megabyte sizes. The most popular way to squeeze down the sheer size of the data is to compress these files using the Zip format. Zip is quick, convenient, and seems to do a great job. But... What if I told you that zip files are not very good at compressing data?
If you actually test it, you will find that the Zip method of compression rates near the bottom of the list of the many archiving programs that are available! It turns out that Zip is optimized for execution speed only. Zip's compression is woeful by comparison to better compression programs. So, what are these better archiving programs? They have names like 777, 7-ZIP, ACB, ARI, BOA, BZIP, COMPRESSIA, DURILCA, ENTROPY, IMP, SBC, and ZZIP. Never heard of them?
Most of these programs are somewhat experimental in nature and are available at the renowned Elf Stuba ftp site. This site allows a limited amount of simultaneous anonymous users so you may have to try repeatedly before you finally connect. Many of the same programs plus a few more can be downloaded from SAC. Some of the programs are available in source code form -- these are mostly GNU "copyleft" programs. Some are commercial efforts and are offered as shareware. Hint: When running an unfamiliar commandline compression program always type "<program_name> -help" so you can find out how to use it.
Believe it or not, but compression programs have become a hotbed of refinement using older ideas in new ways. Almost all create "solid" archives and call older archives "hollow". The truly curious can visit DataCompression.info. There you can read doctoral theses on the subject or download source code and libraries. It's an almost endless listing of people, conferences, and information devoted to compression.
Most lossless compression programs use run-length encoding (RLE) and/or Huffman coding, which is a specialized form of arithmetic coding, in some part of their algorithms. After that the programs diverge, using either some form of LZ compression (Limpel-Ziv), Burrows-Wheeler Transform (BWT, also called block-sorting compression), or PPM (Prediction by Partial Matching). There are many other compression methods but the others are usually specialized and not good for general use. As a rule of thumb LZ seems to do well compressing exe files, BWT excels at large files with repetitions, and PPM does best compressing predictable data.
I've done some experiments that are aimed at finding the "best" compressor for chess authors and tournament directors. This is my set of rules of what constitutes a "best" compression program:
- It must compress reasonably well
- It must compress/decompress in a reasonably fast time
- It must be convenient for an average user to decompress the file
Rule (1) is self-evident. I'm assuming that you have a website with files that are available for public download. You will want the compression to be very good. Many web hosts limit the total number of bytes transferred per day or per month. Going over the limit will either shut down your site temporarily or it can mean a larger bill to pay at the end of the month. Other hosts charge extra if your files get over a certain-sized quota -- exceed the quota and your monthly payment will be larger. The smaller the size of your files the better off you are.
A good example of a program that violates rule (2) is the PAQ program. You can brew a pot of coffee and bake some muffins while waiting for it to compress a single large file, but the resulting file may very well be the smallest compressed archive you have ever seen. Rule (2) is a yes/no item for me -- it's either "fast-enough" or it's not.
Rule (3) is the controversial one. "Convenient for the average user" -- hmmmmmmm. What that means to me is that there must be an easy way for a user to decompress the file. It must have either an easy-to-use GUI program or, the compressor must be able to create a self-extracting exe file that, when run, decompresses itself automatically. I also don't like shareware programs -- every time I'm forced to use WinRar I feel guilty for using it beyond its 40-day evaluation period.
Running various benchmarks and following the above rules left me with just three programs to choose from. All the others failed at least one of the rules. For informational purposes I will include some other popular programs and some others that just seem to compress chess files really well.
The PGN Test
I decided to compress a huge pgn file. The original size was 219,033 KB, or about 214 megabytes. PGN files are highly repetitive and predictable -- compression programs do especially well with them. The maximum compression option was used throughout all tests except for SBC where maximimum compression took much too long.
| Program | Method | Time (mm:ss) | Size (KB) | % Orig Size | Comment |
|---|---|---|---|---|---|
| 7-Zip | PPMD | 2:25 | 36,989 | 16.89% | very good |
| 7-Zip | LZMA | 11:06 | 43,765 | 19.98% | too slow! |
| 7-Zip | BWT | 6:32 | 42,614 | 19.46% | slow |
| BZip2 | BWT | 1:48 | 42,620 | 19.46% | |
| Compressia | ??? | 2:16 | 39,717 | 18.13% | |
| Durilca Light | -t1 | 3:17 | 35,931 | 16.40% | best! |
| SBC | BWT | 2:25 | 37,892 | 17.30% | |
| WinRar | LZ77 | 2:37 | 37,972 | 17.34% | |
| Zip | LZ | 0:40 | 65,177 | 29.76% | worst! |
| ZZip | BWT | 2:24 | 40,947 | 18.69% |
First of all, please note that for the 7-Zip compression method I have used the true method name of BWT rather than the "BZip2 method" the program calls it. Also notice that the Durilca Light file is about *half* the size of the Zip archive: I warned you that file compression with Zip wasn't very good! 7-Zip PPMD does well here.
The WinBoard Engine Test
In the past I have always used Zip files for Horizon downloads. For this test I compressed the files from Horizon 4.3. Uncompressed there are 9 files that total 364 KB in size. The Horizon exe file is by far the largest being about 75% of the total size.
| Program | Method | Time (mm:ss) | Size (KB) | % Orig Size | Comment |
|---|---|---|---|---|---|
| 7-Zip | PPMD | 0:01 | 168 | 46.15% | |
| 7-Zip | LZMA | 0:02 | 157 | 43.13% | good |
| 7-Zip | BWT | 0:02 | 181 | 49.73% | |
| BZip2 | BWT | 0:01 | 185 | 50.82% | |
| Compressia | ??? | 0:01 | 166 | 45.60% | |
| Durilca Light | -t1 | 0:04 | 143 | 39.29% | best! |
| SBC | BWT | 0:01 | 161 | 44.23% | good |
| WinRar | LZ77 | 0:01 | 167 | 45.88% | |
| Zip | LZ | 0:01 | 186 | 51.10% | worst! |
| ZZip | BWT | 0:01 | 178 | 48.90% |
Notice that the Durilca Light file is about 3/4 the size of the Zip archive. Zip compression is again the worst but the slight size savings are perhaps not worth switching away from it.
The Crafty Book Test
I have a Crafty book, book.bin, that is 72,702 KB in size. Opening books are not as predictable nor as repetitive as PGN files.
| Program | Method | Time (mm:ss) | Size (KB) | % Orig Size | Comment |
|---|---|---|---|---|---|
| 7-Zip | PPMD | 1:54 | 31,425 | 43.22% | |
| 7-Zip | LZMA | 2:07 | 25,067 | 34.48% | very good |
| 7-Zip | BWT | 2:36 | 31,272 | 43.01% | |
| BZip2 | BWT | 0:36 | 31,612 | 43.48% | |
| Compressia | ??? | 0:52 | 25,489 | 35.06% | very good |
| Durilca Light | -t1 | 3:12 | 32,129 | 44.19% | worst! |
| SBC | BWT | 1:45 | 24,842 | 34.17% | best! |
| WinRar | LZ77 | 0:53 | 28,144 | 38.71% | |
| Zip | LZ | 0:48 | 29,282 | 40.28% | |
| ZZip | BWT | 0:50 | 30,637 | 42.14% |
Finally! A test where Zip compression does not finish last... The best compressor's size is 85% of Zip's size. Durilca falters badly and, once again, one of the 7-Zip methods finishes as near-best.
Comparing Compressors
First of all some general observations and comments:
- 7-Zip: never use the BZIP2 option (using BWT method) to compress a file -- it gives comparible-size archives as the genuine BZip2 program but runs about 4 times slower
- Durilca Light results are very inconsistent. It's either the best or the worst.
- ZZip seems to be an improved version of BZip2, squeezing out more using block-sorting (BWT) than BZip2 can manage, but taking longer.
- SBC is even better than ZZip. It would be a program of choice if it had a GUI interface or could create self-extracting archives.
- Compressia, with a Windows GUI and an option to create a self-extracting archive, would have been a program of choice if it was still available. The author has removed it from his website and it is no longer supported.
One way to view the results is to present the list of programs along with the average compression and totalling the amount of KB saved on the 3 tests:
| Program | Avg reduction | KB saved vs Zip |
|---|---|---|
| 7-Zip | 31.50% | 32,432 |
| SBC | 31.90% | 31,750 |
| Compressia | 32.93% | 29,283 |
| Durilca Light | 33.29% | 26,442 |
| WinRar | 33.98% | 28,362 |
| Zzip | 36.58% | 22,883 |
| BZip2 | 37.92% | 20,228 |
| Zip | 40.38% | 0 |
The last column is interesting -- Yes, it's true: storing 7-Zip files instead of Zip files would save about 32 MB of space! Now: Which are the programs that can pass the three rules? Certainly not Zip because the compressed files are much too large compared to the others. Not Compressia because the program is no longer available. Not BZip2 nor Durilca Light nor SBC because they all require commandline arguments that might confuse a non-technical person. Zzip also requires commandline args but it can create a self-extracting exe file. In the final analysis, we are left with three candidate programs as "best". 7-Zip, WinRar, and ZZip. What are the pros and cons of using these three?
ZZip
ZZip is a good block-sorting compression program; it always seems to outperform BZip2. The biggest drawback to using ZZip is that you need to deal with a commandline interface. But if you are reading this, you are either a programmer or a tournament director and this should not dissuade you. This is an open-source project with a nice source code library that can be included in C programs. Two programs need to be run to create self-extracting files: Zzip.exe creates the archive, then Zzip-sfx.exe prepends the extractor. Keep in mind that any self-extractor contains not only the compressed archive, but the code for the decompressor as well. For ZZip this is about 27 KB of overhead which may be (or may not be) fairly small in comparison to the total archive size.
WinRar
I've said it before and I'll say it again -- I feel guilty when I use WinRar because I didn't pay for it. It's nagware so the first splash screen always reminds me that I *really* should purchase the program. If you can get past the guilt you'll find a very professional GUI interface that's as easy to use as any. It has a good compression engine as well: it's not the best, but it's in the respectable range. But, in all my tests, both 7-Zip and SBC out-performed it. If you decide to put Rar files on your website you are forcing others to use WinRar and perhaps bothering their consciences as well. (There is a free commandline UnRAR available, but I disqualify it from consideration because of the difficulty it would cause the average user.) The only ethical solution I see is to buy the program and use it to create self-extracting files. (The self-extracting option adds about 46K to the size of the archive.) Then your users can feel relief.
7-Zip
7-Zip has a nice, easy-to-use GUI interface. It also adds a 7-Zip sub-menu to the normal Windows menu that pops up when right-clicking on a file. Using the right-click or the GUI makes it easy to create or extract an archive. The only downside is that 7z files are rarely encountered and posting a link to the 7-Zip site is mandatory so people who download 7z files can decompress them. 7-Zip can create a self-extracting exe file which may be preferred by users to the 7z format, but it will cost an extra 129K of overhead. 7-Zip is an open-source project. When creating an archive, the encoding method must be chosen. Each method excels at compressing certain types of files. A few experiments will quickly reveal the best compression method. There is a source code library, but it's only for the LZMA method of compression.
Conclusion
7-Zip is the winner of my compression contest. Among the three finalists it produced the smallest files when all three tests were combined. 7-Zip's compression is so good and the Windows program GUI interfaces so clearly designed and easy-to-use that it is my compelling choice as the best chess-related compression program. Did I mention that it can also encode/decode plain old Zip files, BZip2 files, and WinRAR files as well?
Disclaimer
I don't claim to be an expert in compression, so if you find an error on this page, please email me and I will correct it. If you have a favorite compressor that you feel is superior to those mentioned, please email me and tell me about it; if it is comparable to the top three programs, I will add it to this page.
If you find an error, a bad link, or just want to comment, please email Ron Murawski