算法篇_C语言实现霍夫曼编码算法

2024-09-06 23:36
文章标签 算法 语言 实现 编码 霍夫曼

本文主要是介绍算法篇_C语言实现霍夫曼编码算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前言

霍夫曼编码（Huffman Coding）是一种广泛使用的数据压缩算法，特别适用于无损数据压缩。它是由David A. Huffman在1952年提出的，并且通常用于文件压缩和传输中减少数据量。霍夫曼编码的核心思想是使用变长编码表对源数据进行编码，其中较频繁出现的数据项会被赋予较短的编码，而较少出现的数据项则会被赋予较长的编码。

该编码方法通过构建一种特殊的二叉树——霍夫曼树，为数据中的各个符号分配长度可变的前缀码，使得高频出现的符号具有较短的编码，而低频出现的符号则具有较长的编码。这种特性使得霍夫曼编码非常适合于压缩具有不均匀符号频率分布的数据集，能够有效地减小数据的存储空间或传输所需的带宽。

霍夫曼编码的工作原理如下：首先统计输入数据中每个符号出现的频率；然后基于这些频率值构造一个最小堆，其中堆中的每个元素都是一个只包含一个符号及其频率的树节点；接着反复从堆中取出频率最小的两个节点，合并成一个新的内部节点，该节点的频率为两个子节点频率之和，并将这个新节点放回堆中；重复这一过程直到堆中只剩下一个节点，这个节点即为霍夫曼树的根节点；最后，从根节点出发遍历整棵树，定义从根到任一叶节点的路径上，向左走标记为0，向右走标记为1，这样每个叶节点就对应了一个唯一的二进制编码，这就是霍夫曼编码。

霍夫曼编码的一个关键特征是其编码具有前缀性质，即没有任何一个符号的编码是另一个符号编码的前缀，这保证了在解码过程中可以唯一确定每一个编码所代表的符号，从而确保了压缩和解压过程的一致性。此外，霍夫曼编码是熵编码的一种形式，它利用了数据的统计特性来进行压缩，理论上可以达到接近于信息熵的压缩效率，即在理想情况下，压缩后的数据量等于数据的信息熵。

霍夫曼编码在文件压缩软件中，如WinZip、7-Zip，使用霍夫曼编码来压缩文件；在网络通信中，为了提高传输效率，会采用霍夫曼编码来压缩数据流；在图像处理和视频编码中，霍夫曼编码经常与其他编码技术结合使用，比如JPEG图像压缩标准就使用了霍夫曼编码来进一步压缩量化后的离散余弦变换系数。

在这里插入图片描述

下面是霍夫曼编码的基本步骤：

  1. 统计字符频率：

    • 首先需要统计输入数据中每个字符出现的次数。

  2. 创建霍夫曼树（也称为最优二叉树）：

    • 创建一个叶子节点集合，每个叶子节点包含一个字符和它的频率。
    • 反复执行以下操作，直到所有节点合并成一棵树：
      • 从集合中选出两个频率最低的节点作为新节点的左右子节点。
      • 新节点的频率是其两个子节点频率之和。
      • 将这个新节点加入集合中。
    • 最终剩下的那棵树就是霍夫曼树。

  3. 生成编码规则：

    • 从霍夫曼树的根节点出发，向左走标记为0，向右走标记为1。
    • 每个叶子节点对应的路径上的数字序列即为其霍夫曼编码。

  4. 编码数据：

    • 使用生成的霍夫曼编码表对原始数据进行编码。

  5. 解码数据：

    • 解码时只需按照霍夫曼树从根节点开始，根据0或1沿着树向下移动即可还原出原始数据。

霍夫曼编码的一个重要特点是它是前缀编码，这意味着没有一个编码是另一个编码的前缀。这样可以确保编码后的数据可以唯一地解码回原始数据。

举个简单的例子来说明霍夫曼编码的过程：

假设我们有这样一个字符串：“ABACDAACAC”，其中字符A出现了5次，B出现了1次，C出现了4次，D出现了1次。

  1. 统计字符频率：

    • A: 5
    • B: 1
    • C: 4
    • D: 1

  2. 创建霍夫曼树：

    • 构建初始节点集合：{A(5), B(1), C(4), D(1)}
    • 合并B(1)和D(1)，得到一个新节点BD(2)
    • 合并C(4)和BD(2)，得到一个新节点CBDB(6)
    • 最后合并A(5)和CBDB(6)，得到霍夫曼树的根节点。

  3. 生成编码规则：

    • A: 0
    • B: 110
    • C: 10
    • D: 111

  4. 编码数据：

    • “ABACDAACAC”编码后变为：“0110100011101000100”

