第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
范式哈夫曼编码.pdf
声明
目录
范式哈夫曼算法的分析与实现
1 前言
2 理论基础
2.1 哈夫曼算法
2.2 范式哈夫曼算法
3 计算编码位长
4 编码
5 解码
5.1 正常解码
5.2 优化解码
6 限制编码位长
7 码表二次压缩
7.1 指数哥伦布编码
7.2 范式哈夫曼二次压缩
8 测试与分析
9 结束语
参考文献
附录：项目说明
1 程序项目
2 MemoryBuffer.pas文件
3 CanonicalHuffman.pas文件
4 CanHuf_Debug.pas文件
声明
本论文题目：范式哈夫曼算法的分析与实现，作者：叶叶，于 2010 年 10 月 14 日在编
程论坛上发表。页面地址：http://programbbs.com/bbs/view12-29332-1.htm。本论文全文及相
关配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。
目录
1 前言.......................................................................................................................................2
2 理论基础...............................................................................................................................2
2.1 哈夫曼算法................................................................................................................2
2.2 范式哈夫曼算法........................................................................................................6
3 计算编码位长.......................................................................................................................7
4 编码.......................................................................................................................................9
5 解码.......................................................................................................................................9
5.1 正常解码....................................................................................................................9
5.2 优化解码..................................................................................................................10
6 限制编码位长.....................................................................................................................11
7 码表二次压缩.....................................................................................................................15
7.1 指数哥伦布编码......................................................................................................15
7.2 范式哈夫曼二次压缩..............................................................................................17
8 测试与分析.........................................................................................................................18
9 结束语.................................................................................................................................20
参考文献.................................................................................................................................20
附录：项目说明.....................................................................................................................20
1 程序项目.....................................................................................................................20
2 MemoryBuffer.pas文件 ...............................................................................................21
3 CanonicalHuffman.pas文件.........................................................................................21
4 CanHuf_Debug.pas文件 ..............................................................................................22
第 1 页 共 26 页
范式哈夫曼算法的分析与实现
作者：叶叶（网名：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 所示：
符号 AB
频度 10
1
C D E F G H
1
5
11
1
1
8
表 2.1 符号频度
第 2 页 共 26 页
构建哈夫曼树的过程是这样的：首先建立一个由二叉树构成的森林，每个叶子节点保存
一个符号和它们的频度。每个分支节点保存一个频度总计。刚开始的时候每个二叉树都只有
叶子节点。然后对于森林中所有的二叉树，以根节点的频度作为关键字从小到大排序。排序
完成后，将排名第 1、2 位的二叉树合并成一棵新的二叉树。具体做法是：新建一个根节点，
将排名第 1 位的二叉树作为新节点的左子树，排名第 2 位的二叉树作为新节点的右子树，新
节点的频度等于这两棵子树根节点的频度之和。合并完成后再进行排序，不断重复这个过程，
直到所有节点都合并到一棵二叉树上。利用表 2.1 中的频度数据构建哈夫曼树的整个过程如
图 2.1 所示。
1)
2)
3)
4)
5)
频度
森林
频度
森林
1
B
1
E
1
C
1
F
1
E
1
F
2
B
C
5
H
5
H
8
G
8
G
10
A
10
A
11
D
11
D
频度
森林
2
2
5
H
8
G
10
A
11
D
E
F
B
C
频度
森林
4
5
H
8
G
10
A
11
D
E
F
B
C
频度
森林
8
G
9
1
0
A
11
D
H
E
F
B
C
第 3 页 共 26 页
6)
频度
森林
10
A
11
D
G
17
H
E
F
B
C
17
21
7)
频度
森林
G
A
D
H
E
F
B
C
38
8)
频度
森林
G
A
D
H
B
C
E
F
图 2.1 哈夫曼树的构建过程
第 4 页 共 26 页
图 2.1 第 8 步得出的就是哈夫曼树。现在可以对这棵哈夫曼树分配编码。一般采用左 0
右 1 的分配方案，即：为左子树分配编码 0，为右子树分配编码 1。注意：如果只是单纯的
使用哈夫曼算法，不管是采用左 0 右 1 还是采用右 0 左 1 都是可以正常编解码的。只要编码
程序和解码程序都使用相同的编码方案就不会出现错误。但是，本文中要推导出范式哈夫曼
算法，所以必需采用左 0 右 1 的分配方案。一棵分配了编码的哈夫曼树如图 2.2 所示。
0
0
0
G
0
0
1
0
E
F
B
1
1
0
1
A
D
1
H
1
1
C
图 2.2 分配编码的哈夫曼树
根据图 2.2 中的哈夫曼树可以得到表 2.2 中的哈夫曼编码。哈夫曼算法编解码的过程其
实就是查树的过程。编码一个符号时，先查找该符号对应的叶子节点；从叶子节点开始沿着
父节点向上直到根节点；记录下路过每个节点的编码；最终得到的就是符号的哈夫曼编码。
解码过程与之相反，从根节点开始；判断输入的位，为 0 时向左走，为 1 时向右走；当遇到
叶子节点时就可以解码出一个符号。
符号 编码位长 哈夫曼编码 范式哈夫曼编码
A
B
C
D
E
F
G
H
10
01010
01011
11
01000
01001
00
011
2
5
5
2
5
5
2
3
00
11100
11101
01
11110
11111
10
110
表 2.2 哈夫曼编码和范式哈夫曼编码
从上述的介绍中可以看出哈夫曼算法的一些缺点。首先，编解码过程都需要建立哈夫曼
树。哈夫曼树是根据符号频度建立的。这就意味着编码输出的时候必需输出一份频度数据（以
下简称“码表”）以便解码的时候可以重建哈夫曼树。这份码表将占用输出数据很大的一部
分空间。其次，哈夫曼树将占用大量的内存。而且频繁查树的效率也不高。另外，哈夫曼编
第 5 页 共 26 页
码具有不确定性。例如，前面讲到的左 0 右 1 的分配方案；再例如，在构建时采用稳定或不
稳定的排序算法。这都会影响到最终输出的哈夫曼编码。范式哈夫曼算法就是为了解决上述
缺点而提出的。
2.2 范式哈夫曼算法
范式哈夫曼算法采用了一个巧妙的方法对哈夫曼树进行了规范调整。首先，对于同一层
的节点，所有的叶子节点都调整到左边。然后，对于同一层的叶子节点按照符号顺序从小到
大调整。最后，按照左 0 右 1 的方案分配编码。图 2.2 中的哈夫曼树经过这样的调整可以得
到一棵范式哈夫曼树（以下简称“范式树”）如图 2.3 所示。
0
1
0
1
0
A
D
G
0
H
0
1
1
0
1
1
0
B
C
E
F
1
图 2.3 范式哈夫曼树
根据图 2.3 中的范式树可以得到表 2.2 中的范式哈夫曼编码。将表 2.2 中的范式哈夫曼
编码，按照以编码位长为第 1 关键字、符号为第 2 关键字进行排序，可以得到范式哈夫曼编
码表。可以将相同位长的符号称之为同组符号。在同组符号之间的排序序号可以称之为同组
序号。结果如表 2.3 所示。
序号 同组序号 符号 位长 编码
0
1
2
3
4
5
6
7
00
01
10
110
11100
11101
11110
11111
0
1
2
0
0
1
2
3
2
2
2
3
5
5
5
5
A
D
G
H
B
C
E
F
表 2.3 范式哈夫曼编码表
第 6 页 共 26 页
观察图 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)所示。
1)
0
9
1
12
2
10
3
15
4
8
5
13
6
14
7
11
8
10
9
1
10
1
11
11
12
1
13
1
14
8
15
5
第 7 页 共 26 页
2)
3)
4)
5)
6)
7)
0
12
1
15
2
10
3
11
0
10
1
15
2
13
3
11
0
10
1
15
2
13
3
11
0
10
1
15
2
13
3
11
0
1
0
1
1
38
1
0
2
1
2
1
3
1
3
1
4
8
4
8
4
8
4
8
4
3
4
2
5
13
6
14
5
14
6
12
5
14
6
12
5
14
5
4
5
3
6
7
6
5
6
4
8
10
8
10
8
10
8
10
8
2
8
2
7
9
7
9
7
2
7
2
7
5
7
4
9
1
9
1
9
7
9
7
9
7
9
5
10
1
11
11
12
1
13
1
14
8
15
5
10
1
11
11
12
1
13
1
14
8
15
5
10
1
11
11
12
7
13
1
14
8
15
5
10
1
11
11
12
7
13
1
14
8
15
5
10
6
11
2
12
7
13
6
14
3
15
4
10
5
11
2
12
5
13
5
14
2
15
3
图 3.1 M 算法的数据整理
根据最小堆的原理，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)所示。重复这个过程，直
第 8 页 共 26 页
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
