46 甘 肃 科 技 第26卷

编码为0001,c的编码为1,那么当遇到0001时,就不知道0001代表ac,还是代表b。出现这种问题的原因是a的编码是b的编码的前缀。由于Huffman编码为根结点到叶子结点路径上的0和1的序列,而一个叶子结点的路径不可能是另一个叶子结点路径的前缀,所以一个Huffman编码不可能为另一个Huffman编码的前缀,这就保证了Huffman编码是可以区分的。2.3 使用Huffman编码进行压缩和解压缩

为了在解压缩的时候,得到压缩时所使用的Huffman树,我们需要在压缩文件中,保存树的信息,也就是保存每个符号的出现次数的信息。

压缩:读文件,统计每个符号的出现次数。根据每个符号的出现次数,建立Huffman树,得到每个符号的Huffman编码。将每个符号的出现次数的信息保存在压缩文件中,将文件中的每个符号替换成它的Huffman编码,并输出。

解压缩:得到保存在压缩文件中的,每个符号的出现次数的信息。根据每个符号的出现次数,建立Huffman树,得到每个符号的Huffman编码。将压缩文件中的每个Huffman编码替换成它对应的符号,并输出。

根据符号的出现次数,建立Huffman树,通过Huff

man树得到每个符号的新的编码。对于文件中出现次数较多的符号,它的Huffman编码的位数比较少。对于文件中出现次数较少的符号,它的Huffman编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。

建立Huffman树:

把所有符号看成是一个结点,该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树。每次从所有树中找出值最小的两个树,为这两个树建立一个父结点,把这两个树和它们的父结点组成一个新的树,新树的值为它的两个子树的值的和。如此往复,直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树。

通过Huffman树得到Huffman编码:

Huffman树是二叉树,它的所有叶子结点就是所有的符号,它的中间结点是在产生Huffman树的过程中不断建立的。我们在Huffman树的所有父结点到它的左子结点的路径上标上0,右子结点的路径上标上1。现在我们从根节点开始,到所有叶子结点的路径,就是一个0和1的序列。我们用根结点到一个叶子结点路径上的0和1的序列,作为这个叶子结点的Huffman编码。

例如:有一个文件的内容如下:abbbbccccddde

统计各个符号的出现次数:

a(1),b(4),c(4),d(3),e(1)

建立Huffman树的过程如图1

所示。

3 LZ77算法

LZ77算法是字符串匹配的算法。例如:在一段文本中某字符串经常出现,并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。

例如,在上一段短语 字符串 经常出现,可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。

一个字符串引用通过下面的方式来表示:*唯一的标记*偏移数量*字符串长度

由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选,因为它允许编码器用引用的大小来交换字符串的大小(例如,如果字符串相当长,增加引用的长度可能是值得的)。3.1 LZ77算法原理

LZ77是AbrahamLempel在1977年发表的无损数据压缩算法。LZ77算法是基于字典的编码器。LZ77算法通过使用编码器或者解码器中已经出现图1 建立Huffman树的过程

通过最终的Huffman树,我们可以得到每个符号的Huffman编码。

a为110,b为00,c为01,d为10,e为111。Huffman树使用变长编码。对于变长编码,可能会遇到一个问题,就是重新编码的文件中可能会,