Data Compression Explained

Data Compression Explained, by Matt Mahoney, is for the reader who wants to understand how data compression works, or who wants to write data compression software.

Book Description

Prior programming ability and some math skills will be needed.

Data compression is the art of finding short descriptions for long strings. Every compression algorithm can be decomposed into zero or more transforms, a model, and a coder. Coding is a solved problem. Given a symbol with probability p, Shannon proved that the best you can do is code it using log2 1/p bits. An arithmetic coder does this efficiently. There is no general procedure for finding good models or prediction algorithms. It is both an art and a hard problem in artificial intelligence. There is (provably) no test to tell you if a string can be compressed or if a better model exists.

Book Download / View Details