一、背景
编码是信息处理的基础(重新表示信息)。 普通的编码是等长编码,例如7位的ASCIL编码,对出现频率不同的字符都使用相同的编码长度。但其在传输和存储等情况下编码效率不高。 可使用不等长编码,来压缩编码:高频字符编码长度更短,低频字符编码长度更长。 [例] 将百分制的考试成绩转换成五分制的成绩![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100791-585945718.png)
![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100804-1168747302.png)
二、哈夫曼树
哈夫曼树的定义![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100831-1253809692.png)
![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100790-404653738.png)
![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100783-1840853039.png)
typedef struct TreeNode *HuffmanTree; struct TreeNode{ int Weight; HuffmanTree Left, Right; }; /* WPL WeightPathLength Cost越小编码越有效, O(NlogN) */ HuffmanTree Huffman( MinHeap H ) { /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */ int i; HuffmanTree T; BuildMinHeap(H); /* 将H->Elements[]按权值调整为最小堆 */ /* 做 H->Size - 1 次合并 */ for (i = 1; i < H->Size; i++) { T = malloc( sizeof( struct TreeNode) ); /* 建立新结点 */ T->Left = DeleteMin(H); /* 从最小堆中删除一个结点,作为新T的左子结点 */ T->Right = DeleteMin(H); /* 从最小堆中删除一个结点,作为新T的右子结点 */ T->Weight = T->Left->Weight + T->Right->Weight; /*计算新权值*/ Insert( H, T ); /*将新T插入最小堆*/ } T = DeleteMin(H); return T; int WPL( HuffmanTree H ) { return H->Weight; }
哈夫曼树的特点
- 没有度为1的结点;
- 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树;
- n个叶子结点的哈夫曼树共有2n-1个结点;
![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100757-2115845032.png)
- 前缀码prefix code:任何字符的编码,都不是另一字符编码的前缀
![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100810-1931364153.png)
![0](/i/l/?n=23&i=blog/1596082/202304/1596082-20230415224100882-78589648.png)