当前位置：首页 > news >正文

哈夫曼编码的实现

news 2024/11/8 0:50:39

哈夫曼编码（Huffman Coding）是一种用于无损数据压缩的广泛使用的算法。它是由美国计算机科学家大卫·哈夫曼（David A. Huffman）在1952年发明的。哈夫曼编码是一种前缀编码方法，它的核心思想是使用更短的编码来表示频繁出现的字符，而使用更长的编码来表示不经常出现的字符，从而减少整个消息的长度。
以下是哈夫曼编码的基本步骤：
1. **统计频率**：首先，统计待编码的消息中每个字符出现的频率。
2. **构建优先队列**：根据字符的频率，构建一个优先队列（通常是一个最小堆）。每个节点包含一个字符和它的频率。
3. **构建哈夫曼树**：
   - 从优先队列中取出两个频率最小的节点。
   - 创建一个新的内部节点，其频率是这两个节点的频率之和。
   - 将这两个节点作为新节点的左右子节点。
   - 将新节点添加回优先队列。
   - 重复上述步骤，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
4. **生成编码**：
   - 从哈夫曼树的根节点开始，为每个字符生成编码。
   - 向左走记为 '0'，向右走记为 '1'。
   - 从根节点到叶子节点的路径即为该叶子节点字符的哈夫曼编码。
哈夫曼编码的特点：
- **前缀编码**：没有任何编码是其他编码的前缀，这避免了编码的歧义。
- **最优性**：在所有前缀编码中，哈夫曼编码能够保证平均编码长度最小，即对于给定的字符频率分布，哈夫曼编码能够产生最短的编码平均长度。
哈夫曼编码的应用非常广泛，特别是在文件压缩中，如GZIP和PKZIP等压缩工具都使用了哈夫曼编码算法。由于哈夫曼编码的效率依赖于字符的频率分布，所以它特别适用于字符频率分布不均匀的数据压缩。

全部代码

#include<stdio.h>
#include<stdlib.h>
#include <ctime>typedef struct Node {char ch;//字符int freq;//频次struct Node* lchild, * rchild;}Node;Node* getNewNode(int freq, char ch) {Node* p = (Node*)malloc(sizeof(Node));p->ch = ch;p->freq= freq;p->lchild = p->rchild = NULL;return p;
}void clear(Node* root) {if (root == NULL) return;clear(root->lchild);clear(root->rchild);free(root);return;
}void swap_node(Node** node_arr, int i, int j) {Node* temp = node_arr[i];node_arr[i] = node_arr[j];node_arr[j] = temp;
}int find_min_node(Node** node_arr,int last_index) {int ind = 0;for (int i = 0; i < last_index; i++) {if (node_arr[ind]->freq > node_arr[i]->freq) {ind = i;}}return ind;
}
Node* buildHaffmanTree(Node** node_arr, int n) {for (int i = 1; i < n; i++) {//第i轮合并了i-1个节点//第i轮时，减少了i-1个节点，还剩下n-i-1个节点，最后一个节点的下标是n-iint ind1 = find_min_node(node_arr, n - i);swap_node(node_arr, ind1, n - i);//与最后一个交换int ind2 = find_min_node(node_arr, n - i - 1);swap_node(node_arr, ind2, n - i-1);//与倒数第二个交换//找到两个频率最小的节点的下标int freq = node_arr[n - i]->freq + node_arr[n - i - 1]->freq;//合并频率Node* node = getNewNode(freq,0);//新节点node->lchild = node_arr[n - i - 1];node->rchild = node_arr[n - i];//新节点的左右子树是原来的最小和第二小的节点node_arr[n - i - 1] = node;//将新节点放在倒数第二小的节点的位置}return node_arr[0];}void extractHaffmanCode(Node* root, char buff[], int k) {buff[k] ='\0';//存的是编码,k是到当前节点的前缀长度if (root->lchild == NULL && root->rchild == NULL) {printf("%c : %s\n", root->ch, buff); \return;}//如果是叶子节点，就输出字符和编码buff[k] = '0';//往左边走，buff数组加入0extractHaffmanCode(root->lchild, buff, k + 1);buff[k] = '1';//往右边走，buff数组加入1extractHaffmanCode(root->rchild, buff, k + 1);
}
int main(){//哈夫曼编码的前提是统计了每一个字符的概率char ch;int freq;Node** node_arr = (Node**)malloc(sizeof(Node*) * 26);for (int i = 0; i < 26; i++) {freq = rand() % 100000;ch = 'a' + i;node_arr[i] = getNewNode(freq, ch);printf("%c %d\n", ch, freq);}//随机生成每一个字符出现的次数Node* root = buildHaffmanTree(node_arr, 26);char buff[1000];extractHaffmanCode(root, buff, 0);clear(root);return 0;
}

主要代码

Node* buildHaffmanTree(Node** node_arr, int n) {for (int i = 1; i < n; i++) {//第i轮合并了i-1个节点//第i轮时，减少了i-1个节点，还剩下n-i-1个节点，最后一个节点的下标是n-iint ind1 = find_min_node(node_arr, n - i);swap_node(node_arr, ind1, n - i);//与最后一个交换int ind2 = find_min_node(node_arr, n - i - 1);swap_node(node_arr, ind2, n - i-1);//与倒数第二个交换//找到两个频率最小的节点的下标int freq = node_arr[n - i]->freq + node_arr[n - i - 1]->freq;//合并频率Node* node = getNewNode(freq,0);//新节点node->lchild = node_arr[n - i - 1];node->rchild = node_arr[n - i];//新节点的左右子树是原来的最小和第二小的节点node_arr[n - i - 1] = node;//将新节点放在倒数第二小的节点的位置}return node_arr[0];}

void extractHaffmanCode(Node* root, char buff[], int k) {buff[k] ='\0';//存的是编码,k是到当前节点的前缀长度if (root->lchild == NULL && root->rchild == NULL) {printf("%c : %s\n", root->ch, buff); \return;}//如果是叶子节点，就输出字符和编码buff[k] = '0';//往左边走，buff数组加入0extractHaffmanCode(root->lchild, buff, k + 1);buff[k] = '1';//往右边走，buff数组加入1extractHaffmanCode(root->rchild, buff, k + 1);
}

输出哈夫曼编码的递归函数解释