|
本论文题目：范式哈夫曼算法的分析与实现，作者：叶叶，于2010年10月14日在编程论坛上发表。页面地址：http://programbbs.com/bbs/view12-29332-1.htm 。 目录 1 前言 2 范式哈夫曼算法的分析与实现 作者：叶叶（网名：yeye55） 摘要：全面介绍了范式哈夫曼算法的理论基础和实现方式。详细讨论了编码位长计算、限制编码位长、解码优化、码表二次压缩等实现技术。并给出了一个切实可行的应用程序。 关键词：哈夫曼；范式哈夫曼；指数哥伦布编码；Delphi 中图分类号：TP301.6 1 前言 David A. Huffman于1952年第一次提出了哈夫曼（Huffman）算法[1]，该算法一经提出就引起了研究人员的广泛兴趣。哈夫曼算法使用变长前缀编码来压缩数据。对于出现次数较多的符号使用较短的编码表示，对于出现次数较少的符号使用较长的编码表示。哈夫曼算法的性能十分优异，即使在很糟糕的情况下都可以获得不错的压缩率。但是，哈夫曼算法也有许多缺点。例如：二叉树大量占用内存、码表过大、编解码速度过慢等等。 Eugene S. Schwartz于1964年提出了范式哈夫曼编码（Canonical Huffman Code）算法[2]。作为哈夫曼算法的一个重要的变体，范式哈夫曼算法解决了哈夫曼算法的许多不足之处。范式哈夫曼算法可以根据编码位长算出编码。这样输出的码表就大大的减少了，而且编解码过程不再需要二叉树结构。在提高编解码速度的同时，内存占用也大幅减少。 目前范式哈夫曼算法已经在数据压缩领域大量的应用。本文将详细的分析范式哈夫曼算法的理论基础和实现方式，并给出一个在Delphi 7.0下开发，使用范式哈夫曼算法压缩数据的应用程序。 2 理论基础 2.1 哈夫曼算法 范式哈夫曼算法是哈夫曼算法的一种变体。所以这里先对哈夫曼算法进行介绍，然后再推导出范式哈夫曼算法。 哈夫曼算法需要扫描两遍数据。第一遍扫描计算符号在数据中出现的次数（以下简称“频度”），然后根据符号频度构建一棵哈夫曼二叉树（以下简称“哈夫曼树”）。最后再次扫描数据将符号按哈夫曼树进行编码。例如：一份长度为38个符号的数据，其中一共出现8种符号，其频度如表2.1所示： 符号 A B C D E F G H 表2.1 符号频度 构建哈夫曼树的过程是这样的：首先建立一个由二叉树构成的森林，每个叶子节点保存一个符号和它们的频度。每个分支节点保存一个频度总计。刚开始的时候每个二叉树都只有叶子节点。然后对于森林中所有的二叉树，以根节点的频度作为关键字从小到大排序。排序完成后，将排名第1、2位的二叉树合并成一棵新的二叉树。具体做法是：新建一个根节点，将排名第1位的二叉树作为新节点的左子树，排名第2位的二叉树作为新节点的右子树，新节点的频度等于这两棵子树根节点的频度之和。合并完成后再进行排序，不断重复这个过程，直到所有节点都合并到一棵二叉树上。利用表2.1中的频度数据构建哈夫曼树的整个过程如图2.1所示。
图2.1第8步得出的就是哈夫曼树。现在可以对这棵哈夫曼树分配编码。一般采用左0右1的分配方案，即：为左子树分配编码0，为右子树分配编码1。注意：如果只是单纯的使用哈夫曼算法，不管是采用左0右1还是采用右0左1都是可以正常编解码的。只要编码程序和解码程序都使用相同的编码方案就不会出现错误。但是，本文中要推导出范式哈夫曼算法，所以必需采用左0右1的分配方案。一棵分配了编码的哈夫曼树如图2.2所示。
根据图2.2中的哈夫曼树可以得到表2.2中的哈夫曼编码。哈夫曼算法编解码的过程其实就是查树的过程。编码一个符号时，先查找该符号对应的叶子节点；从叶子节点开始沿着父节点向上直到根节点；记录下路过每个节点的编码；最终得到的就是符号的哈夫曼编码。解码过程与之相反，从根节点开始；判断输入的位，为0时向左走，为1时向右走；当遇到叶子节点时就可以解码出一个符号。 符号 编码位长 哈夫曼编码 范式哈夫曼编码 表2.2 哈夫曼编码和范式哈夫曼编码 从上述的介绍中可以看出哈夫曼算法的一些缺点。首先，编解码过程都需要建立哈夫曼树。哈夫曼树是根据符号频度建立的。这就意味着编码输出的时候必需输出一份频度数据（以下简称“码表”）以便解码的时候可以重建哈夫曼树。这份码表将占用输出数据很大的一部分空间。其次，哈夫曼树将占用大量的内存。而且频繁查树的效率也不高。另外，哈夫曼编码具有不确定性。例如，前面讲到的左0右1的分配方案；再例如，在构建时采用稳定或不稳定的排序算法。这都会影响到最终输出的哈夫曼编码。范式哈夫曼算法就是为了解决上述缺点而提出的。 2.2 范式哈夫曼算法 范式哈夫曼算法采用了一个巧妙的方法对哈夫曼树进行了规范调整。首先，对于同一层的节点，所有的叶子节点都调整到左边。然后，对于同一层的叶子节点按照符号顺序从小到大调整。最后，按照左0右1的方案分配编码。图2.2中的哈夫曼树经过这样的调整可以得到一棵范式哈夫曼树（以下简称“范式树”）如图2.3所示。
根据图2.3中的范式树可以得到表2.2中的范式哈夫曼编码。将表2.2中的范式哈夫曼编码，按照以编码位长为第1关键字、符号为第2关键字进行排序，可以得到范式哈夫曼编码表。可以将相同位长的符号称之为同组符号。在同组符号之间的排序序号可以称之为同组序号。结果如表2.3所示。 序号 同组序号 符号 位长 编码 表2.3 范式哈夫曼编码表 观察图2.3和表2.3可以得出一些结论。第一，只要知道一个符号的编码位长就可以知道它在范式树上的位置。这就意味着在码表中只要保存每个符号的编码位长即可。编码位长通常要比符号频度小很多，所以码表的体积就可以减小很多。第二，相同位长的编码之间都相差1。例如，同组符号“A”、“D”、“G”的编码分别为“00”、“01”、“10”。而且，相邻的不同位长的编码，对齐后的高位相差1低位补充0。例如“H”和“B”的编码分别为“110”和“11100”，高3位相差1，补充2位0。这就意味着编码可以根据位长计算出来。编解码的过程可以根据计算出来的编码表进行，从而加快了编解码的速度。第三，根据以上两点可以发现，在编码的过程中，不必再建立范式树。只要模拟哈夫曼树的构建，计算出符号的编码位长即可。这样可以加快编码速度，同时又能减少内存的占用。 可以看出，范式哈夫曼算法解决了哈夫曼算法的许多不足之处。以下就来讨论范式哈夫曼算法的具体实现。 3 计算编码位长 先说排序算法。前面讲到哈夫曼树的构建过程，其实就是从一个有序表中删除两个最小的元素，再插入一个新的元素。在这种情况下使用堆排序算法（Heap Sort）可以获得不错的性能。另外，由于只要计算编码位长，可以使用一个数组模拟构建哈夫曼树的过程。Alistair Moffat在书中描述了一种计算哈夫曼编码位长的算法[3]（以下简称“M算法”）。设n为符号的信息量（Content），M算法使用了一个2n大小的数组。利用数组的左边保存一个最小堆结构，利用数组的右边保存符号频度。在这个数组中进行数据整理，可以模拟出构建哈夫曼树的过程。并且计算出编码位长。M算法不仅节约内存，其运行效率也相当不错。下面就来介绍这种算法。 在我们的例子里一共出现了8种符号，所以n = 8。可以使用下面的代码建立一个具有2n个元素的数组Buf。 Buf : array [0 .. (2 * n) - 1] of Cardinal; 假设符号“A”的序号为0、“B”的序号为1、……、“H”的序号为7。先将“A”到“H”的符号频度依次放入数组Buf的n到2n - 1位置。Buf的左边用来建立一个最小堆结构。左边的每个元素都保存一个指向右边元素的索引。对Buf的n到2n - 1元素遍历一遍就可以构建起一个最小堆，构建完成后的数据如图3.1 1)所示。
根据最小堆的原理，Buf[0]就是最小的一个元素。将Buf[0]移动到堆的末尾，这里是Buf[7]。然后重新整理堆，结果如图3.1 2)所示。再执行一次上述操作，结果如图3.1 3)所示。这样，我们就有两个需要合并的节点Buf[7]和Buf[6]对应Buf[9]和Buf[12]。将Buf[9]和Buf[12]相加保存到Buf[7]中，Buf[9]和Buf[12]分别保存对于Buf[7]的索引7。此时Buf[7]中已经保存了频度之和，将Buf[7]重新放入堆进行整理。过程如图3.1 4) 5)所示。重复这个过程，直到堆中只剩下一个元素，如图3.1 6)所示。 可以看出，整理完成后Buf的1到2n-1已经保存了一棵哈夫曼树。Buf[1]就是根节点，后续元素保存一个指向父节点的索引。由于子节点的编码位长肯定等于父节点编码位长加1。所以可以用一个简单的公式算出节点的编码位长：Buf[i] = Buf[Buf[i]] + 1。将Buf[1]设为0。对Buf的2到2n - 1元素按上述公式遍历计算一遍，就可以得到编码位长。如图3.1 7)所示。 自此，符号“A”到“H”的编码位长就保存到Buf的n到2n - 1位置上。 4 编码 当符号的编码位长计算出来之后，就可以根据位长为符号分配编码。现在先对表2.3中的数据进行统计。计算出相同位长的符号数量。以及相同位长中第一个符号的编码（以下简称“首编码”）。结果如表4.1所示。 编码位长 首编码 符号数量 表4.1 位长表 综合分析表2.3和表4.1中的数据可以发现一些规律。每个首编码都等于上个首编码加上对应的符号数量，再左移相差位。例如，“110”等于“00”加上3再左移1位。在同组符号之间，符号编码等于首编码加上该符号的同组序号。例如，在编码位长为5的符号中“E”的序号是2。“E”的编码“11110”等于“11100”加上2。 在实现的时候，由于前面计算完编码位长后Buf的0到n - 1位置已经不再使用。这时可以用这部分的空间来保存编码。注意：这里有一个前提，编码的位长不会超过32位。因为数组Buf使用Cardinal类型保存数据。 分配编码的过程是这样的。首先，对Buf的n到2n - 1位置的位长数据扫描一遍。计算相同位长的符号数量；以及符号的同组序号。符号数量可以新建一个数组保存，同组序号可以保存到Buf的0到n - 1位置。接着，根据符号数量计算出首编码。然后，对Buf的n到2n - 1位置的位长数据再扫描一遍。根据首编码和符号的同组序号计算出符号编码，保存到Buf的0到n - 1位置。 这样当范式哈夫曼算法第2遍扫描数据，进行编码的时候。就可以从Buf中直接获得编码以及编码位长。例如，符号“A”的编码就保存在Buf[“A”]中，编码位长就保存在Buf[“A”+ n]中。 5 解码 5.1 正常解码 编码过程中的符号编码是根据一定的规律计算出来的。解码过程就相当于编码过程的逆运算。在解码之前需要根据编码位长建立一份解码表。如表5.1所示。 序号 编码位长 首编码 符号数量 符号索引 表5.1 解码表 表5.1与表4.1类似，只是多了一个符号索引。符号索引对应于表2.3中的序号。例如，编码位长为5的符号，在表2.3中从序号4开始。那么表5.1中对应符号索引就等于4。在解码的时候不仅需要表5.1中的数据，还需要表2.3中经过排序的符号列表。 一般情况下，编码位长会和压缩数据一起保存。解码时先从压缩数据中提取符号的编码位长。然后，可以使用基数排序算法（Radix Sort）计算符号列表。同时计算出表5.1中的相关数据。具体过程同分配编码时类似，这里就不再重复。 建立完解码表就可以开始解码了。首先，设i = 0，从解码表的第i行开始。根据编码位长从数据中读取相应长度的位。将读取数据与首编码相减，假设差值等于Num。如果Num大于等于符号数量，那么将i加1重新开始整个过程。如果Num小于符号数量，那么将符号索引加Num从符号列表上的对应位置解码出一个符号。 例如，输入数据“11110”。令i = 0，此时编码位长为2。读取2位的数据“11”与首编码相减等于3。3大于等于符号数量，于是i = i + 1等于1。此时编码位长为3。读取3位的数据“111”与首编码相减等于1。1大于等于符号数量，于是i = i + 1等于2。此时编码位长为5。读取5位的数据“11110”与首编码相减等于2。2小于符号数量，2加符号索引4等于6。从表2.3中可以查到序号为6的符号是“E”。从而解码出符号“E”。跳过当前已经解码的5位数据，可以重新开始解码下一个符号。 由于前面编码的时候假设了一个前提，即：编码位长不会超过32位。那么在实现的时候，可以使用32个元素的数组保存表5.1中的数据。其中编码位长隐含在数组中可以被省略。另外，解码的时候可以声明一个Cardinal类型的变量，一次性读取32位的数据。在相减的时候，可以根据当前的编码位长将变量右移再相减。这样就不用一点一点的读取位数据。 5.2 优化解码 从解码的过程可以看出，解码最重要的问题就是判断编码位长。上述解码算法需要从最小的编码位长开始向下查找可能的编码位长。这种算法并不高效。一种比较简单的改进方案是建立一张k位的快速查询表（以下简称“快表”），其中k称为快表位长。k位的快表一共有2k个表项，每个表项保存一个符号和对应的编码位长。快表的序号对应于Num输入的编码。 快表的建立过程是这样的：对于编码位长小于快表位长的情况，快表序号高位与编码相同的表项都设置为相应的符号。对于编码位长等于快表位长的情况，快表序号与编码相同的表项设置为相应的符号。对于编码位长小于快表位长的情况，快表序号与编码高位相同的表项设置为相应的起始符号。在我们的例子中使用4位快表的情况，如表5.2所示。 序号 二进制序号 符号 编码位长 编码 表5.2 快表 注意，快表中只保存符号和编码位长两项。使用快表解码时，先读取k位的数据。直接将数据作为索引在快表中查询。如果对应表项的编码位长小于等于快表位长，则直接解码出符号。如果对应表项的编码位长大于快表位长，则从对应的编码位长开始，然后按照正常解码的算法进行。 例如，输入数据“01110”，先读取4位数据“0111”。查询快表，符号为“D”，编码位长为2。2小于4，此时可以直接解码出符号“D”。再例如，输入数据“11110”，先读取4位数据“1111”。查询快表，符号不确定，编码位长为5。5大于4，然后以编码位长为5开始，按照正常解码的算法进行。可以解码出“E”。 可以看出，快表能够提高解码速度。对于编码位长小于等于k的符号一次查表就可以解码出来。这些符号通常都是频度比较高的符号。即使查表出现编码位长大于k的情况，即：没有命中符号。也可以根据查到的编码位长缩短正常解码时查询的范围。 在实现的时候，如果对内存占用的要求很高，可以省略快表中的符号项。解码时先从快表中查到对应的编码位长，再根据编码位长进行正常的解码。这样速度会略慢一点。另外，在处理实际数据的时候，可以根据数据特点调整快表的位长。例如，将快表位长设为最大编码位长。在我们的例子里最大编码位长是5。这样解码每一个符号都只要一次查表。但是在最大编码位长较大的时候，这种方法会占用大量的内存。所以实现的时候还要根据实际情况调整。还有，在解码的时候同样可以一次性读取32位的数据。然后根据变量的高k位进行查表。 6 限制编码位长 在前面编解码的时候都假设了一个前提：编码位长不会超过32位。如果编码位长超过了32位，前面的编解码过程将会出现错误。那么哈夫曼编码位长最长可以达到多少？这是一个非常有趣的问题。学过算法的人都知道斐波那契数列，那么我们假设符号的频度恰好为一个斐波那契数列。符号对应的频度如表6.1所示。 符号 A B C D E F G H 表6.1 符号频度为斐波那契数列 其中符号“A”、“B”、“C”的频度都为1，“D”的频度为前3个频度之和。从“E”开始频度值为一个斐波那契数列。按照这样的频度生成的范式树如图6.1所示。
图6.1中的范式树可以被称之为单边范式树。注意将它与单边二叉树相区别。根据上述规律，假设信息量为n的符号，其哈夫曼编码位长理论上最长可以达到n - 1位。对于8位符号，信息量为256，其哈夫曼编码位长理论上最长可以达到255位。这是一个相当惊人的数据。但是这仅仅只是理论上的结果，我们还要考虑现实一点的问题。 当实际编码位长大于指定编码位长时称之为位长溢出。上面的例子中使用了8种符号以及一份46个符号的数据，让实际编码位长达到了7位。如果要让编码位长超过32位，就要使用34种符号。并构造一份长达12,752,042个符号的数据。这还只是一份人工数据。在现实的应用中，符号通常用来表示特定的信息。符号与符号之间也具有一定的关系。出现像表6.1那样的频度十分罕见。 当然，出现位长溢出的概率很低不等于不会出现位长溢出。解决位长溢出的方法无外乎两种，要么对计算出来的位长进行限制，要么采用无限制位长的编解码算法。很明显采用无限制位长的编解码算法会严重拖慢编解码的速度。那么只有采用限制位长的方法。 限制位长的方法也有两种，第一种方法是在计算编码位长之前对符号频度进行调整，使之不会出现位长溢出；另一种方法是在出现位长溢出后对位长进行调整，使之满足要求。限制位长肯定会影响到压缩率。第一种方法可以把压缩率的损失降到最低，第二种方法次之。但第二种方法的速度比第一种方法快很多，而且它只是在出现溢出的时候才进行调整。所以整体性能比第一种方法高。下面就来介绍第二种方法。 首先我们观察图2.3中的范式树，假设现在要将编码位长限制到4位。那么调整需要从最右边最下层的分支（以下简称“右下分支”）开始。根据哈夫曼树和范式树的规律，右下分支肯定是如图6.2所示的样式。
从图2.3中的范式树上查找小于第4层的最右边的叶子节点。可以看出这是符号“H”对应的叶子节点。将该叶子节点下放一层，形成一个分支节点。原叶子节点作为新分支节点的左叶子节点。将右下分支的左叶子节点作为新分支节点的右叶子节点。将右下分支的右叶子节点上提一层替换原右下分支节点。过程如图6.3 1) 2)所示。
上述的调整可以看出一个问题：右下分支的叶子节点应该是最下层的节点，占用最长的位。而该叶子节点却被调整到了较上层，占用较少的位。这样对于压缩率的损失较大。所以还要进行下优化调整。优化调整时遵循这样一个原则：在调整的时候，尽量保持符号原先的左右顺序不变。在满足上一条件的情况下，再按照范式树的规范进行调整。优化调整后的范式树如图6.3 3)所示。注意，由于此时调整还未完成，所以符号“H”排在了“B”和“C”的左边。这是按照原先的左右顺序排列。调整后又会出现一个右下分支，可以继续进行调整。直到所有的节点都不低于4层。最后调整完成的范式树如图6.3 4)所示。 当然，范式哈夫曼算法在实现的时候并没有生成一棵完整的树。那么调整就要在表2.3中的数据中进行。仔细观察表2.3中的数据可以发现，位于表末尾的两个符号就是要进行调整的右下分支。这就意味着可以在表中进行调整，以模拟出上述在树中调整的过程。注意，表2.3中的数据是经过排序的。 在表中调整位长的过程是这样的：首先，从表的末尾向上查找位长小于限制位长的序号。这里是序号3。将该位长加1，并设置倒数第二位的位长为该位长。然后将倒数第一位的位长减1。最后再对位长数据按大小整理。整理时要注意保持符号的顺序不变。原先序号6的位长被整理到了序号4。原先序号7的位长被整理到了序号5。这时可以判断末尾的位长是否大于限制位长。如果不大于，则调整完成。如果大于，就从原先序号3的下一位序号4开始向上查找位长小于限制位长的序号。并重复刚才的调整过程，直到末尾的位长小于等于限制位长。整个过程如表6.2所示。 序号 符号 位长 位长调整 表6.2 位长调整 可以看出在表中调整可以完美的模拟出在树中的调整，而且速度还更快。观察调整完的位长后可以发现，“B”、“C”、“E”、“F”的位长减小了，“H”的位长没有改变，而“G”的位长增加了。这说明该算法在控制压缩率损失方面并不优秀。但是，由于每次调整都是从较下层的节点开始。如果下层节点能够腾出足够的位置，对于上层节点将不会有任何影响。这意味着，虽然该算法在压缩率上会有损失，但仍然是可以被接受的。另外，由于只是在出现位长溢出的时候进行调整。对于没有溢出的压缩来讲，将不会有任何影响。 7 码表二次压缩 7.1 指数哥伦布编码 一般情况下，码表数据会和压缩输出数据一起保存。范式哈夫曼算法只需要保存编码位长数据。位长已经限制在了32。考虑到有的符号没有出现，它们的位长为0。那么，位长数据的范围就在0至32之间，每个位长数据需要6位的空间。假设8位符号总共输出256个位长数据，需要占用192个字节。如果使用16位符号，则需要占用49,152个字节。所以，对于位长数据进行再次压缩还是很有必要的。 从前面几节的描述中可以发现，位长数据都是一些数值比较小的数据。对于这种数据使用指数哥伦布编码（Exp-Golomb Coding，以下简称“EG编码”）压缩是比较合适的。Jukka Teuhola于1978年提出了EG编码[4]。EG编码也是一种变长前缀编码，它可以用来压缩非负整数的数值数据。EG编码利用较短的编码表示较小的数值，利用较长的编码表示较大的数值。EG编码还可以设定一个阶数k，根据待压缩数据的数值范围调整k，可以获得更好的压缩率。EG编码由前缀m (m≥0)个0、分隔符“1”、后缀m + k (k≥0)个位组成。数值0至9的EG编码如表7.1所示。 数值 k = 0 k = 1 k = 2 表7.1 指数哥伦布编码 对于位长数据的压缩，使用0阶的EG编码比较合适。0阶EC编码的编码过程是这样的：对于输入的数值数据，例如Num。先将Num加1，然后计算Num最高位的“1”位于第几位，将该数减1即是m。这相当于是在计算log2Num。最后输出m个“0”以及Num的低m + 1位。解码过程与之相反：先从输入数据中读取“0”，直到遇到“1”。计算总共读取了几个“0”，赋值给m。然后从“1”开始读取m + 1个位，赋值给Num。最后将Num减1，即可解码出数值。 EG编码可以有效的压缩数值数据，但是在实现的时候还有几个问题需要解决。首先观察表2.2中的编码位长数据。可以发现一点：数值较大的数据出现次数较多。比如位长5出现了4次。这是由于二叉树的性质决定的。对于一般的二叉树来说，下层叶子节点总是比上层叶子节点多。这就意味着，在位长数据中数值较大的数据占大多数。这将不利于EG编码压缩。解决方法是对位长数据进行调整。根据刚才分析的特点，可以用以下的公式对编码位长数据进行调整： 调整后数值 = 最大位长 - 当前位长 + 1 将表2.2中的位长数据按照上述公式进行调整，结果如表7.2所示。 符号 A B C D E F G H 表7.2 位长数据调整 虽然在我们的例子里，这样的调整没有得到很好的效果。但是在符号较多的位长表中，这样的调整可以让数据整体变小，并且让较下层的叶子节点使用较小的数值。这就可以充分发挥出EG编码的特点。 在实现的时候还有另外一个问题。在有些数据中，符号并没有完全出现。例如，对于8位符号总共有256种符号。在压缩英文文档或程序源代码的时候，全文中大约只出现了80至90种符号。有大量的符号没有出现，位长为0，如果直接保存也会占用大量空间。这时可以用RLE（Run Length Encoding）算法压缩一下。RLE算法是利用数据和重复次数来替换重复的数据。由于在现实的情况下，不为0的位长重复的可能性很小。所以这里只对位长为0的数据进行压缩。具体做法是：如果遇到为0的位长就输出0，然后输出0重复的次数。即使为0的位长只出现了一次，也要输出一个0和一个1。一个例子如表7.3所示。 位长 5 8 0 6 5 0 0 0 0 7 表7.3 位长数据的RLE压缩 综上所述，在输出码表数据的时候，先输出最大位长。然后再依次输出调整后的位长数据。如果遇到为0的位长就输出0，然后输出0重复的次数。所有输出的数据都使用EG编码。在我实现的程序里，将该压缩方案称之为“G方案”。经测试，在使用8位符号的情况下。对于英文文档，码表可以压缩到大约60至80字节。对于出现符号较多的文档，码表可以压缩到大约110至160字节。 7.2 范式哈夫曼二次压缩 使用G方案可以看出一个缺点：虽然对位长数据进行了调整，但是这种调整不一定是最优的。按照G方案的调整，最底层的叶子节点使用最小的数值。但是最底层不一定是出现最多叶子节点的层。所以更好的方案是将位长数据使用范式哈夫曼算法再压缩一遍。这称之为二次压缩。二次压缩又会产生一份新的码表，称为二次码表。这份码表再使用G方案压缩。 可以根据当前最大位长为二次压缩的范式哈夫曼算法指定符号信息量。符号信息量等于最大位长加1。在我们的例子里可以设为6。即：位长数据只在0至5的范围内变化。另外，二次压缩同样使用RLE算法压缩为0的位长数据。但是，有一点需要注意。RLE算法需要输出重复次数。0位长出现的重复次数通常变化很大，特别是使用较多符号的数据中。所以重复次数不使用范式哈夫曼编码，而使用EG编码。 综上所述，在输出码表数据的时候，先根据最大位长建立范式哈夫曼编码器。扫描一遍位长数据，统计频度分配编码。随后用EG编码输出最大位长。接着用G方案输出二次码表。然后再依次用范式哈夫曼编码输出位长数据。如果遇到为0的位长就用范式哈夫曼编码输出0，然后用EG编码输出0重复的次数。在我实现的程序里，将该压缩方案称之为“H方案”。 现在使用卡尔加里语料库（The Calgary Corpus[5]）中的18个文件，进行H方案的码表压缩性能测试。测试分别使用8位符号和16位符号两种情况。测试输出码表压缩后的大小，占用多少位以及大约相当于多少字节。测试结果如表7.4所示。 文件 8位符号 16位符号 表7.4 码表压缩测试 注意，表7.4中的字节数据是由位数据直接整除8得到的。观察表7.4中的数据可以发现，在使用8位符号的情况下。对于英文文档或程序源代码，如“book1”、“progc”等文件，码表可以压缩到大约55至65字节。对于出现符号较多的文档，如“obj1”、“pic”等文件，码表可以压缩到大约100至120字节。 8 测试与分析 范式哈夫曼算法的实现程序在Delphi 7.0下开发，编译通过并调试正常。测试程序的计算机使用Intel 2.66GHz单核CPU，DDR400 512MB内存，Windows 2000 SP4操作系统。测试程序压缩文件的时候，将文件全部读入内存进行压缩。压缩后的数据再写入到文件中。解压缩的过程也是如此。算法计时的时候，读写文件的时间并没有计算在内。只计算单纯算法的耗时。另外，程序中使用API函数GetTickCount进行计时。按照微软官方的说法，该函数有15ms（15毫秒）的误差。 现在使用卡尔加里语料库（The Calgary Corpus[5]）中的18个文件，以及大型语料库（The Large Corpus[5]）中的3个文件，进行测试。测试结果如表8.1和表8.2所示。 文件 输入大小 输出大小 压缩率 bpc 编码耗时 解码耗时 表8.1 卡尔加里语料库压缩测试 文件 输入大小 输出大小 压缩率 bpc 编码耗时 解码耗时 表8.2 大型语料库压缩测试 以上测试数据中的压缩率以及bpc（Bit Per Char）采用以下公式进行计算： 压缩率 = ((输入大小 - 输出大小) * 100) div 输入大小 测试程序使用8位符号进行压缩，保存码表的时候使用了H方案，在解压缩的时候使用了8位快表。 观察测试数据可以发现，范式哈夫曼算法的速度还是很快的。对于数百KB的数据，无论是压缩还是解压缩耗时都在15ms左右。对于数MB的数据，耗时也保持在100ms左右。另外，范式哈夫曼算法的压缩率在同类算法中还是不错的。在同类算法中范式哈夫曼算法的综合性能最高。但是，范式哈夫曼算法也有许多不足之处。最大的缺点就是它需要扫描两遍数据。对于实时数据压缩，这个缺点是致命的。而且，从上一节的表7.4中可以发现，范式哈夫曼算法仍然需要输出一份码表。对于使用百万量级符号的数据，这份码表会占用很大的数据空间。 9 结束语 范式哈夫曼算法以其优异的性能被广泛的应用在数据压缩领域。本文详细介绍了范式哈夫曼算法的理论基础和各种实现技术的细节。并给出了一个切实可行的应用程序。希望本文能够对压缩算法的研究人员有所帮助。 参考文献 [1] David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, 1952, 40(9), 1098-1101. [2] Eugene S. Schwartz, Bruce Kallick, Generating a cannonical prefix encoding, Communications of the ACM, 1964, 7(3), 166-169. [3] Lan H. Witten, Alistair Moffat, Timothy C. Bell, 梁斌(译), 深入搜索引擎, 北京: 电子工业出版社, 2009, 44-51, 421-432. [4] Jukka Teuhola, A Compression Method for Clustered Bit-Vectors, Information Processing Letters, 1978, 7, 308-311. [5] The Canterbury Corpus, http://corpus.canterbury.ac.nz/descriptions/. 附录：项目说明 1 程序项目 本程序项目是论文《范式哈夫曼算法的分析与实现》（以下简称“《范》”）的配套程序。本程序项目同时作为免费开源程序进行发布。本程序项目中的代码无需任何授权或许可即可用于个人和商业目的。使用者一切后果自负。 本程序项目在Delphi 7.0下开发，编译通过并且调试正常。本程序项目提供了一个文件到文件的，范示哈夫曼算法的压缩程序。本程序项目中还提供了相关测试代码，以分析范式哈夫曼算法的运行过程。 本程序项目中的主要文件及相关说明如表1.1所示。 文件 说明 表1.1 项目主要文件说明 在程序项目中MemoryBuffer.pas和CanonicalHuffman.pas两个文件是核心文件。在这两个文件中实现了论文《范》中描述的所有算法。同时，这两个文件也可以独立使用。将这两个文件添加到其它项目中，调用其中的相关函数就可以实现数据压缩。 2 MemoryBuffer.pas文件 由于范式哈夫曼算法输出变长位的数据，所以我编写了这个单元文件，提供了位读写的可扩展缓冲区操作。在这个单元文件里我定义了一个缓冲区类型TMBBuffer。同时，我编写了一系列的函数，提供对这个类型缓冲区的读写操作。通过这些函数可以以字节为单位读写缓冲区，也可以以位为单位读写缓冲区。还可以把缓冲区中的内容导入或导出到文件中。向缓冲区写入数据时，如果缓冲区不足，这些函数还可以扩展缓冲区。另外注明一点。出于性能的考虑，这些函数在读写位时将缓冲区视为Cardinal类型构成的数组。读写位时从Cardinal元素的高位向低位读写。 这些函数中比较重要的有MBWriteBit和MBReadBit两个函数。MBWriteBit函数负责将Cardinal类型数据的指定位写入到缓冲区中。而MBReadBit函数负责从缓冲区中读取指定的位数据。在范式哈夫曼算法编解码的过程中，主要调用这两个函数完成位数据的读写操作。 另外两个比较重要的函数是MBEncodeEG和MBDecodeEG。这两个函数实现了0阶的EG编码（指数哥伦布编码）。MBEncodeEG可以将一个Cardinal类型的数值数据进行编码并写入到缓冲区中，MBDecodeEG可以从缓冲区中解码出一个数值数据。在进行范式哈夫曼算法的码表压缩时，主要调用这两个函数完成EG编码的输入和输出。 单元文件中还有许多其它函数。我在每个函数实现部分的开头，添加了相应的说明注释。有兴趣的读者可以到单元文件中查看，这里不再重复。 3 CanonicalHuffman.pas文件 我在这个单元文件里编写了范式哈夫曼算法的实现代码。在这个单元文件中一共定义了3个类。其中，TCHEncode实现了编码过程，TCHDecode实现了解码过程，TCHCoding提供了对TCHEncode和TCHDecode的简单封装。 TCHEncode类实现了范式哈夫曼算法的编码过程。注意，TCHEncode类不负责符号频度的统计工作。频度统计工作应该由调用TCHEncode类的代码完成。在TCHEncode类中的AllocCode方法实现了编码位长计算和编码分配两个过程。对应于论文《范》中的第3节和第4节。TCHEncode类中的LengthLimited方法实现了限制编码位长的过程。对应于论文《范》中的第6节。TCHEncode类中的SaveBitLenG和SaveBitLenH两个方法实现了码表二次压缩的过程。对应于论文《范》中的第7节。其中，SaveBitLenG使用G方案，对应第7.1节；SaveBitLenH使用H方案，对应第7.2节。TCHEncode类的其它方法说明见单元文件中的相关注释。 TCHDecode类实现了范式哈夫曼算法的解码过程。TCHDecode类中的Construct方法实现了解码表的构建和快表的构建两个过程。对应于论文《范》中的第5节。TCHDecode类中的LoadBitLenG和LoadBitLenH两个方法实现了码表解压缩的过程。对应于论文《范》中的第7节。TCHDecode类的其它方法说明见单元文件中的相关注释。 TCHCoding类实现了范式哈夫曼算法的编解码过程。TCHCoding类是对TCHEncode和TCHDecode的简单封装。TCHCoding类提供了一个缓冲区到缓冲区的压缩与解压缩过程。TCHCoding类中的Encode方法是以字节为单位从缓冲区中读取数据进行压缩，然后保存到另一缓冲区中。TCHCoding类中的Decode方法是从缓冲区中读取压缩数据进行解压缩，然后保存到另一缓冲区中。TCHCoding类中的Encode16和Decode16两个方法与上述两个方法类似。只不过这两个方法是以双字节（Word）为单位进行数据的压缩与解压缩。在Unit1.pas单元文件中的测试程序就是调用TCHCoding类中的相关方法完成文件压缩与解压缩的。 4 CanHuf_Debug.pas文件 本单元文件是在CanonicalHuffman.pas单元文件的基础上添加了测试数据输出代码。本单元文件中的基本功能与CanonicalHuffman.pas单元文件完全相同。除此之外，在调用本单元中的一些方法的时候，这些方法会向Unit1.pas单元中的Form1.Memo1输出测试信息。正是由于如此，本单元文件必需与Unit1.pas单元文件一同使用。 在本单元文件中，TCHEncode. AllocCode会输出分配编码表的内容。TCHEncode. LengthLimited会输出位长整理的整个过程。TCHEncode类中的SaveBitLenG和SaveBitLenH会输出码表压缩情况。TCHDecode. Construct会输出解码表和快表的内容。TCHDecode类中的LoadBitLenG和LoadBitLenH会输出码表解压缩情况。 在本单元文件中可以修改常量CH_MAXLENGTH，这个常量就是限制位长的大小。在测试的时候可以将这个常量调小，以观察TCHEncode. LengthLimited方法的调整过程。 在本程序项目中带有一个例子文件：示范数据.txt文件。这个文件中的数据与论文《范》中的例子相对应。其符号与编码的对应关系如表4.1所示。 符号 A B C D E F G H 表4.1 符号与编码对应关系 现在对该文件进行测试。在程序中选择“范式哈夫曼算法（8位符号测试）”算法。注意：由于采用H方案保存码表，输出信息会有两份。一份是数据压缩的编码表，一份是码表压缩的编码表。程序输出结果如下： ================================================================== 数据种数：8 数据种数：4 设定符号容量：6种 设定符号容量：256种 编码器内存占用：2080B ≈ 2KB ≈ 0MB 编码器内存占用：80B ≈ 0KB ≈ 0MB 操作完成，耗时：15 ================================================================== 数据种数：4 最大位长：3 快表位长：3 输入码表大小（G）：27位≈3字节 数据种数：8 最大位长：5 快表位长：5 输入码表大小（H）：107位≈13字节 解码器内存占用：1604B ≈ 1KB ≈ 0MB 解码器内存占用：484B ≈ 0KB ≈ 0MB 操作完成，耗时：47 比较文件： 叶叶 |
联系客服