二、算法设计（C语言）

2.1 霍夫曼编码算法实现

下面代码里实现了创建霍夫曼树、生成霍夫曼编码、对输入文本进行编码和解码的功能。编译运行这段代码可以得到每个字符的霍夫曼编码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_TREE_HT 100// 霍夫曼树节点
struct MinHeapNode {char data;unsigned freq;struct MinHeapNode* left, * right;
};// 最小堆
struct MinHeap {unsigned size;unsigned capacity;struct MinHeapNode** array;
};// 创建新节点
struct MinHeapNode* newNode(char data, unsigned freq) {struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));temp->left = temp->right = NULL;temp->data = data;temp->freq = freq;return temp;
}// 创建最小堆
struct MinHeap* createMinHeap(unsigned capacity) {struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));return minHeap;
}// 交换两个最小堆节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {struct MinHeapNode* t = *a;*a = *b;*b = t;
}// 堆化
void minHeapify(struct MinHeap* minHeap, int idx) {int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)smallest = left;if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)smallest = right;if (smallest != idx) {swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 检查大小是否为1
int isSizeOne(struct MinHeap* minHeap) {return (minHeap->size == 1);
}// 提取最小值节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {struct MinHeapNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入最小堆
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {++minHeap->size;int i = minHeap->size - 1;while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = minHeapNode;
}// 构建最小堆
void buildMinHeap(struct MinHeap* minHeap) {int n = minHeap->size - 1;int i;for (i = (n - 1) / 2; i >= 0; --i)minHeapify(minHeap, i);
}// 检查是否是叶子节点
int isLeaf(struct MinHeapNode* root) {return !(root->left) && !(root->right);
}// 创建和构建最小堆
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {struct MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;buildMinHeap(minHeap);return minHeap;
}// 构建霍夫曼树
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {struct MinHeapNode* left, * right, * top;struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);while (!isSizeOne(minHeap)) {left = extractMin(minHeap);right = extractMin(minHeap);top = newNode('$', left->freq + right->freq);top->left = left;top->right = right;insertMinHeap(minHeap, top);}return extractMin(minHeap);
}// 打印编码
void printCodes(struct MinHeapNode* root, int arr[], int top) {if (root->left) {arr[top] = 0;printCodes(root->left, arr, top + 1);}if (root->right) {arr[top] = 1;printCodes(root->right, arr, top + 1);}if (isLeaf(root)) {printf("%c: ", root->data);for (int i = 0; i < top; ++i)printf("%d", arr[i]);printf("\n");}
}// 霍夫曼编码主函数
void HuffmanCodes(char data[], int freq[], int size) {struct MinHeapNode* root = buildHuffmanTree(data, freq, size);int arr[MAX_TREE_HT], top = 0;printCodes(root, arr, top);
}// 主函数
int main() {char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };int freq[] = { 5, 9, 12, 13, 16, 45 };int size = sizeof(arr) / sizeof(arr[0]);HuffmanCodes(arr, freq, size);return 0;
}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.2 数据的编码与还原

