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使用GZIP压缩反回数据问题

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》：本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么，可以干什么？3、Spr
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
Java图片压缩三种高效压缩方案详细解析

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,：本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点：适用场景：二、JPEG质量参数压缩关键技术：压缩效果对比
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
一文详解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.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2