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。

相关文章

Linux中压缩、网络传输与系统监控工具的使用完整指南

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压：数据存储与传输的优化核心1. zip/unzip：通用压缩格式的便捷操作2.
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
SpringBoot实现文件记录日志及日志文件自动归档和压缩

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志，日志文件自动归档和压缩2.1、
阅读更多...
使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
Springboot实现推荐系统的协同过滤算法

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品（如商品、电影、音乐等）的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法（Collaborativ
阅读更多...
使用Python实现矢量路径的压缩、解压与可视化

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1
阅读更多...
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
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2