管理课件哈夫曼编码.doc

哈夫曼编码 I.问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 II.问题分析 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 设C为编码字符集，则表示其最优前缀码的二叉树中恰有|C|个叶子，|C|-1个内部结点。其中，每个叶子对应于字符集中一个字符。 二叉树T的代价：编码文件需要二进制位数 使 达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。 编码字符集中每一字符c的频率是freq。以freq为键值的最小堆优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入最小堆优先队列Q。 经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 III.算法描述： HUFFMAN(C) //哈夫曼编码算法 n = |C| // 初始化最小优先队列Q INITIALIZE(Q) = BUILD-MIN-HEAP(C) for i=1 to n-1 allocate a new node z z.left = x ← EXTRACT-MIN(Q) //提取队列Q中的最前列结点 z.right = y ← EXTRACT-MIN(Q) z.freq ← x.freq + y.freq INSERT(Q, z) //在队列Q中插入结点z return EXTRACT-MIN(Q) 时间复杂度描述： INITIALIZE(Q) = BUILD-MIN-HEAP(C)的时间复杂度为O（n）； 循环 for i=1 to n-1的时间复杂度为O（n）； 其中， z.left = x ← EXTRACT-MIN(Q) 和z.right = y ← EXTRACT-MIN(Q) 的时间 复杂度分别为O(nlogn)； INSERT(Q, z)的时间复杂度为O（nlogn）； 最后返回最前列结点return EXTRACT-MIN(Q)的时间复杂度也为O(nlogn)。 所以，这个哈弗曼算法的时间复杂度为T（n）=O(nlogn)。 IV.程序 #include stdio.h #include stdlib.h #include string.h typedef struct //结点结构体 { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 //选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i=n; i++) { if((*ht)[i].parent==0 i!=(*s1)) { min=i; break; } } for(i=1; i=n; i++) { if((*ht)[i].parent==0 i!=(*s1)) { if((*ht)[i].weight(*ht)[min].weight) min=i;