文本压缩理论简介

 

以前认为压缩软件很神奇，很大的东西可以压缩到很小，甚至有时压缩比很惊人，但是一直都不清楚其理论是什么。很多人可能也都会有这样的疑问，所有的文件都可以压缩吗，压缩的极限又是什么？带着这样的问题，我对压缩的理论进行了一些了解。

简单来说，压缩就是用较少的数据来表示较多的数据，可是为什么可以这样表示呢。本文主要讲述文本的压缩，就用文本来举例，在前文出现过的东西在后文中出现的可能性会比没出现过的可能性大，在一部小说中，书中的人物将会多次出现，在一段代码中，同一个变量名可能也会多次出现。同一段数据出现了多次，就存在信息的冗余，那就可以进行压缩。

本文的很多内容都跟信息论有关，先来说一点信息论的概念。信息是文件所包含的有效内容，就是通过文件我们能知道的东西。我们用信息量来表示一个文件中包含信息的多少。

压缩分为有损压缩和无损压缩。顾名思义，文件经过有损压缩后信息量将会减少，不可还原到原来的状态，而无损压缩后文件包含的信息量不会减少，可以再进行解压缩。前者主要用于图片和视频的压缩，虽然信息量减少了，但是还是可以使用的，因为原画质的图片和视频太大了，经过有损压缩后，文件大小会减少很多很多，对于上传和下载更加方便。后者主要用于文本的压缩，在需要时，再进行解压缩，解压出的文件内容与原文件完全相同。这两种压缩使用的技术大体上还是相同的，当然有损压缩还会牵扯一些其他学科的知识，本文的主要内容是无损压缩，这里也不再赘述。

有一点需要明确，没有普适的压缩算法，没有一种压缩算法可以压缩所有的文件，简单证明一下。对于大小为n的文件，一共有2n个，如果这些文件压缩之后都会变小，然而大小小于n的文件的数量只有2n-1，所以，不可能所有的文件都被压缩。在实际中，对于一般的压缩算法，适用于该压缩算法的文件经过压缩后，大小会明显减少，而很多文件经过压缩后，大小可能并不会减少，很多情况下反而还会增大。有些压缩软件在压缩前会检测文件类型，来选择合适的压缩算法对文件进行压缩，这样能取得不错的效果。

大家可能听说过哈夫曼编码，它就是对一个文件中的元素根据其出现的频率进行重编码，使得长度变小。一般的文本文件经过哈夫曼编码编码后，大小很可能会减少，但是一个成熟的压缩器又应该具备那些东西呢？编码器是其中一部分，还有一个重要部分是预测模型。预测模型用来在不知后文的情况下来预测后文的内容，而编码器就是用新的编码方式来表示原来的数据。一个单独的预测模型或一个单独的编码器都可对文件进行压缩，但是将他们结合起来才能达到较好的效果。（本段内容是对于无损压缩而言的）

举个简单的例子，现在有一串数字，数字之间都很接近，如下：

27 28 29 28 26 27 29 28 30 32 34 36 38

那么我们就可以使用后一个字符与前一个字符之差来表示后一个字符，这就是一个简单的预测模型，上述数字就可以表示为

27 1 1 -1 -2 1 2 -1 2 2 2 2 2

后面的数字都很小，就可以较少的位来表示这些数字了，当然这时候你也可以选择使用哈夫曼编码来对这些小数字进行编码。虽然很简单，但这也是一个完整的压缩算法。

接着来说信息论的一些理论，编码是有极限的。在信息论中有信息熵这样一个概念，跟信息量的概念基本相同，它是信息论的创始人香农提出的，他还给出了一个计算信息熵的公式，并把它定义为信息熵。公式这里就不列出来了，主要是通过个元素出现的概率来计算信息熵的。如果一个文件中各元素出现的频率基本相同，那么该文件的信息熵就会比较大，如果频率相差很大，那么信息熵就会比较小，但是一个文件的信息熵不会大于文件的大小。一个文件的信息熵就是对该文件编码所能达到的极限。

文件不可重复压缩。对于一个已经压缩过的文件，其内容已经相对随机，如果对其再进行压缩，并不会得到一个很好的结果，压缩后文件很可能会变大。一般来说可以进行压缩的文件，经过一次压缩后，基本也就可以了，也没必要重复压缩。

理论知识还是不要说太多的好，再说其他的我也不会了...不过，以上这些差不多也够了，后有什么需要的后面再说。