20147 §6.6.2 Huffman编码 §6.6.2 Huffman编码 ◆定长编两：网长g 公静态墙网 ◆变长增调：问题是解码可能有二义性 无需海次压结前均统计C的频度，而是对定义在相同字符靠 如：设E,T,W编码为00,01,0001 上的大量文件进行计，测出每个字符C,出现的率，此 两，则平均网长为： 解码时对0001串有两种方式：E工，W 问题的原因一E的墙码是W的填码的前氯 Σ了一平均码长最短的前氯码为最优前领码 前源增钢：是求字符集中，任一字符的纳码肯不是其他 字符填网的前氯。显然，定长纳网是前量墙网 2鲜克学轻008…086平构奶长为 量优的前细网（付uffman编码）：压镇效果量佳的前氯网 特点 所有文件使用同一纳码，省时 ①功态格调 编码算法 对不同的文件，效果不尽相同 对错定文件，先统计字符集C=C1,c2,c】中各字符出现 2. 的频率，据此设计墙码，设c的网长为，则墙吗文件总长度： ·算法思想 之—使文件编码总长最短的前领码是最优前银网 件物态智表示的不同文件，塘码方素不同，即文 利用Huffman制求量优前氯码 step1:用字符c作为叶子，p,(或切徽c的权，构造uffman制 特点：费时，效果最佳 s19p2将制的左右分支分别标记0和1，将根到那叶子的路径上的振号 依次相连，作为该叶子字符的编网。 s6.6.2 Huffman编码 s6.6.2 Huffman编码 ·例子 ·上述编码是量优的前领吗？ 678910 T45n13c512bm16eu09,05,a142503,5510 电量优 :叶子的码长=叶子的路径长度 ,∑P以疑是平均网长，又是=叉树的WPL 55 下标ch bits 即Huffman制是WPL量最小的二又树=>平均网长量小 ②前绿码 72 :制中在一叶子不可能是其它叶子的祖先 1D0 每叶子纳码不可能是其它叶子纳码的前爆 2=0.110国16 3I风 3 111 0 3算法实现（对字符集编码，即叶子集编码） 5 50 typedef struct 100 710 char ch; ∥放字符 ()哈夫曼编码树 ()哈夫曼编码表 char bits[n+们：∥放位率0结桌，码长不会超过n }CodeNode; ∥存放Huffman纳码的结点 按算法建立的Huffman树幢 typedef CodeNode HuffmanCode[n]: S6.62 Huffman编码 s6.6.2 Huffman编码 void HuffmanCoding (HuffmanTree T,HuffmanCode H){ ∥根据哈夫曼树求哈夫曼绮网瘦H 4应用（数据文件的压缩与解压） int c,p,i; ∥c和p分别指示树打中孩子和父亲的位量 ①压缩徽据文件对文件编冯 char cd[n+小：B编时存放编码 for(依次从H中读入字将c)( int start; ∥指示编网在cd中的起始位量 在Huffman网表H中，找H0.ch=c cdn=n0:B从后往前放编周 将c转换为H门.bits写入压输文件2中： fort=0:i<n;计+H依次求时于可的填网0≤i≤n1 /按bis0,1写入“位”，设2是二进制文件 H叮.ch=getchar(0:煤入叶子T)对应的字符，若建树时有字符则无霜滨入 start n; ®加压绿网对压输文件解码 cei 从叶子T可上测至根，逆肉求棉网 while(p=TIc.parent)>=0){∥到授为止 for(依次读入f2中的位率(1直至文件结来 许(Tp].lchild=c)cd-star=0':∥暂Tc是p)的左于刺生成代码0 从Huffman树根Tm-]出发 else cd[-start]='1'; ∥否测生成代码1 若当前读入0，走向左孩子，否别走向右孩子： c=p; ∥链蝶上别 若到达叶子T四，便泽出字符H门.ch写入还原文件中，然后 量新从根出发译码 strcpy(H0.bits,&cd[start]∥复制编爵位率 }∥endfor Note:实际压缩与解压时，编网的01位率，不是字符串，即写入 ∥时间：on.h 压文件中的是“位” 102014/4/7 10 §6.6.2 Huffman编码   lg C    定长编码：码长  变长编码：问题是解码可能有二义性 例如：设E,T,W编码为00, 01, 0001 解码时对0001串有两种方式：ET, W 问题的原因 —— E的编码是W的编码的前缀  前缀编码：要求字符集中，任一字符的编码皆不是其他 字符编码的前缀。 显然，定长编码是前缀编码  最优的前缀码 (H ff 编码) 压缩效果最佳的前缀码 55  最优的前缀码 (Huffman编码)：压缩效果最佳的前缀码 ① 动态编码 对给定文件，先统计字符集C = {c1,c2,…,cn} 中各字符出现 的频率fi , 据此设计编码，设ci 的码长为li ，则编码文件总长度： —— 使文件编码总长最短的前缀码是最优前缀码 对同一字符集表示的不同文件，编码方案不同，即根据文 件特征动态编码。 特点： 费时，效果最佳 1 n i i i f l =  §6.6.2 Huffman编码 1 n i i i p l =  ② 静态编码 无需每次压缩前均统计Ci 的频度，而是对定义在相同字符集 上的大量文件进行统计，得出每个字符Ci 出现的概率pi ，据此编 码，则平均码长为： —— 平均码长最短的前缀码为最优前缀码 例：上例中a～f 出现的概率为：0.45, 0.13, …, 0.05, 平均码长为 2.24，优于定长编码 (平均码长为3)。 56 特点 2. 编码算法  算法思想 利用Huffman树求最优前缀码 step1：用字符ci 作为叶子，pi (或fi )做ci 的权，构造Huffman树 step2：将树的左右分支分别标记0和1，将根到叶子的路径上的标号 依次相连，作为该叶子(字符)的编码。    所有文件使用同一编码，省时 对不同的文件，效果不尽相同 §6.6.2 Huffman编码  例子 57 按算法建立的Huffman树唯一 §6.6.2 Huffman编码  上述编码是最优的前缀吗？ ② 最优 ∵ 叶子的码长 = 叶子的路径长度li ∴ 既是平均码长，又是二叉树的WPL 即 Huffman树是WPL最小的二叉树 => 平均码长最小 ② 前缀码 ∵ 树中任 叶子不可能是其它叶子的祖先 1 n i i i p l =  58 ∵ 树中任一叶子不可能是其它叶子的祖先 ∴ 每叶子编码不可能是其它叶子编码的前缀 3. 算法实现 (对字符集编码，即叶子集编码) typedef struct { char ch; // 放字符 char bits[n+1]; // 放位串‘\0’结束，码长不会超过n } CodeNode; // 存放Huffman编码的结点 typedef CodeNode HuffmanCode[n]; §6.6.2 Huffman编码 void HuffmanCoding (HuffmanTree T, HuffmanCode H) { // 根据哈夫曼树T求哈夫曼编码表H int c, p, i; // c和p分别指示树T中孩子和父亲的位置 char cd[n+1]; // 临时存放编码 int start; // 指示编码在cd中的起始位置 cd[n] = ‘\0’; // 从后往前放编码 for (i = 0; i < n; i++){ //依次求叶子T[i]的编码 0 ≤ i ≤ n-1 H[i].ch = getchar();//读入叶子T[i]对应的字符,若建树时有字符则无需读入 start = n; 59 start = n; c = i; //从叶子T[i]上溯至根，逆向求编码 while((p = T[c].parent) >= 0) { // 到根为止 if (T[p].lchild == c) cd[--start] = ‘0’; // 若T[c]是T[p]的左子树生成代码0 else cd[--start] = ‘1’; // 否则生成代码1 c = p; // 继续上溯 } strcpy(H[i].bits, &cd[start]); // 复制编码位串 } // endfor } // 时间: O(n.h) §6.6.2 Huffman编码 4. 应用 (数据文件的压缩与解压) ① 压缩数据文件 (对文件编码) for (依次从f1中读入字符c) { 在Huffman编码表H中，找H[i].ch = c 将c转换为H[i].bits写入压缩文件f2中； // 按bits0，1串写入“位”，设f2是二进制文件 } 60 ② 加压译码 (对压缩文件解码) for (依次读入f2中的位串) { // 直至文件结束 从Huffman树根T[m-1]出发 若当前读入0，走向左孩子，否则走向右孩子； 若到达叶子T[i]，便译出字符H[i].ch写入还原文件中，然后 重新从根出发译码 } Note: 实际压缩与解压时，编码的0/1位串，不是字符串，即写入 压缩文件中的是“位