文本压缩技术

文本压缩是指用较少的位或字节来表示文本，这样将可以显著地减小计算机中存储文本的空间大小。通常说的“文本压缩”都是无损压缩。

简述为了存储和传输数据，减少数据所占用空间的大小是很有用的。完成这项工作的技术称为数据压缩。过去由于存储的局限性，需要进行数据压缩。现在，虽然存储容量不受限制，但由于要与他人共享数据，网络具有固有的带宽限制，定义了在固定时间内从一个地点传输到另一个地点的最大位数或字节数，因此也需要进行数据压缩。

压缩率说明了压缩的程度，是用原始数据的大小去除压缩后的数据大小。计算压缩率可以是位数、字符数或其他单位，只要这两个值采用的单位相同即可。压缩率是一个0到1之间的数。压缩率越小，压缩程度越高。

数据压缩技术可以是无损的，即解压缩后的数据没有丢失任何原始信息。数据压缩也可以是有损的，即在压缩过程中丢失了一些信息。尽管不希望丢失信息，但在某些情况下，丢失是可以接受的。在处理数据表示和压缩时，往往要在精确度和数据大小之间做出权衡。1

主要方法通信带宽是一种昂贵的资源。许多用户希望尽可能地减少传送的总“比特”数，即文本压缩。此外，文本压缩也有保密的意义。下面介绍实现文本压缩的主要方法。

1**．采用符号有限集合编码及替换方法**

实际应用中，报文中的许多数据项都可以用编码表示。如器材库的器材名称，设其为10个字符，采用ASCII码表示后，则一个器材名称占70位。若给器材进行编号，就可以大大压缩原器材名的比特数。如果有1万种器材，用14位二进制编码就足够了。这样使器材名由原来的70位压缩成14位。报文中其他数据项也可采用同样的方法进行压缩替换。此外很多场合可以采用一目了然的方式存储信息。如日期的存储，可写成正规的1989年6月1日，也可编写成89.6.1。可用应用程序来完成这种替换。

在很多情况下，如果是以人们都能“一目了然”的方式存储信息，势必包含有许多冗余的信息。常常利用程序来压缩冗余信息。

2．字符的可变长编码

一般的字符编码位数都是固定的。数据传输过程中，字符的出现概率分布悬殊很大，通常数字比字母出现的频率大，而数字0又占了很大的比例。在英文中，各字母出现的概率也不同，字母E出现的频率是字母Q的100倍。下面介绍一种更为紧凑的编码方式。它采用不同长度的位进行编码，对出现频率高的字符给以位数最短的编码——霍夫曼编码。

霍夫曼编码技术只适用于字符出现概率不同的场合，如果出现的概率相同，采用霍夫曼编码反而不利，字符的概率分布越不均匀，则效果越好。

实现霍夫曼编码的方法是把原来的字符作为存储器地址查询表，找出字的编码。因为存储器的位置长度是固定的，而编码是可变的，所以要用标志说明用哪些位。为了方便起见，可以根据霍夫曼编码理论对产生的最长编码进行压缩。最长的编码共17位，而实际使用时最大长度缩减到14位。解码也同样可以用查表的方法来处理。为节省存储空间，可采用树结构。

如果先将重复字符压缩，再使用霍夫曼编码，则压缩量还要增加。研究结果表明，利用霍夫曼编码，对规整的程序文本进行压缩，其压缩量为55%～57%;对目标文件进行压缩，压缩量为35%～45%。2

常见算法GZIPDeflate算法是同时使用了LZ77与哈夫曼编码的一个无损数据压缩算法，Gzip算法是以Deflate算法为基础扩展出来的一中算法。Gzip是一种数据压缩格式，一般情况下使用Gzip压缩可以达到70%左右的压缩率，例如你的网页是100K，压缩后可以达到30K左右。

GZIP只能指定源文件，目标文件的扩展名由GZIP确定。压缩文件的属性、时间等都保持不变。通常，新文件的扩展名改为.GZ，但如果源文件还有扩展名，则根据扩展名的长度确定。若扩展名有三个字符，则第三个字符用“Z”代替，否则扩展名加一字符“z”。对于Windows 95和Windows NT则是在文件名后直接加.GZ，而不管被压缩文件有没有扩展名。如果不喜欢使用GZIP的默认扩展名，也可自由定义。

GZIP最大的特点是高性能的压缩以及自由使用，而且被GNUI程(开发linux系统的)所开发的系统列为标准压缩程序。所以在网络上非常流行使用GZIP。3

HaffmanHuffman方法是多媒体信息压缩中经常采用的方法，它是一种不定常的熵编码方法，当由字符集{c1,c2,..,cn}构成的源信息中各字符出现频率(概率)不均匀时具有很好的压缩效果，我们希望，通过适当选择不定常的代码字，使平均码长尽可能小。

