利用树实现霍夫曼编码
昨天本来就把这篇文章发出来了，但是程序有一点小的问题，而且没有解码步骤，几天全部补上。
霍夫曼编码是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 26typedef struct Honde{char val;double p;//概率值int parent;int LeftChild;int RightChild;}Hnode,*pHnode;//数组用来承载集合hHnode 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';elseelemnetCode[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;elseindex = H[index].RightChild;if(H[index].LeftChild == -1 && H[index].RightChild == -1){printf("%c",H[index].val);index = hsize-1;}}free(content);return true;}