Huffman算法:
输入m+1个权值: W = {w0, w1, ... wm} 输出: Huffman 树 while( W中多于两个元素) { 1)令x1, x2为最小的两个权值; 2)构造新的二叉树内部节点N, 其权值为w(N) = x1 + x2; 3)令N的左子为x1,右子为x2; 4)令W = W -{x1, x2} + {w(N)}; } 输出W. Huffman压缩算法:
输入:字符串s = s1s2...sm 输出: s 的 Huffman压缩编码; 1)统计s中每个字符的出现概率; 2)以字符的频率作为权值;构造Huffman树T; 3)根据T将s中的每个字符替换为其Huffman编码; 4)输出s; Huffman树的建立: 假设字符集: S= {0, 1, ... , 255, 256} 其中256专门用来表示原文的结束: struct Huffman_node { int freq_; //字符的出现频率; int lc_; //节点的左子; int rc_; //节点的右子; }; Huffman_node huff[514]; //Huffman tree huff[0..256]用于存放字符的出现频率, 也是Huffman的扩充节点(叶节点) huff[257..512]存放Huffman树的内部节点; huff[513]指明Huffman树的根节点; |
|