Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the current state of text-only compression algorithms?

In honor of the Hutter Prize, what are the top algorithms (and a quick description of each) for text compression?

Note: The intent of this question is to get a description of compression algorithms, not of compression programs.

like image 988
Brian R. Bondy Avatar asked Oct 25 '08 14:10

Brian R. Bondy


People also ask

What are the 3 text compression methods?

There are three types of models: • static • semiadaptive or semistatic • adaptive. A static model is a fixed model that is known by both the compressor and the decompressor and does not depend on the data that is being compressed.

What is text compression in data compression?

Text Compression involves changing the representation of a file so that the (binary) compressed output takes less space to store, or less time to transmit, but still the original file can be reconstructed exactly from its compressed representation.

What is the most powerful compression algorithm?

At maximum compression level, ZIPX is the fastest format, followed by RAR, ARC, and 7Z, ZPAQ being the slowest. Using moderate compression settings, RAR and ARC emerge as the fastest formats.


2 Answers

The boundary-pushing compressors combine algorithms for insane results. Common algorithms include:

  • The Burrows-Wheeler Transform and here - shuffle characters (or other bit blocks) with a predictable algorithm to increase repeated blocks which makes the source easier to compress. Decompression occurs as normal and the result is un-shuffled with the reverse transform. Note: BWT alone doesn't actually compress anything. It just makes the source easier to compress.
  • Prediction by Partial Matching (PPM) - an evolution of arithmetic coding where the prediction model(context) is created by crunching statistics about the source versus using static probabilities. Even though its roots are in arithmetic coding, the result can be represented with Huffman encoding or a dictionary as well as arithmetic coding.
  • Context Mixing - Arithmetic coding uses a static context for prediction, PPM dynamically chooses a single context, Context Mixing uses many contexts and weighs their results. PAQ uses context mixing. Here's a high-level overview.
  • Dynamic Markov Compression - related to PPM but uses bit-level contexts versus byte or longer.
  • In addition, the Hutter prize contestants may replace common text with small-byte entries from external dictionaries and differentiate upper and lower case text with a special symbol versus using two distinct entries. That's why they're so good at compressing text (especially ASCII text) and not as valuable for general compression.

Maximum Compression is a pretty cool text and general compression benchmark site. Matt Mahoney publishes another benchmark. Mahoney's may be of particular interest because it lists the primary algorithm used per entry.

like image 59
Corbin March Avatar answered Sep 17 '22 12:09

Corbin March


There's always lzip.

All kidding aside:

  • Where compatibility is a concern, PKZIP (DEFLATE algorithm) still wins.
  • bzip2 is the best compromise between being enjoying a relatively broad install base and a rather good compression ratio, but requires a separate archiver.
  • 7-Zip (LZMA algorithm) compresses very well and is available for under the LGPL. Few operating systems ship with built-in support, however.
  • rzip is a variant of bzip2 that in my opinion deserves more attention. It could be particularly interesting for huge log files that need long-term archiving. It also requires a separate archiver.
like image 35
Sören Kuklau Avatar answered Sep 20 '22 12:09

Sören Kuklau