数字图像处理课程设计-- huffman编码理论及算法实现

《数字图像处理课程设计-- huffman编码理论及算法实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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、如何给符号编码。如果符号出现的频率太高，则给符号的码越短，相反符号的号码越长。假设我们要给一个英文单字"FORGET"进行霍夫曼编码，而每个英文字母出现的频率。一、演算过程（一）进行霍夫曼编码前，我们先创建一个霍夫曼树。⒈将每个英文霍夫曼树字母依照出现频率由小排到大，最小在左。⒉每个字母都代表一个终端节点（叶节点），比较F.O.R.G.E.T五个字母中每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点。如Fig.1所示，发现F与O的频率最小，故相加2+3=5。⒊比较5.R.G.E.T，发现R与G的频率最小，故相加4+4=8。⒋比较5.8.E.T，发现5与E的频率最小，故

4、相加5+5=10。⒌比较8.10.T，发现8与T的频率最小，故相加8+7=15。⒍最后剩10.15，没有可以比较的对象，相加10+15=25。图2霍夫曼树图1霍夫曼树（二）进行编码1.给霍夫曼树的所有左链结'0'与霍夫曼树右链结'1'。2.从树根至树叶依序记录所有字母的编码，如Fig.2。三、实现方法实现霍夫曼编码的方式主要是创建一个二叉树和其节点。这些树的节点可以存储在数组里，数组的大小为符号（symbols）数的大小n，而节点分为是终端节点（叶节点）与非终端节点（内部节点）。一开始，所有的节点都是终端节点，节点内有三个字段：1.符号（Symbol）2.权重（Weight、Pr

5、obabilities、Frequency）3.指向父节点的链结（Linktoitsparentnode）而非终端节点内有四个字段：1.权重（Weight、Probabilities、Frequency）2.指向两个子节点的链结（Linkstotwochildnode）3.指向父节点的链结（Linktoitsparentnode）基本上，我们用'0'与'1'分别代表指向左子节点与右子节点，最后为完成的二叉树共有n个终端节点与n-1个非终端节点，去除了不必要的符号并产生最佳的编码长度。过程中，每个终端节点都包含着一个权重（Weight、Probabilities、Frequency

6、），两两终端节点结合会产生一个新节点，新节点的权重是由两个权重最小的终端节点权重之总和，并持续进行此过程直到只剩下一个节点为止。实现霍夫曼树的方式有很多种，可以使用优先队列（PriorityQueue）简单达成这个过程，给与权重较低的符号较高的优先级（Priority），算法如下：⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1≤i≤n⒉如果队列内的节点数>1，则：⑴从队列中移除两个最大的Pi节点，即连续做两次remove(max(Pi),Priority_Queue)⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和⑶把（2

7、）产生之节点加入优先队列中⒊最后在优先队列里的点为树的根节点（root）而此算法的时间复杂度（TimeComplexity）为O（nlogn）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（logn）。此外，有一个更快的方式使时间复杂度降至线性时间（LinearTime）O(n)，就是使用两个队列（Queue）创件霍夫曼树。第一个队列用来存储n个符号（即n个终端节点）的权重，第二个队列用来存储两两权重的合（即非终端节点）。此法可保证第二个队列的前端（F