## 哈夫曼编码/哈夫曼树 ###### 哈夫曼编码（英语：Huffman Coding），又译为霍夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由美国计算机科学家大卫·霍夫曼于1952年发明。 ###### 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。 `这里可以是权重，也可以是在编码中出现的次数` ### 例如 #### 现在有一个字符串为`'AABBBCDE'` 编码方式大概有几种
1. ``` A:0 B:1 C:10 D:11 E:100 依照上述变换方法 'AABBBCDE'->'001111011100' 当然，缺点或者硬伤也显而易见，得到的字符串解码结果不唯一 ``` 2. ``` 第二种方法就是在第一种方法的基础上让每一个码具有相同的位数，这样就保证了解码得到的结果是唯一的 A:000 B:001 C:010 D:011 E:100 这时，最简单的方式就出现了，但是仍然有缺点，也就是得到的结果并不一定是最短的 ``` 3. ``` 最后这一种就是哈夫曼编码，使用二叉树的数据结构，在保证解码结果唯一的前提下得到最短的结果 ``` ```C typedef struct ListNode // 结点结构，哈夫曼树与频度链表共用 { char c; // 结点的字符 int frequency; // 字符的频度 char *code; // 字符的编码(对哈夫曼树结点有效) struct ListNode *parent; // 结点的双亲结点(对哈夫曼树结点有效) struct ListNode *left; // 结点的左子树(对哈夫曼树结点有效) struct ListNode *right; // 结点的右子树(对哈夫曼树结点有效) struct ListNode *next; // 结点的后继结点(对频度链表结点有效) } ListNode, HuffmanTree; ``` `以下代码实现均采用C语言` ## FIRST 建立频度链表来统计字符的频度通过频度也就是权重来建立哈夫曼树，频度链表的建立可以使用链表来实现 ```c int main() { // 这里一定要给字符串分配空间 char str[1000]; ListNode *head = (ListNode *)malloc(sizeof(ListNode)); head->next = NULL; ListNode *p = head; // 循环读取每一行输入 while (fgets(str, 1000, stdin) != NULL) { char *s = str; while (*s != '\0') { int flag = 0; p = head; while (p->next != NULL) { if (p->next->c == *s) { p->next->frequency++; flag = 1; break; } p = p->next; } if (flag == 0) { ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); newNode->c = *s; newNode->frequency = 1; newNode->code = NULL; newNode->parent = NULL; newNode->left = NULL; newNode->right = NULL; newNode->next = NULL; p->next = newNode; } s++; } } // 为每个节点添加序号以记录输入顺序 int inputOrder = 0; p = head->next; while (p != NULL) { p->parent = (struct ListNode *)(long)inputOrder++; // 借用parent指针临时存储顺序 p = p->next; } // 按照从大到小的顺序排序频度链表，相同频度按输入顺序 // 使用插入排序，它是稳定的排序算法 ListNode *sorted = NULL; p = head->next; head->next = NULL; while (p != NULL) { ListNode *next = p->next; if (sorted == NULL || sorted->frequency < p->frequency) { // 插入到链表头部 p->next = sorted; sorted = p; } else { // 找到合适的位置插入 ListNode *current = sorted; while (current->next != NULL && (current->next->frequency > p->frequency || (current->next->frequency == p->frequency && (long)current->next->parent < (long)p->parent))) { current = current->next; } p->next = current->next; current->next = p; } p = next; } head->next = sorted; // 遍历输出 p = head->next; while (p != NULL) { if (p->c == '\n') { printf("'\\n' %d\n", p->frequency); } else { printf("'%c' %d\n", p->c, p->frequency); } p = p->next; } // 释放内存 p = head->next; while (p != NULL) { ListNode *temp = p; p = p->next; free(temp); } free(head); return 0; } ``` ::: tip 注意：一般都使用头插法实现链表，原因如下：
头插法的时间复杂度为O(1)，而尾插法的时间复杂度为O(n) ::: ## SECOND 建立哈夫曼树并生成哈夫曼编码（顺手的事儿） ```c // 函数声明 void generateHuffmanCode(HuffmanTree *root); void freeHuffmanTree(HuffmanTree *root); void collectLeafNodes(HuffmanTree *root, ListNode **list); int main() { char str[1000]; ListNode *head = (ListNode *)malloc(sizeof(ListNode)); head->next = NULL; ListNode *p = head; // 循环读取每一行输入 // 统计字符频度 // 直到输入结束(EOF) while (fgets(str, 1000, stdin) != NULL) { char *s = str; while (*s != '\0') { int flag = 0; p = head; while (p->next != NULL) { if (p->next->c == *s) { p->next->frequency++; flag = 1; break; } p = p->next; } if (flag == 0) { ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); newNode->c = *s; newNode->frequency = 1; newNode->code = NULL; newNode->parent = NULL; newNode->left = NULL; newNode->right = NULL; newNode->next = NULL; p->next = newNode; } s++; } } // 哈夫曼编码实现逻辑 // 添加序号记录输入顺序 int inputOrder = 0; p = head->next; while (p != NULL) { // 利用parent暂时保存输入顺序 p->parent = (struct ListNode *)(long)inputOrder++; p = p->next; } // 1. 将频度链表按照频度从高到低排序，相同频度按输入顺序排序 ListNode *sorted = NULL; p = head->next; head->next = NULL; while (p != NULL) { ListNode *next = p->next; if (sorted == NULL || sorted->frequency < p->frequency) { // 频度更高，插入到链表头部 p->next = sorted; sorted = p; } else { // 找到合适的位置插入 ListNode *current = sorted; while (current->next != NULL && (current->next->frequency > p->frequency || (current->next->frequency == p->frequency && (long)current->next->parent < (long)p->parent))) { current = current->next; } p->next = current->next; current->next = p; } p = next; } head->next = sorted; // 重置排序，按频度从小到大排序（为了构建哈夫曼树） sorted = NULL; p = head->next; head->next = NULL; while (p != NULL) { ListNode *next = p->next; if (sorted == NULL || sorted->frequency > p->frequency) { p->next = sorted; sorted = p; } else { ListNode *current = sorted; while (current->next != NULL && current->next->frequency <= p->frequency) { current = current->next; } p->next = current->next; current->next = p; } p = next; } head->next = sorted; // 2. 构建哈夫曼树 ListNode *forest = head->next; // 森林，初始每棵树只有一个节点 head->next = NULL; // 断开head与forest的连接 while (forest != NULL && forest->next != NULL) { // 取出两个频度最小的树 ListNode *first = forest; ListNode *second = forest->next; forest = second->next; // 更新森林 // 创建新的根节点 ListNode *newRoot = (ListNode *)malloc(sizeof(ListNode)); newRoot->c = '\0'; // 内部节点无字符 newRoot->frequency = first->frequency + second->frequency; newRoot->code = NULL; newRoot->parent = NULL; newRoot->left = first; newRoot->right = second; newRoot->next = NULL; // 设置子节点的父节点 first->parent = newRoot; second->parent = newRoot; // 将新树插入到森林中合适的位置 if (forest == NULL || newRoot->frequency <= forest->frequency) { newRoot->next = forest; forest = newRoot; } else { p = forest; while (p->next != NULL && p->next->frequency < newRoot->frequency) { p = p->next; } newRoot->next = p->next; p->next = newRoot; } } HuffmanTree *huffmanRoot = forest; // 最后森林中只剩一棵树，即哈夫曼树 // 3. 生成哈夫曼编码 if (huffmanRoot != NULL) { // 如果只有一个节点 if (huffmanRoot->left == NULL && huffmanRoot->right == NULL) { huffmanRoot->code = (char *)malloc(2 * sizeof(char)); huffmanRoot->code[0] = '0'; huffmanRoot->code[1] = '\0'; } else { // 递归为每个叶子节点生成编码 generateHuffmanCode(huffmanRoot); } // 4. 输出哈夫曼编码表（按频度从高到低排序） // 创建一个新的链表用于按频度从高到低排序输出 ListNode *sortedOutput = NULL; collectLeafNodes(huffmanRoot, &sortedOutput); // 按频度从高到低排序 ListNode *sortedHead = (ListNode *)malloc(sizeof(ListNode)); sortedHead->next = NULL; // 将收集到的叶子节点按频度从高到低排序 ListNode *node = sortedOutput; while (node != NULL) { ListNode *next = node->next; if (sortedHead->next == NULL || sortedHead->next->frequency < node->frequency) { node->next = sortedHead->next; sortedHead->next = node; } else { p = sortedHead; while (p->next != NULL && (p->next->frequency > node->frequency || (p->next->frequency == node->frequency && (long)p->next->parent < (long)node->parent))) { p = p->next; } node->next = p->next; p->next = node; } node = next; } // 输出排序后的哈夫曼编码 p = sortedHead->next; while (p != NULL) { if (p->c == '\n') { printf("'\\n' %d %s\n", p->frequency, p->code); } else { printf("'%c' %d %s\n", p->c, p->frequency, p->code); } p = p->next; } // 输出带权路径长度 int wpl = 0; p = sortedHead->next; while (p != NULL) { wpl += p->frequency * strlen(p->code); p = p->next; } printf("%d\n", wpl); // 释放sortedHead free(sortedHead); } // 释放内存 freeHuffmanTree(huffmanRoot); free(head); return 0; } // 收集哈夫曼树中的所有叶子节点 void collectLeafNodes(HuffmanTree *root, ListNode **list) { if (root == NULL) return; if (root->left == NULL && root->right == NULL) { // 是叶子节点，添加到链表 ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); newNode->c = root->c; newNode->frequency = root->frequency; newNode->code = (char *)malloc((strlen(root->code) + 1) * sizeof(char)); strcpy(newNode->code, root->code); newNode->parent = root->parent; // 保留parent中存储的输入顺序 newNode->left = NULL; newNode->right = NULL; newNode->next = *list; *list = newNode; } collectLeafNodes(root->left, list); collectLeafNodes(root->right, list); } // 生成哈夫曼编码 void generateHuffmanCode(HuffmanTree *root) { if (root == NULL) return; // 初始化根节点的编码 if (root->parent == NULL) { root->code = (char *)malloc(sizeof(char)); root->code[0] = '\0'; } // 递归生成左右子树的编码 if (root->left != NULL) { int codeLen = strlen(root->code); root->left->code = (char *)malloc((codeLen + 2) * sizeof(char)); strcpy(root->left->code, root->code); root->left->code[codeLen] = '0'; root->left->code[codeLen + 1] = '\0'; generateHuffmanCode(root->left); } if (root->right != NULL) { int codeLen = strlen(root->code); root->right->code = (char *)malloc((codeLen + 2) * sizeof(char)); strcpy(root->right->code, root->code); root->right->code[codeLen] = '1'; root->right->code[codeLen + 1] = '\0'; generateHuffmanCode(root->right); } } // 释放哈夫曼树内存 void freeHuffmanTree(HuffmanTree *root) { if (root == NULL) return; freeHuffmanTree(root->left); freeHuffmanTree(root->right); if (root->code != NULL) { free(root->code); } free(root); } ``` ## THIRD 解码 ```c void decodeHuffmanCode(HuffmanTree *root, char *encodedStr); // 解码哈夫曼编码 void decodeHuffmanCode(HuffmanTree *root, char *encodedStr) { if (root == NULL || encodedStr == NULL) return; // 特殊情况：如果只有一个节点 if (root->left == NULL && root->right == NULL) { for (int i = 0; i < strlen(encodedStr); i++) { printf("%c", root->c); } return; } HuffmanTree *current = root; char *p = encodedStr; while (*p != '\0') { if (*p == '0') { current = current->left; } else if (*p == '1') { current = current->right; } // 如果到达叶子节点，输出字符并重新从根节点开始 if (current->left == NULL && current->right == NULL) { printf("%c", current->c); current = root; } p++; } } ```