为了用不定量的代码字，同时又要避免译码时的不确定性，可以采用由二元树所定义的“前缀码”，所谓前缀码是一个代码字的集合，其中任一个代码字都不是另一个代码字的前缀(即前面一部分，如10是101的前缀)，显然，任一个二元树，每一结点的左右边分别赋标号值0，1，由于每个叶都有一条唯一的由根到叶的道路，从而对应一个由道路中各边标号形成的二进制代码字，显然，这些代码字构成前缀码，反之，由一个前缀码，也可以构造出相应的二元树，因此，要找一个使平均码长最小的的前缀码，可以找一个二元树，Halfman提出了一个根据频率p1,p2,..,pn找出一棵有n个叶的二元树，其对应的前缀码能使平均码长最小。不过按原来的算法所得的二元树不是唯一的，虽然它们彼此等价，即相应的前缀码平均码长是一样的，为了消除不唯一性，便于程序实现和用图来表示。4

LZ77算法LZ77(Lempel-Ziv-1977)是一个简单但十分高效的数据压缩算法，它与霍夫曼编码的思想完全不同。LZ77算法是一种字典式编码，由于所用的字典是由前面已处理过的一串字符所构成的，随着编码的进行，字典也不断地滑动，故取名为滑动窗口编码。文本窗口分成两个部分，第一部分为搜索缓存区(Search Buffer)，用于存放部分最近已编码的序列，即字典；第二部分为前视缓存区(Look-ahead Buffer)，一般要小一些，用于存放刚被读入但尚未编码的字符。

LZ77通过用小的标记代替数据中多次重复出现的长串来方法来压缩数据。与霍夫曼编码不同的是，其处理的符号不一定是文本字符，可以是任何大小的符号，但其通常选择一个字节的符号。5

LZ78算法LZ78算法仍是基于字典的，与LZ77算法一样，在压缩编码之初，所用的字典是空的，随着编码的进程，字典由已处理的文本逐步构成。但与LZ77算法的实现思路有本质的区别，LZ78算法放弃了窗口滑动的概念，采用树形结构组织字典，保存短语。字典的大小没有限制，凡是已出现过的短语都被收入在字典之中。编码输出的码字由两部分构成，即字典中短语的标号和紧跟在该短语之后的第一个字符的标号(或字符码)。与LZ77不同，不给出匹配字符串的长度，其长度可由算法本身的规则来确定。

在实现LZ78算法时，字典的构建和维护十分重要。LZ78算法用一棵多叉树存放字典，每个结点对应一个短语，即一串字符，并且被赋予一个固定的标号，码树的根结点是空字符(NULL)。LZ78算法开始压缩时从NULL开始构造字典。每读入源文件的一个字符就与字典已存放的短语逐一比较，如果与某一条目匹配，继续输入下一个字符，直至找不到匹配的条目为止。这时将最后找到的也是最长的匹配字符串的标号和未匹配的字符作为输入串的压缩码字输出，同时将匹配字符串和紧随其后不匹配的字符级联，构成一个新的短语，加入到字典中。5

PPM部分匹配预测(predictionbypartialmatching，PPM)技术采用字符有限上下文模型。PPM依赖于前面编码过的文本中已观察到的上下文，采用不同的上下文长度，而不是把上下文长度严格地限制为一种来作出预测，“部分匹配”就由此得名了。

PPM是一种混合有限上下文统计建模技术，即混合使用若干固定阶数的上下文模型来预测输入序列中的下一个字符的概率，而这种预测是根据自适应更新的频率计数实现的。该算法计算以前出现的上下文中信源符号发生的统计特性，然后用这些统计特性给序列中下一个位置上即将发生的符号分配码字，并使码字的平均长度最小。这就是说，给可能发生的符号要有比不太可能发生的符号分配更短的码字。某一符号在不同上下文下发生的概率分别存储，这样在处理一个符号时由于上下文的变化使得分配给该符号的编码有可能完全不同。6

应用文本压缩技术因为有无损、通用的独特优点，一部分算法还非常简单、容易实现，并且资源开销不大，所以得到了广泛的应用。对它的应用主要体现在以下三个方面。

1．软件上的应用

这是最活跃、最多样化的一类应用。

在UNIX操作系统领域，最早的通用压缩程序之一是COMPACT，但是它运行得太慢。后来有了比COMPACT运行更快、压缩更好的COMPRESS。

上世纪80年代，通过SQ程序，数据压缩首次进入了MS-DOS领域。后来ARC程序取而代之。ARC程序不但可以实现压缩，还可以对文件进行归档处理。接下来的有PKZIP、LHARC和ARJ等程序。以后发展出的程序一般都被广泛移植到了各种操作系统和硬件平台上。

2．硬件上的应用

数据压缩算法在硬件中实现具有高速的特点。LZW提出时就是被应用到磁盘的数据读写通道的硬件电路中的。而近来提出的新的数据压缩算法，一般具有较高的复杂度，不少作者都提出了它的硬件实现方案，充分利用现代先进的半导体技术提高算法的运行速度。而不少工业厂商都致力于用硬件产品的形式提供它们的数据压缩算法，例如IBM公司一直致力于开发ALDC系列高性能数据压缩专用芯片。

3．通信的应用

在数据传输之前先进行无损的压缩可以有效地节约通信带宽，加快传输速度。当然，能够这样做的前提是通信双方的压缩、解压缩算法必须相互成一对，因为这样才能保证实现正确的还原。美国的Stac电子公司用专用芯片实现的基于LZ77的压缩算法被“1/4英寸盒式磁带(Quarter Inch Cartridge)工业集团”接受为工业标准，得到了广泛的应用。7

本词条内容贡献者为:

吴晨涛 - 副研究员 - 上海交通大学