昨天本来就把这篇文章发出来了，但是程序有一点小的问题，而且没有解码步骤，几天全部补上。
霍夫曼编码是Huffman在MIT的博士毕业论文中提出的一种编码方法。因为它的简单实用，所以虽然已经过去了很多很多年，但这种方法依然经久不衰。说来惭愧，虽说是通信专业科班出身，但是信息论的内容已经忘得差不多了，只记住了如何编码，而这种编码背后所蕴含的复杂的数学推导（否则也不能作为博士论文发表啊），已经几乎没有印象了。
通俗的说，就是假如我们知道我们要发的消息一定是由a，b，c，d，e，f，g，h8个字母组成的。而且每个字符出现的概率是确定的。比如a出现概率有60%，b有20%等等，它的基本思想是，对于出现频率高的字符，用较少的比特表示，而出现频率低的字符，则用较长的比特表示。这样与直接从000到111的平局分配相比，当字符很多的时候，可以减少总的比特数。
它的编码过程如下：
假设N个字符构成了集合h
1.从h中选择2个概率最小的字符x,y,它们的权值分别为wx，wy。
2.用x，y构造二叉树X。X的左右节点为x，y，这个节点的权值为wx+wy
3.将新产生的二叉树X加入到集合h中，同时将x，y删去
4.不断重复1~3，直到h中只剩下一个元素。
5.沿着产生的树，一边为0，另一边为1，直到叶子节点，则每个叶子节点经过的0、1路径就是该叶子节点对应字符的编码。
让我们先看看定义的数据结构：
//26个英文字母
#define SIZE 26
typedef struct Honde
{
char val;
double p;//概率值
int parent;
int LeftChild;
int RightChild;
}Hnode,*pHnode;
//数组用来承载集合h
Hnode H[400];
程序中有一点小的技巧，就是树的父亲、孩子指针不再是指向另一棵树，而是存放这棵树在树类型的数组H中的下标。
让我们先看看主函数：
#include "huffman.h"
int main()
{
if(!initData())
return -1;
int hsize = HuffmanCode(SIZE);
decode(hsize);
return 0;
}
可以看出，整个程序分为3个步骤：初始化数据，编码，以及解码。
初始化数据的任务，就是读取一份文件，对立面的字数进行统计，并求出对应的概率。这里为了简单，只统计了小写字母。
//读入文本，并统计每个字符的概率
bool initData()
{
FILE *fp;
//注意：如果使用\表示下一级目录，则会当做转义字符
fp = fopen("D:\\MyPrograms\\ds\\mytext.txt","r");
if(NULL == fp)
{
printf("can't open the file!");
return false;
}
//记录文件中每个字母的个数，charCount[0]记录的是总数
int charCount[SIZE+1];
for(int i = 0; i < SIZE+1;++i)
{
charCount[i] = 0;
}
//字符数组用来标识每个字符
char firstChar = 'a';
char word[SIZE];
for(int i = 0; i < SIZE;++i,++firstChar)
word[i] = firstChar;
char ch;
while((ch = getc(fp)) != EOF)
{
++charCount[0];
switch(ch)
{
case 'a':
++charCount[1];
break;
case 'b':
++charCount[2];
break;
case 'c':
++charCount[3];
break;
case 'd':
++charCount[4];
break;
case 'e':
++charCount[5];
break;
case 'f':
++charCount[6];
break;
case 'g':
++charCount[7];
break;
case 'h':
++charCount[8];
break;
case 'i':
++charCount[9];
break;
case 'j':
++charCount[10];
break;
case 'k':
++charCount[11];
break;
case 'l':
++charCount[12];
break;
case 'm':
++charCount[13];
break;
case 'n':
++charCount[14];
break;
case 'o':
++charCount[15];
break;
case 'p':
++charCount[16];
break;
case 'q':
++charCount[17];
break;
case 'r':
++charCount[18];
break;
case 's':
++charCount[19];
break;
case 't':
++charCount[20];
break;
case 'u':
++charCount[21];
break;
case 'v':
++charCount[22];
break;
case 'w':
++charCount[23];
break;
case 'x':
++charCount[24];
break;
case 'y':
++charCount[25];
break;
case 'z':
++charCount[26];
break;
default:
break;
}
}
printf("总单词个数为%d:\n",charCount[0]);
for(int i = 0;i < SIZE; ++i)
printf("字符%c: %d\t",word[i],charCount[i+1]);
printf("\n每组字符的概率为：\n");
//记录概率的数组
double p[SIZE];
for(int i = 0; i < SIZE;++i)
{
p[i] = (double)charCount[i+1] / (double)charCount[0];
printf("字符%c:%f\t",word[i],p[i]);
}
printf("\n");
fclose(fp);
//初始化H矩阵
for(int i = 0; i < SIZE;++i)
{
H[i].val = word[i];
H[i].p = p[i];
H[i].LeftChild = H[i].RightChild = H[i].parent = -1;
}
return true;
}
然后再看编码步骤：
int HuffmanCode(int n)
{
//合并后的新结构体依次放在后面H数组的后面
int cnt = n;
//直到合并的剩了最后一个元素，停止合并
while(cnt > 1)
{
int i = 0,j = 0;
select2MinValue(n,&i,&j);
// printf("\ni = %d,j = %d\n",i,j);
GenerrateBineryTree(n,i,j,n);
++n;
--cnt;
}
outputCode(n);
//返回值为整个数组的总的元素个数
return n;
}
可以看出编码步骤基本对应于我们前面提到的步骤：先选择两个概率最小的节点，然后把它们合并成新的节点，放在数组的末尾。最后遍历树来实现整个编码。唯一有一点小的技巧的地方在于：在选择最小概率的节点时，需要判断这个节点是否已经被选择过了，这通过合并节点时记录子节点的父节点可以判断，这样就少去了原步骤中的删除x，y。
//遍历数组：找出其中最小的元素，并将其通过index和inex传出去
void select2MinValue(int n,int *minIndex,int *subminIndex)
{
double min = 1;
double submin = 1;
for(int i = 0; i < n;++i)
{
if(H[i].parent != -1)
continue;
if(H[i].p <= min)
{
submin = min;
min = H[i].p;
*subminIndex = *minIndex;
*minIndex = i;
}
else
{
if(H[i].p < submin)
{
submin = H[i].p;
*subminIndex = i;
}
}
}
}
void GenerrateBineryTree(int n,int index1,int index2,int newindex)
{
H[newindex].LeftChild = index1;
H[newindex].RightChild = index2;
H[newindex].parent = -1;
H[newindex].p = H[index1].p + H[index2].p;
H[index1].parent = newindex;
H[index2].parent = newindex;
}
int outputCode(int n)
{
//先输出整个数组的情况：
for(int i = 0; i < n;++i)
{
printf("序号:%d\t概率:%f\t父亲:%d\tleft:%d\tright%d\n",i,H[i].p,H[i].parent,H[i].LeftChild,H[i].RightChild);
}
//密码表
FILE *code = fopen("codelist.txt","w");
if(NULL == code )
return -1;
//通过一个动态字符串数组来存储这个元素的编码
char** elemnetCode = (char**)malloc(sizeof(char*)*SIZE);
//对于实际存在的元素
for(int i = 0; i < SIZE;++i)
{
//遍历每个元素的路径，通过遍历来确定每条路径的长度
int currentIndex = i;
int fatherIndex = H[i].parent;
int cnt = 1;
while(H[currentIndex].parent != -1)
{
currentIndex = fatherIndex;
fatherIndex = H[fatherIndex].parent;
++cnt;
}
int charsize = cnt;
//为每个元素分配合适的存储空间
elemnetCode[i] = (char*)malloc(sizeof(char)*(charsize));
//重新遍历一次，这次遍历的任务是给节点赋值
currentIndex = i;
fatherIndex = H[i].parent;
int k = cnt;
elemnetCode[i][--k] = NULL;
while(H[currentIndex].parent != -1)
{
if(H[fatherIndex].LeftChild == currentIndex)
elemnetCode[i][--k] = '0';
else
elemnetCode[i][--k] = '1';
currentIndex = fatherIndex;
fatherIndex = H[fatherIndex].parent;
}
printf("第%d个元素编码为%s\n",i,elemnetCode[i]);
fprintf(code,"%c: %s\n",H[i].val,elemnetCode[i]);
}
fclose(code);
//打开待加密的文件
FILE *fp = fopen("D:\\MyPrograms\\ds\\mytext.txt","r");
if(NULL == fp)
{
printf("can't open sourse file");
return -1;
}
FILE *Ciphertext = fopen("Ciphertext.txt","w+");
if(NULL == Ciphertext)
{
printf("can't open Ciphertext file");
return -1;
}
char letter;
while(( letter = fgetc(fp))!= EOF)
{
char first = 'a';
int number = 0;
while( first != letter)
{
++first;
++number;
}
//加一行打印
// printf("%s\n",elemnetCode[number]);
fprintf(Ciphertext,"%s",elemnetCode[number]);
}
fclose(fp);
fclose(Ciphertext);
//释放内存
for(int i = 0 ;i < SIZE;++i)
free(elemnetCode[i]);
free(elemnetCode);
return 0;
}
最后再看解码，解码的原理比较比较简单，由于霍夫曼码是“非前缀码”，所以只需要从根开始，按照编码指定的方向沿着树走，走到最后就找到了对应的元素了。
//解码
bool decode(int hsize)
{
FILE *fp = fopen("Ciphertext.txt","r");
if(NULL == fp)
{
printf("can't find Ciphertext");
return false;
}
char letter;
int i = 6000;
char *content = (char*)malloc(sizeof(char)* i);
//计算整个编码有多少位
i = 0;
int cnt = 0;
while(( letter = getc(fp))!= EOF)
{
content[i] = letter;
++i;
++cnt;
}
content[i] = NULL;
int index = hsize-1;
for(int j = 0; j < cnt;++j)
{
if('0' == content[j])
index = H[index].LeftChild;
else
index = H[index].RightChild;
if(H[index].LeftChild == -1 && H[index].RightChild == -1)
{
printf("%c",H[index].val);
index = hsize-1;
}
}
free(content);
return true;
}
程序的基本思路就是这样，可能会有一些小的瑕疵，但是大体上还是可以用的。
分享到：
相关推荐
霍夫曼编码是一种高效的数据压缩编码方式，源于霍夫曼树的概念。霍夫曼树，又称最优二叉树，是带权路径长度最小的二叉树。在信息处理和编码中，霍夫曼编码是一种基于概率的一致性编码，常用于无损数据压缩。编码的...
本文将深入探讨霍夫曼编码的概念、工作原理以及如何利用它进行加密和解密。 霍夫曼编码的基本思想是为出现频率高的字符分配较短的编码，而为出现频率低的字符分配较长的编码。这样，常见的字符在数据中占用的空间更...
在MATLAB中实现霍夫曼编码主要涉及两个关键步骤：码树的构建和编码的生成。 1. 码树的构建： - 首先，根据给定的字符及其概率，将概率从大到小排序，创建位置索引矩阵（Index）。 - 接着，每次选择概率最小的两个...
在MATLAB环境下实现霍夫曼编码，不仅可以加深对这一算法的理解，还可以通过实验来直观地观察编码效率和压缩效果。 霍夫曼编码的基本原理是：频繁出现的字符用较短的编码，不常出现的字符用较长的编码，这样可以使得...
3. **编码映射**：利用构建好的霍夫曼树，为每个字符生成对应的霍夫曼编码，并存储在字符串数组`MM`中。 4. **编码反转**：通过`nixu`函数对生成的编码进行反转，使得编码顺序符合常规（从左到右）。 5. **输出结果*...
在C++中实现霍夫曼编码，首先要理解其基本步骤： 1. **统计字符频率**：遍历输入文件，统计每个字符出现的次数，形成频率表。 2. **构建霍夫曼树**：根据频率表，使用优先队列（如最小堆）创建霍夫曼树。初始时，每...
MATLAB作为一种强大的数学计算和数据分析工具，自然也可以用于实现霍夫曼编码的过程。以下我们将详细探讨霍夫曼编码的原理及其在MATLAB中的实现。 首先，霍夫曼编码的核心思想是根据字符出现的频率来分配不同的二...
霍夫曼树是实现霍夫曼编码的关键数据结构，也称为最优二叉树或最小带权路径长度树。它的构建过程基于贪心策略：首先将每个字符视为一个只有一个节点的树（称为叶子节点），然后按照字符出现频率从小到大依次合并这些...
利用C语言实现霍夫曼编码不仅可以帮助我们理解霍夫曼树的构建过程，还能让我们更加深刻地了解霍夫曼编码的原理。此外，通过对代码的具体分析，还可以掌握如何在实际应用中灵活运用霍夫曼编码进行数据压缩，这对于...
在VC++环境下实现霍夫曼编码涉及以下几个关键知识点： 1. 霍夫曼树的构建：首先，我们需要统计输入文本中各个字符的出现频率，创建一个频率表。然后，使用这些频率作为权重，构建一个最小带权路径长度（Minimum ...
### 霍夫曼编码及译码的C语言实现 ...通过理解其核心原理并掌握其实现细节，可以更好地利用霍夫曼编码解决实际问题。上述代码提供了一个基本的实现框架，对于初学者来说，是理解和实践霍夫曼编码的一个良好起点。
本篇文章将详细介绍如何基于二叉树实现霍夫曼编码，并通过一个具体的C++程序实例进行演示。 #### 二、霍夫曼编码原理 霍夫曼编码的核心思想是根据字符出现的频率构建一颗特殊的二叉树——霍夫曼树（Huffman Tree）...
在C++中实现霍夫曼编码通常包括以下几个步骤： 1. **统计字符频率**：首先，需要统计输入数据中每个字符出现的频率。这可以通过遍历整个文本，使用一个哈希表或数组记录每个字符出现的次数来完成。 2. **构建...
在C++中实现霍夫曼编码，需要理解以下几个关键知识点： 1. 频率统计：首先，我们需要对输入的文本进行字符频率统计。C++中可以使用`std::map`或`std::unordered_map`来存储每个字符及其出现次数。 ```cpp std::map...
总结来说，JPEG中的霍夫曼编码利用了霍夫曼树这一数据结构，通过优化符号的编码长度，实现了高效的无损数据压缩。解码时，可以通过重建霍夫曼树或使用查找表来还原原始数据。这种编码技术在图像压缩等领域具有重要的...
在MATLAB中实现霍夫曼编码，首先需要理解图像的基本表示，如像素值、颜色空间等。通常，图像数据以二维数组形式存在，如RGB图像的每个像素由三个分量（红、绿、蓝）组成。 实现步骤大致如下： 1. **读取图像**：...
本段代码实现了霍夫曼编码的完整过程，包括霍夫曼树的构建以及霍夫曼编码的生成。 1. **头文件包含**：通过`#include`指令包含了必要的头文件，如`stdio.h`、`stdlib.h`和`string.h`等，这些头文件提供了基本的输入...
最后，提到的“Huffman”可能是实验提供的源代码文件或者实验报告模板，它包含了实现霍夫曼编码的具体步骤和示例，供学习者参考和实践。通过阅读和运行这些代码，你可以直观地看到霍夫曼编码的动态过程，进一步巩固...
"赫夫曼编码-译码器.exe" 是一个执行程序，用于实现霍夫曼编码和解码的功能。这个程序首先会读取输入文件，计算每个字符的出现频率，然后根据这些频率构建霍夫曼树。接着，利用霍夫曼树生成每个字符的霍夫曼编码，并...