Huffman算法压缩解压缩（C）

2024-06-22 16:04
文章标签 算法 解压缩 压缩 huffman

本文主要是介绍Huffman算法压缩解压缩（C），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 概述

Huffman压缩算法是一种基于字符出现频率的编码算法，通过构建Huffman树，将出现频率高的字符用短编码表示，出现频率低的字符用长编码表示，从而实现对数据的压缩。以下是Huffman压缩算法的详细流程：
统计字符频率：遍历待压缩的数据，统计每个字符出现的频率。
构建优先队列：将每个字符及其频率作为一个结点放入优先队列（或最小堆）中，根据字符频率构建一个按频率大小排序的优先队列。
构建Huffman树：不断地从优先队列中取出频率最小的两个结点，合并为一个新结点，并将新结点重新插入到优先队列中，直到队列只剩下一个结点，即Huffman树的根结点。
生成Huffman编码：通过遍历Huffman树，从根结点到每个叶子结点的路径上的左右分支分别对应编码0和1，根据路径生成每个字符的Huffman编码。
压缩数据：根据生成的Huffman编码，将待压缩数据中的每个字符替换为对应的Huffman编码，得到压缩后的数据。
存储压缩表：将字符与对应的Huffman编码关系存储为压缩表，以便解压缩时使用。
存储压缩数据：将压缩后的数据以二进制形式存储。
在解压缩时，需要根据存储的Huffman编码表和压缩数据，使用相同的Huffman树结构进行解码，将压缩数据解压缩成原始数据，并输出原始数据。
Huffman压缩算法的优势在于可以根据数据的特征自适应地确定编码，使得出现频率高的字符拥有更短的编码，从而实现高效的数据压缩。然而，Huffman算法对于小规模数据压缩效果不佳，适用于处理较大规模的数据压缩。

2 huffman压缩算法过程详细演示

下面将通过一个简单的例子来演示Huffman压缩算法的压缩过程，假设有一个字符串 “ABRACADABRA” 需要进行压缩。

  1. 统计字符频率：

A: 5 次
B: 2 次
R: 2 次
C: 1 次
D: 1 次
2) 构建优先队列：
构建一个优先队列，按照字符频率排序：

(C, 1), (D, 1), (B, 2), (R, 2), (A, 5)
3) 构建Huffman树：
不断地从优先队列中取出频率最小的两个结点，合并为一个新节点，并重新插入队列中，直到队列只剩下一个节点，作为Huffman树的根节点。

  1. 合并过程：

(C, 1)和(D, 1) -> (CD, 2)
(B, 2)和(R, 2) -> (BR, 4)
((CD, 2) 和 (BR, 4)) -> ((CD)BR, 6)
((A, 5) 和 ((CD)BR, 6)) -> (((CD)BR)A, 11)
最终得到的Huffman树如下：
(((CD)BR)A)
/
(CD)BR A
/
CD BR
/ \ /
C D B R

  1. 生成Huffman编码：
    从根节点开始，左分支为0，右分支为1，生成每个字符的Huffman编码：

A: 0
B: 101
R: 100
C: 1100
D: 1101
6) 压缩数据：
将原始数据字符串 “ABRACADABRA” 中的每个字符使用对应的Huffman编码替换，得到压缩后的数据。

原始数据：ABRACADABRA
Huffman编码：010110011001011010001011110
压缩后数据：010110011001011010001011110

在实际压缩过程中，还需要将Huffman编码表（字符与编码的映射关系）一并存储，以便在解压缩时使用。通过上述过程，原始数据被成功压缩，并且根据Huffman编码，高频字符编码较短，低频字符编码较长，实现了数据的有效压缩。

3 c语言Huffman压缩代码示例

