3.5 信息论与数据压缩
上面这些简单的例子说明，在谈到信息论和熵时，还是有一些回旋的空间的。需要记住的是，熵定义的只是在对数据流进行编码时，每个符号平均所需的最小二进制位数。这就意味着，有些符号需要的二进制位数比熵小，而有些符号需要的二进制位数则比熵大。
数据压缩算法的艺术，就在于真正试图去突破熵的限定，或者说是将数据转换成一种熵值更小的、新的表现形式。这可以说是真正的舞蹈：信息论已经制定了相应的规则，数据压缩则以斗牛士的热情巧妙地避开了这些规则。
亲爱的读者，事实就是这样，这也是这本书的全部内容：怎样应用数据转换以创造熵更小的数据流（然后再用适当的方法进行压缩）。理解信息论与数据压缩之间的相互作用，将有助于你在当今这个信息世界更全面地看待这两者之间的相互协调与让步。
柯尔莫哥洛夫复杂性
正如前面所讨论的那样，在对压缩进行评价时熵不是一个好指标。
其实，还存在其他更准确的度量复杂性的方法，但这些方法在使用上还没有真正地标准化。
柯尔莫哥洛夫复杂性（Kolmogorov complexity），度量的是确定一个对象所需要的计算资源。它以数学家安德雷•柯尔莫哥洛夫（Andrey Kolmogorov）的名字命名，以纪念他在1963年发表了这方面的第一篇论文。
举个例子，考虑以下两个由32个小写字母和数字组成的字符串：
可以写一个简单的Python程序来生成第一个字符串：
< v = 'ab' * 16 >
注意，这个生成字符串的程序要比字符串本身小。作为一种有效的数据压缩方法，你完全可以把这段程序发送给某个人，然后让他运行程序重新生成源字符串。
而第二个字符串没有什么规律，生成它的程序要比源字符串大。因此，这样做谈不上压缩。
下面做一个简单的总结。
熵，指为了唯一地描述一段数据所需要做出的“是”“否”回答的次数。
柯尔莫哥洛夫复杂性，指为了准确地生成数据，所需要的生成程序的大小。
可以证明，任何字符串的柯尔莫哥洛夫复杂性顶多比字符串本身的长度大几个字节(基本上，也就是一个程序输出字符串的每个元素）。那些柯尔莫哥洛夫复杂性要比字符串本身小很多，就像上面的所举的abab的例子，可以认为这样的字符串都很简单。
当开始讨论用逻辑综合（logic synthesis）或者程序综合（program synthesis）进行数据压缩的时候，柯尔莫哥洛夫复杂性就开始真正起作用了，本质上它取的是数据集以及反向生成产生字符串的程序的二进制位流。
平心而论，这样的解释有些大而化之。熵远远算不上最佳解决方法，但它的确是很多人信任的“足够好的”度量标准。要找到一个更准确的解决方法，涉及对数据信息和分析空间的大量随机探索。这里，需要着重说明的是，虽然已有将近50年的历史，但是数据压缩作为一个学科仍然很年轻。不是所有的问题都有答案，而这才是你真正需要去努力探索的。