C++实现Huffman编码解码算法：原理与代码详解
C++实现Huffman编码解码算法：原理与代码详解
1. 概述
Huffman编码是一种常用的数据压缩算法，它利用字符出现频率的差异，对出现频率高的字符使用较短的编码，对出现频率低的字符使用较长的编码，从而达到压缩数据的效果。本文将详细介绍Huffman编码解码算法的原理和实现，并提供完整的C++代码示例。
2. Huffman编码原理
2.1 哈夫曼树
Huffman编码的核心是哈夫曼树。哈夫曼树是一种二叉树，每个节点代表一个字符，节点的权值代表该字符出现的频率。哈夫曼树的构建过程如下：
- 将所有字符按照权值从小到大排序，并将其作为叶子节点；
- 选择权值最小的两个节点，将其合并成一个新的节点，新的节点的权值等于两个节点的权值之和；
- 将新的节点加入到排序后的节点列表中，重复步骤2，直到所有节点都被合并成一个节点为止。
2.2 编码
哈夫曼树构建完成后，就可以根据哈夫曼树进行编码。编码的规则如下：
- 从根节点出发，到达每个叶子节点的路径可以表示为0和1的组合，其中0表示向左子树遍历，1表示向右子树遍历；
- 将每个叶子节点的路径用0和1的组合表示，就得到了该字符的编码。
2.3 解码
解码的过程就是根据编码反向推导出原始字符。具体步骤如下：
- 从哈夫曼树的根节点开始遍历，若当前编码位为'0'，则向左子树遍历，否则向右子树遍历，直到遇到叶子节点为止；
- 将遍历路径上的字符按顺序拼接起来，得到对应的原始字符；
- 重复步骤1和2，直到将所有编码都解码为原始字符。
3. C++代码实现
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<map>
#include <fstream>
#include<iostream>
#define MAXN 50
using namespace std;
typedef char **HuffmanCode;
typedef struct{
int weight;
int parent, lchild, rchild;
}HTNode,*HuffmanTree;
HuffmanTree HT;
HuffmanCode HC;
int m,s1,s2,start,c,f;
char *cd;
int z[30];
int weight[MAXN] ;
void Select(HuffmanTree HT,int n,int &s1,int &s2)//Select函数
{
int min1 =0x3f3f3f3f;
int min2 =0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
if(HT[i].parent) continue;//不是根节点
if(HT[i].weight < min1)
{
min1 = HT[i].weight;
s1 = i;
continue;
}
if(HT[i].weight < min2 && HT[i].weight >= min1)
{
min2 = HT[i].weight;
s2 = i;
}
}
}
void CreatHuffmanTree(HuffmanTree &HT ,int n )
{
if ( n <= 1 ) return;
int m = 2 * n ;
HT = new HTNode[m+1] ;
for (int a = 1 ; a <= m ; a ++ )
{
HT[a].parent = HT[a].lchild = HT[a].rchild = HT[a].weight = 0;
}
for (int j = 1 ; j <= n ; j ++ )
{
HT[j].weight = weight[j] ;
}
int s1 ,s2 ;
for (int i = n + 1 ; i <= m ; i ++ )
{
Select(HT ,i - 1 ,s1 ,s2 );
HT[s1].parent = i ; HT[s2].parent = i ;
HT[i].lchild = s1 ,HT[i].rchild = s2 ;
HT[i].weight = HT[s1].weight + HT[s2].weight ;
}
} //编码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
HC = new char*[n+1];
cd = new char[n];
cd[n-1] = '\0';
for(int i=1; i<=n; ++i)
{
start = n-1;
c = i;
f = HT[i].parent;
while(f!=0)//
{
--start;
if(HT[f].lchild == c) cd[start]='0';
else cd[start]='1';
c = f;
f = HT[f].parent;//向上回溯
}
HC[i] = new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
}
//解码
int main()
{
// freopen("in.txt", "r", stdin);//文件要和代码放在同一个文件夹
// freopen("out.txt", "w", stdout);
char s[MAXN];
scanf("%s",s);
int len = strlen(s);
memset(z,0,sizeof(z));
for(int i=0;i<len;i++)//统计字符个数
z[s[i]-'A'+1]++;
int cnt=0;
for(int j=1;j<=26;++j)
if(z[j])
cnt++;
for(int k=1;k<=26;k++)
if(z[k])
printf("%c:%d\n",'A'+k-1,z[k]);
CreatHuffmanTree(HT,cnt);
//输出一下看看是否建立好哈夫曼数
printf("\n i weight parent lchild rchild \n");
for(int x=1; x<=m; ++x)
printf("%2d %5d %8d %8d %8d\n",x,HT[x].weight,HT[x].parent,HT[x].rchild,HT[x].lchild);
CreatHuffmanCode(HT,HC,cnt);
printf("\n\nHuffmanCode:\n");
printf(" i Char Code\n\n");
for(int t=1; t<=cnt; ++t)
printf("%2d %c %s\n",t,t+'A'-1,HC[t]);
puts("");
for(int z=0;z<len;z++)
printf("%s",HC[s[z]-'A'+1]);
return 0;
}
string decode(HuffmanTree HT, string encoded) {
int len = encoded.length();
string decoded = "";
int i = 0;
while (i < len) { // 遍历编码串
int p = m; // 从哈夫曼树的根节点开始
while (HT[p].lchild != 0 || HT[p].rchild != 0) { // 遍历到叶子节点
if (encoded[i] == '0') p = HT[p].lchild;
else p = HT[p].rchild;
i++;
}
decoded += char(p - m + 'A' - 1); // 将遍历路径上的字符按顺序拼接起来
}
return decoded;
}
4. 代码解释
4.1 CreatHuffmanTree 函数
void CreatHuffmanTree(HuffmanTree &HT ,int n )
{
if ( n <= 1 ) return;
int m = 2 * n ;
HT = new HTNode[m+1] ;
for (int a = 1 ; a <= m ; a ++ )
{
HT[a].parent = HT[a].lchild = HT[a].rchild = HT[a].weight = 0;
}
for (int j = 1 ; j <= n ; j ++ )
{
HT[j].weight = weight[j] ;
}
int s1 ,s2 ;
for (int i = n + 1 ; i <= m ; i ++ )
{
Select(HT ,i - 1 ,s1 ,s2 );
HT[s1].parent = i ; HT[s2].parent = i ;
HT[i].lchild = s1 ,HT[i].rchild = s2 ;
HT[i].weight = HT[s1].weight + HT[s2].weight ;
}
}
该函数用于构建哈夫曼树，它接收一个指向哈夫曼树的指针和字符个数作为参数。函数首先分配内存空间，然后将每个字符的权值存储到哈夫曼树节点的 weight 属性中。接着，函数调用 Select 函数选择权值最小的两个节点，并将它们合并成一个新的节点，重复该步骤直到所有节点都被合并成一个节点为止。
4.2 CreatHuffmanCode 函数
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
HC = new char*[n+1];
cd = new char[n];
cd[n-1] = '\0';
for(int i=1; i<=n; ++i)
{
start = n-1;
c = i;
f = HT[i].parent;
while(f!=0)//
{
--start;
if(HT[f].lchild == c) cd[start]='0';
else cd[start]='1';
c = f;
f = HT[f].parent;//向上回溯
}
HC[i] = new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
}
该函数用于生成哈夫曼编码，它接收一个指向哈夫曼树的指针、一个指向哈夫曼编码的指针和字符个数作为参数。函数首先为哈夫曼编码分配内存空间，然后遍历哈夫曼树，从每个叶子节点向上回溯到根节点，将路径上的0和1存储到 cd 数组中，最后将 cd 数组中的编码复制到哈夫曼编码数组中。
4.3 decode 函数
string decode(HuffmanTree HT, string encoded) {
int len = encoded.length();
string decoded = "";
int i = 0;
while (i < len) { // 遍历编码串
int p = m; // 从哈夫曼树的根节点开始
while (HT[p].lchild != 0 || HT[p].rchild != 0) { // 遍历到叶子节点
if (encoded[i] == '0') p = HT[p].lchild;
else p = HT[p].rchild;
i++;
}
decoded += char(p - m + 'A' - 1); // 将遍历路径上的字符按顺序拼接起来
}
return decoded;
}
该函数用于解码哈夫曼编码，它接收一个指向哈夫曼树的指针和一个编码字符串作为参数。函数首先遍历编码字符串，从哈夫曼树的根节点开始，根据编码位的值选择左子树或右子树遍历，直到遍历到叶子节点为止。然后将叶子节点对应的字符添加到解码后的字符串中，重复该步骤直到遍历完整个编码字符串为止。
5. 总结
本文介绍了Huffman编码解码算法的原理和实现，并提供完整的C++代码示例。文章涵盖了哈夫曼树的构建、编码、解码等步骤，并对代码进行注释解释。希望本文能帮助读者更好地理解Huffman编码解码算法。
原文地址: https://www.cveoy.top/t/topic/lPxD 著作权归作者所有。请勿转载和采集!