以下是一个简单的C语言示例代码，实现了Huffman算法进行数据压缩和解压缩的功能：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_TREE_HT 100// 结点结构体
typedef struct MinHeapNode {char data;unsigned freq;struct MinHeapNode *left, *right;
} MinHeapNode;// 最小堆结构体
typedef struct MinHeap {unsigned size;unsigned capacity;MinHeapNode **array;
} MinHeap;// 创建新结点
MinHeapNode* newNode(char data, unsigned freq) {MinHeapNode* node = (MinHeapNode*)malloc(sizeof(MinHeapNode));node->left = node->right = NULL;node->data = data;node->freq = freq;return node;
}// 创建最小堆
MinHeap* createMinHeap(unsigned capacity) {MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (MinHeapNode**)malloc(minHeap->capacity * sizeof(MinHeapNode*));return minHeap;
}// 交换两个结点
void swapMinHeapNodes(MinHeapNode** a, MinHeapNode** b) {MinHeapNode* t = *a;*a = *b;*b = t;
}// 最小堆调整
void minHeapify(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) {swapMinHeapNodes(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 获取最小结点
MinHeapNode* extractMin(MinHeap* minHeap) {MinHeapNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入结点
void insertMinHeap(MinHeap* minHeap, 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;
}// 创建和构建最小堆
MinHeap* buildMinHeap(char data[], int freq[], int size) {MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;for (int i = size / 2 - 1; i >= 0; --i)minHeapify(minHeap, i);return minHeap;
}// 检查结点是否是叶子结点
int isLeaf(MinHeapNode* root) {return !(root->left) && !(root->right);
}// 构建霍夫曼树
MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {MinHeapNode *left, *right, *top;MinHeap* minHeap = buildMinHeap(data, freq, size);while (minHeap->size != 1) {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(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 huffmanCompression(char data[]) {int freq[256] = {0};int n = strlen(data);for (int i = 0; i < n; ++i)++freq[data[i]];char arr[256];int freq2[256];int size = 0;for (int i = 0; i < 256; ++i) {if (freq[i] != 0) {arr[size] = (char)i;freq2[size] = freq[i];++size;}}MinHeapNode* root = buildHuffmanTree(arr, freq2, size);int arr2[MAX_TREE_HT], top = 0;printCodes(root, arr2, top);
}int main() {char data[] = "hello world";huffmanCompression(data);return 0;
}

这个示例代码演示了使用Huffman算法对输入的数据进行压缩，并打印出各个字符的Huffman编码。huffmanCompression 函数首先统计输入数据中每个字符的出现频率，并构建Huffman树，然后通过递归遍历Huffman树获取每个字符的Huffman编码并打印出来。在 main 函数中，我们对一个简单的字符串进行了压缩，并输出了每个字符的Huffman编码。

需要注意的是，这个示例代码仅演示了Huffman算法的基本压缩原理，实际应用中可能需要对数据内容、编码方式等进行更多处理和优化。

4 C语言Huffman解压缩算法示例

以下是一个简单的C语言示例代码，实现了Huffman算法进行数据解压缩的功能：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 结点结构体
typedef struct MinHeapNode {char data;struct MinHeapNode *left, *right;
} MinHeapNode;// 解压缩数据
void huffmanDecompression(char data[], MinHeapNode* root) {int n = strlen(data);MinHeapNode* current = root;for (int i = 0; i < n; ++i) {if (data[i] == '0') {current = current->left;} else {current = current->right;}if (current->left == NULL && current->right == NULL) {printf("%c", current->data);current = root;}}
}int main() {// 构造Huffman树MinHeapNode *root = (MinHeapNode*)malloc(sizeof(MinHeapNode));root->left = root->right = NULL;MinHeapNode *A = (MinHeapNode*)malloc(sizeof(MinHeapNode));A->data = 'A';A->left = A->right = NULL;MinHeapNode *B = (MinHeapNode*)malloc(sizeof(MinHeapNode));B->data = 'B';B->left = B->right = NULL;MinHeapNode *C = (MinHeapNode*)malloc(sizeof(MinHeapNode));C->data = 'C';C->left = C->right = NULL;root->left = A;root->right = B;A->left = C;A->right = NULL;B->left = B->right = NULL;C->left = C->right = NULL;// 待解压缩的数据char data[] = "00100110001";// 解压缩数据huffmanDecompression(data, root);return 0;
}

在这个简单的示例代码中，我们首先构建了一个简单的Huffman树，然后定义了一个待解压缩的数据字符串。huffmanDecompression 函数接受压缩后的数据和Huffman树的根结点作为参数，通过逐位解析压缩后的数据，按照Huffman树逐步走到叶子结点，从而解压缩出原始数据并打印。

在 main 函数中，我们构造了一个简单的Huffman树，并指定了一个简单的待解压缩的数据字符串，然后调用 huffmanDecompression 函数进行解压缩操作。解压缩过程中，输出的字符序列应该是根据Huffman树进行解码后的原始数据。

需要注意的是，这个示例代码中的Huffman树和待解压缩的数据都是固定的，实际应用中可能需要根据具体的压缩数据和Huffman树结构进行相应的解压缩处理。

这篇关于Huffman算法压缩解压缩（C）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “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]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
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
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2