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。

相关文章

一文详解SpringBoot响应压缩功能的配置与优化

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录，并压缩为zip文件到另一个
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python利用PIL进行图片压缩

Python利用PIL进行图片压缩

《Python利用PIL进行图片压缩》有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所以本文为大家介绍了Python中图片压缩的方法,需要的可以参考下... 有时在发送一些文件如PPT、Word时，由于文件中的图片太大，导致文件也太大，无法发送，所有可以对文件中的图
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
Qt实现文件的压缩和解压缩操作

Qt实现文件的压缩和解压缩操作

《Qt实现文件的压缩和解压缩操作》这篇文章主要为大家详细介绍了如何使用Qt库中的QZipReader和QZipWriter实现文件的压缩和解压缩功能,文中的示例代码简洁易懂,需要的可以参考一下... 目录一、实现方式二、具体步骤1、在.pro文件中添加模块gui-private2、通过QObject方式创建
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2