霍夫曼编码(Huffman Coding)是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个位来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明霍夫曼树的WPL是最小的。 代码： //本来参照维基百科里的示例写的，可以向量容器始终搞不定，所以参照使用动态数组来完成 #include <iostream> #include <cstdlib> #include <string> using namespace std; typedef struct { unsigned int weight;//结点权值 unsigned int parent,lchild,rchild;//结点的父指针，左右孩子指针 }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表 HuffmanTree HT;//哈夫曼树HT HuffmanCode HC;//哈夫曼编码表HC unsigned int *w;//w存放叶子结点权值 void CreateHuffmanTree(HuffmanTree &,unsigned int*,int);//生成一棵哈夫曼树 void HuffmanCoding(HuffmanTree,HuffmanCode&,int);//对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode,unsigned int*,int);//显示哈夫曼编码 void Select(HuffmanTree,int,int&,int&);//在数组中寻找权值最小的两个结点 int main() { int n,i; //n是哈夫曼树叶子结点数 char choose='y'; //用于选择程序是否退出 while(choose!='N' && choose!='n') { cout << "请输入叶子结点数目:"; do { cin >> n;//输入叶子结点数 cin.clear(); cin.ignore(); } while( n<=1 ); w=(unsigned int*)malloc(n*sizeof(unsigned int));//开辟空间存放权值 for(i=0;i<n;i++) { cout << "W" << i+1 << "的权值:"; cin >> w[i];//输入各叶子结点权值 } CreateHuffmanTree(HT,w,n);//生成哈夫曼树 HuffmanCoding(HT,HC,n);//进行哈夫曼编码 cout << endl; PrintHuffmanCode(HC,w,n);//显示哈夫曼编码 cout << "还要继续吗?(Y/N)"; cin >> choose; } system("pause"); return 0; } void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n) {//w存放n个结点的权值，将构造一棵哈夫曼树HT int i,m; int s1,s2; HuffmanTree p; if(n<=1) return; m=2*n-1;//n个叶子结点的哈夫曼树，有2*n-1个结点 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟2*n各结点空间，0号单元不用 for(p=HT+1,i=1;i<=n;++i,++p,++w)//进行初始化 { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;++i,++p) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i)//建哈夫曼树 { //从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i;//修改s1和s2结点的父指针parent HT[i].lchild=s1; HT[i].rchild=s2;//修改i结点的左右孩子指针 HT[i].weight=HT[s1].weight+HT[s2].weight;//修改权值 } } void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n) { //将有n个叶子结点的哈夫曼树HT进行编码,所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i,c,f,start; char *cd; HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个编码的头指针向量 cd=(char *)malloc(n*sizeof(char));//开辟一个求编码的工作空间 cd[n-1]='/0';//编码结束符 for(i=1;i<=n;++i)//逐个地求哈夫曼编码 { start=n-1;//编码结束位置 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]='0';//若是左孩子编为'0' else cd[--start]='1';//若是右孩子编为'1' HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个编码分配空间 strcpy(HC[i],&cd[start]);//将编码从cd复制到HC中 } free(cd);//释放工作空间 } void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n) { //显示有n个叶子结点的哈夫曼树的编码表 int i; cout << "哈夫曼编码如下:/n"; for(i=1;i<=n;i++) { cout << HC[i]<<"/t" <<"W"<<i<< "ȨֵΪ£º" <<w[i-1]<<endl; } cout<<endl; } void Select(HuffmanTree HT,int t,int&s1,int&s2) { //在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2,s1存放最小的，s2存放次小的 int i=0; int j=0; int k=0; int least=0; int second=0; for(i=1;i<=t;i++) { if(HT[i].parent==0) break; } for(j=i+1;j<=t;j++) { if(HT[j].parent==0) break; } if(HT[i].weight<HT[j].weight) { least=i; second=j; } else { least=j; second=i; } for(k=j+1;k<=t;k++) { if(HT[k].parent==0) { if(HT[k].weight<HT[least].weight) { second=least; least=k; } else if(HT[k].weight>=HT[least].weight&&HT[k].weight<HT[second].weight) second=k; } } s1=least; s2=second; } 运行示例：
转载于:https://www.cnblogs.com/ituff/archive/2011/03/16/2858556.html
相关资源：霍夫曼编码 C语言实现