Kolmogorov Complexity

Kolmogorov Complexity

One of the more theoretical ways to measure the “complexity” of a file is to compute the amount of space it takes to hold a computer program that would recreate the file. This is the same thing as asking what is the final size of a self-extracting archive created by the best compression function. This measurement is often used in some theoretical proofs about the limits of what computers can do.

The definition it self doesn' t offer many lessons on how to build compression  functions that actually work, but it does provide some inspiration. While all of the functions described in this book are self-contained, well deˇ ned, and pretty practical, there is no reason why there can' t be more programs that do a better job. 

For instance, imagine the ˇ lecontaining all 65,536 possible 16-bit numbers in sorted order. There is no statistical pattern that would be easily extracted by the algorithms in Chapter 2. Each number only occurs once, and all of the digits are used with close to the same frequency. Each 7 is just as likely to be followed by a 3 as a 5. In binary form, all of the bits occur equally often in each of the positions. None of the dictionary algorithms from Chapter 3 would do much good. The numbers aren' t repeated. But a program written with one loop could duplicate the entire list. 

The Kolmogorov complexity of a file is rarely used in practical settings. The number of different programs that could generate a particular output are so great that it is hard to check them all and determine which was the smallest. It also makes it difficult to write a program that will automatically find another program to simulate the data. In fact, it is really intended to be a theoretical construct. 

But the Kolmogorov complexity can serve as an inspiration to programmers. It should hold out the possiblity that more and more complicated descriptions and software packages should be able to extract more patterns from the data. Reducing these patterns should add more compression.

 

Tweet