1、 数字图像处理课程设计 课程题目 Huffman 编码原理及算法实现 Huffman 编码理论及算法实现 一、基本介绍 霍夫曼编码使用变长编码表对源符号（如文件中的一个 字母）进行编码，其中变长编码表是通过一种评估来源符号 出现机率的方法得到的，出现机率高的字母使用较短的编 码，反之出现机率低的则使用较长的编码，这便使编码之后 的字符串的平均长度、期望值降低，从而达到无损压缩数据 的目的。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的 二叉树。所谓树的带权路径长度，就是树中所有的叶结点的 权值乘上其到根结点的路径长度（若根结点为 0 层，叶结点 到根结点的路径长度为叶结点的层数） 。树的路
2、径长度是从 树根到每一结点的路径长度之和，记为 WPL= （W1*L1+W2*L2+W3*L3+.+Wn*Ln） N 个权值 Wi （i=1,2,.n） 构成一棵有 N 个叶结点的二叉树， 相应的叶结点的路径长度为 Li（i=1,2,.n） 。可以证明霍 夫曼树的 WPL 是最小的。 输入输入 符号集合 S=s1,s2, ,Sn，其 S 集合的大小为 n。 权重集合 W=w1,w2, ,Wn，其 W 集合不为负数且 Wi=weight(Si)， 1 i n。 输出输出 一组编码 C(S,W)=c1,c2, Cn，其 C 集合是一组二 进制编码且 Ci 为 Si 相对应的编码，1 i n。 霍夫
3、曼树常处理符号编写工作。根据整组数据中符号出 现的频率高低，决定如何给符号编码。如果符号出现的频率 太高，则给符号的码越短，相反符号的号码越长。假设我们 要给一个英文单字“F O R G E T“进行霍夫曼编码，而每个 英文字母出现的频率。 二、二、演算过程演算过程 （一）进行霍夫曼编码前，我们先创建一个霍夫曼树。 将每个英文霍夫曼树字母依照出现频率由小排到大， 最小在左。 每个字母都代表一个终端节点（叶节点） ，比较 F.O.R.G.E.T 五个字母中每个字母的出现频率，将最小的两 个字母频率相加合成一个新的节点。如 Fig.1 所示，发现 F 与 O 的频率最小，故相加 2+3=5。 比较
4、 5.R.G.E.T，发现 R 与 G 的频率最小，故相加 4+4=8。 比较5.8.E.T， 发现5 与E的频率最小， 故相加5+5=10。 比较 8.10.T， 发现 8 与 T 的频率最小， 故相加 8+7=15。 最后剩 10.15， 没有可以比较的对象， 相加 10+15=25。 （二）进行编码（二）进行编码 1.给霍夫曼树的所有左链结0与霍夫曼树右链结1。 2.从树根至树叶依序记录所有字母的编码，如 Fig.2。 三、实现方法三、实现方法 实现霍夫曼编码的方式主要是创建一个二叉树和其节 点。这些树的节点可以存储在数组里，数组的大小为符号 （symbols）数的大小 n，而节点分为是
5、终端节点（叶节点） 图 1 霍夫曼树 图 2 霍夫曼树 与非终端节点（内部节点） 。 一开始， 所有的节点都是终端节点， 节点内有三个字段： 1.符号（Symbol） 2.权重（Weight、Probabilities、Frequency） 3.指向父节点的链结（Link to its parent node） 而非终端节点内有四个字段： 1.权重（Weight、Probabilities、Frequency） 2.指向两个子节点的 链结（Links to two child node） 3.指向父节点的链结（Link to its parent node） 基本上，我们用0与1分别代表指向左
6、子节点与右子 节点，最后为完成的二叉树共有 n 个终端节点与 n-1 个非终 端节点，去除了不必要的符号并产生最佳的编码长度。 过程中，每个终端节点都包含着一个权重（Weight、 Probabilities、Frequency） ，两两终端节点结合会产生一 个新节点，新节点的权重是由两个权重最小的终端节点权重 之总和，并持续进行此过程直到只剩下一个节点为止。 实现霍夫曼树的方式有很多种，可以使用优先队列 （Priority Queue）简单达成这个过程，给与权重较低的符 号较高的优先级（Priority） ，算法如下： 把 n 个终端节点加入优先队列，则 n 个节点都有一个 优先权 Pi，1 i n 如果队列内的节点数1，则： 从队列中移除两个最大的 Pi 节点，即连续做两次 remove(max(Pi), Priority_Queue) 产生一个新节点，此节点为（1）之移除节点之父节 点，而此节点的权重值为（1）两节点之权重和 把（2）产生之节点加入优先队列中 最后在优
