Lossless data compression benchmark

Contents:

• Results
• Algorithms
• Test sets
• Compression programs
• Rules
• Questions & answers

Algorithms

Column "Alg" shows the dominant algorithm used in a compression program. Compression algorithms are explained in depth in an excellent online book Data Compression Explained so I won't repeat that here. I will only list some algorithms names and their abbreviations:

• CM = Context Mixing
• BWT = Burrows-Wheeler Transform
• LZ = Lempel-Ziv compressors family
• LZ77 = Lempel-Ziv variant 1, published in 1977
• LZ78 = Lempel-Ziv variant 2, published in 1978
• LZP = Lempel-Ziv Predictive
• LZW = Lemper-Ziv-Welch
• o<N> = order-N coding
• PPM = Prediction by Partial Matching
• ROLZ = Reduced Offset LZ

Please note that compression programs often combine multiple compression algorithms, filtering, transforms, etc so the dominant algorithm (or algorithms) is a subjective category and can also be a subject to interpretation and/ or discussion. Some algorithm families (like Lempel-Ziv) have multiple variants so concrete algorithm can be either named after the popular algorithm family it resembles or named with it's unique name.

Test sets:

• enwik8 & enwik9 are the test files used in Large Text Compression Benchmark created by Matt Mahoney.
• Calgary corpus is a set of test files created by Ian Witten, Tim Bell and John Cleary from University of Calgary and is currently avaiable here.
• Canterbury corpus is a set of test files created at University of Canterbury and is currently available here.
• Maximum Compression is a lossless data compression benchmark created by Werner Bergman. It has two benchmark modes - single file compression (SFC) and multiple files compression (MFC). In SFC files are compressed independently and only compression ratio is tracked. In MFC files are compressed all at once and additionally compression and decompression times are published and analyzed. Only files for SFC are public and are available here.
• Silesia compression corpus was developed by Sebastian Deorowicz et al. It is a much newer corpus than Calgary corpus or Canterbury corpus and aims to reflect data types in common use when creating the corpus.

Compression programs

• bzip

  bzip2 is a single file compressor with BSD-like license by Julian Seward. It popularized Burrows-Wheeler Transform as a means for compression. Its predecessor, bzip, was encumbered by patents due to use of arithmetic coding. bzip2 uses Huffman coding instead.

• cmix

  cmix is GPL-licensed file compressor by Byron Knoll. Is is based on PAQ series of compression programs, but greatly increases amount of processing per input bit. Recent versions include LSTM neural networks based models.

• CMV

  CMV is free, closed source file compressor by Mauro Vezzosi.

• COPY

  This is actually a no operation. Exists to show uncompressed file sizes.

• Info-ZIP

  Info-ZIP is a collection of portable software for handling of .zip archives. It has BSD-like license.

• PAQ

  PAQ is a series of GPL-licensed context mixing file archivers originally developed by Matt Mahoney and also improved by numerous contributors.

Rules:

• Results must be publicly verifiable. Compression programs must be free for personal use without expiration date (no trialware) and without registration. Publishing benchmark results must not be prohibited in program license.
• By default programs are ranked by compressed (enwik9 or all files) size + decompressor size. Decompressor size may be based on publicly available source code (if it exists) or executable size. Decompressor itself may be compressed to .7z format using LZMA compression or to .zip format using Deflate compression. Source form is denoted by placing (s) after decompressor size, executable form is denoted by placing (x).
• Decompressor must be self-contained. It must not rely on any data that is not contained in decompressor package. Any libraries that are not standard libraries or are not available in stock OS install must also be placed in decompressor package (in source or executable form).

Questions & answers

1. Q: How to measure speed and memory usage on Microsoft Windows?

   A: Look for latest version of ProcProfile here: encode.ru: Command Line Process Profiling Tool

2. Q: How to measure speed and memory usage on GNU/ Linux?

   A: Invoke /usr/bin/time -v <original command>. Time to be reported will be after Elapsed (wall clock) time and memory usage to be reported will be after Maximum resident set size (kbytes) (needs to be scaled to get usage in megabytes).