以下是使用霍夫曼编码算法对一段数据进行压缩和还原。代码包括生成霍夫曼树、生成编码表、对数据进行压缩和还原的功能。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_TREE_HT 100
#define MAX_CHAR 256// 霍夫曼树节点
struct MinHeapNode {unsigned char data;unsigned freq;struct MinHeapNode* left, * right;
};// 最小堆
struct MinHeap {unsigned size;unsigned capacity;struct MinHeapNode** array;
};// 创建新节点
struct MinHeapNode* newNode(unsigned char data, unsigned freq) {struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));temp->left = temp->right = NULL;temp->data = data;temp->freq = freq;return temp;
}// 创建最小堆
struct MinHeap* createMinHeap(unsigned capacity) {struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));return minHeap;
}// 交换两个最小堆节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {struct MinHeapNode* t = *a;*a = *b;*b = t;
}// 堆化
void minHeapify(struct MinHeap* minHeap, int idx) {int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)smallest = left;if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)smallest = right;if (smallest != idx) {swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 检查大小是否为1
int isSizeOne(struct MinHeap* minHeap) {return (minHeap->size == 1);
}// 提取最小值节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {struct MinHeapNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入最小堆
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {++minHeap->size;int i = minHeap->size - 1;while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = minHeapNode;
}// 构建最小堆
void buildMinHeap(struct MinHeap* minHeap) {int n = minHeap->size - 1;int i;for (i = (n - 1) / 2; i >= 0; --i)minHeapify(minHeap, i);
}// 检查是否是叶子节点
int isLeaf(struct MinHeapNode* root) {return !(root->left) && !(root->right);
}// 创建和构建最小堆
struct MinHeap* createAndBuildMinHeap(unsigned char data[], int freq[], int size) {struct MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;buildMinHeap(minHeap);return minHeap;
}// 构建霍夫曼树
struct MinHeapNode* buildHuffmanTree(unsigned char data[], int freq[], int size) {struct MinHeapNode* left, * right, * top;struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);while (!isSizeOne(minHeap)) {left = extractMin(minHeap);right = extractMin(minHeap);top = newNode('$', left->freq + right->freq);top->left = left;top->right = right;insertMinHeap(minHeap, top);}return extractMin(minHeap);
}// 生成编码表
void generateCodes(struct MinHeapNode* root, int arr[], int top, char* codes[]) {if (root->left) {arr[top] = 0;generateCodes(root->left, arr, top + 1, codes);}if (root->right) {arr[top] = 1;generateCodes(root->right, arr, top + 1, codes);}if (isLeaf(root)) {codes[root->data] = (char*)malloc(top + 1);for (int i = 0; i < top; ++i) {codes[root->data][i] = arr[i] + '0';}codes[root->data][top] = '\0';}
}// 压缩数据
void compressData(const char* data, char* codes[], char* compressed) {while (*data) {strcat(compressed, codes[(unsigned char)*data]);data++;}
}// 解码霍夫曼树
void decodeHuffmanTree(struct MinHeapNode* root, char* encoded, char* decoded) {struct MinHeapNode* current = root;while (*encoded) {if (*encoded == '0') {current = current->left;}else {current = current->right;}if (isLeaf(current)) {*decoded++ = current->data;current = root;}encoded++;}*decoded = '\0';
}// 打印编码表
void printCodes(char* codes[]) {for (int i = 0; i < MAX_CHAR; i++) {if (codes[i]) {printf("%c: %s\n", i, codes[i]);}}
}// 主函数
int main() {const char* data = "我是DS小龙哥-这是一段测试的数据，如果你可以正确的看到我，说明解码已经成功了";int freq[MAX_CHAR] = { 0 };for (int i = 0; data[i]; i++) {freq[(unsigned char)data[i]]++;}unsigned char uniqueChars[MAX_CHAR];int uniqueFreqs[MAX_CHAR];int size = 0;for (int i = 0; i < MAX_CHAR; i++) {if (freq[i]) {uniqueChars[size] = i;uniqueFreqs[size] = freq[i];size++;}}struct MinHeapNode* root = buildHuffmanTree(uniqueChars, uniqueFreqs, size);char* codes[MAX_CHAR] = { 0 };int arr[MAX_TREE_HT], top = 0;generateCodes(root, arr, top, codes);printf("Huffman Codes:\n");printCodes(codes);char compressed[1024] = { 0 };compressData(data, codes, compressed);printf("\nCompressed Data: %s\n", compressed);char decoded[1024] = { 0 };decodeHuffmanTree(root, compressed, decoded);printf("\nDecoded Data: %s\n", decoded);for (int i = 0; i < MAX_CHAR; i++) {if (codes[i]) {free(codes[i]);}}return 0;
}

这段代码实现了霍夫曼编码算法的压缩和解码功能。霍夫曼编码是一种无损数据压缩算法，利用字符在数据中出现的频率构建霍夫曼树，从而生成字符的二进制编码。

代码先定义了霍夫曼树节点和最小堆的结构，包含创建新节点、交换节点、堆化节点、提取最小值节点、插入最小堆和构建最小堆的功能。然后，通过辅助函数isLeaf检查节点是否为叶子节点。

通过buildHuffmanTree函数构建霍夫曼树，将字符和其对应的频率插入最小堆，反复提取两个最小频率节点，并将它们合并成一个新节点，再插回最小堆，直到堆中只剩一个节点，即为霍夫曼树的根节点。通过generateCodes函数递归遍历霍夫曼树，生成每个字符的霍夫曼编码，并存储在编码表中。

compressData函数使用生成的编码表将输入数据压缩为霍夫曼编码。

decodeHuffmanTree函数通过遍历霍夫曼树解码压缩后的数据，恢复原始数据。

printCodes辅助函数用于打印生成的霍夫曼编码表。

在主函数中，统计输入数据中每个字符的频率，然后构建霍夫曼树，生成编码表，对输入数据进行压缩，最后再对压缩后的数据进行解码，并打印结果。代码在实现霍夫曼编码和解码过程中，展示了从频率统计、树的构建、编码生成到数据压缩和解码的完整流程。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

这篇关于算法篇_C语言实现霍夫曼编码算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1143434。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2