摘要：作为一种常用的编码方式即哈夫曼编码，很多人在它的原理即应用方面都弄不不清楚，本文主要以哈夫曼编码原理与应用实例及算法流程图俩进一步说明。
哈夫曼编码（HuffmanCoding），又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码（VLC）的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，将符号按照概率由大到小排队，如图所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图（a）的编码比（b）好。
赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。
长游程的主码和基码均用赫夫曼规则进行编码，这称为修正赫夫曼码，其结果有表可查。该方法已广泛应用于文件传真机中。
哈夫曼编码的算法是查找最优路径的一种算法，首先在所有未分配parent域的节点中找出最小的两个节点，将他们的全值相加，组成新的节点，并且将它标记为原来两个最小节点的parent。这样调用递归，最后就能够成一颗完整的哈夫曼树。然后对每个节点进行遍历编码，得到最终的哈夫曼编码库。流程图如下：
哈夫曼算法的过程为：统计原始数据中各字符出现的频率；所有字符按频率降序排列；建立哈夫曼树：将哈夫曼树存入结果数据；重新编码原始数据到结果数据。哈夫曼算法实现流程如图3所示。
哈夫曼算法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码。实用中．符号的出现频率不能预知，需要统计和编码两次处理，所以速度较慢，无法实用。而自适应（或动态）哈夫曼算法取消了统计，可在压缩数据时动态调整哈夫曼树，这样可提高速度。因此，哈夫曼编码效率高，运算速度快，实现方式灵活。
采用哈夫曼编码时需注意的问题：
（1）哈夫曼码无错误保护功能，译码时，码串若无错就能正确译码；若码串有错应考虑增加编码，提高可靠性。
（2）哈夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。
（3）哈夫曼树的实现和更新方法对设计非常关键。
哈夫曼编码，主要用途是实现数据压缩。
设给出一段报文：CASTCASTSATATATASA。字符集合是{C，A，S，T}，各个字符出现的频度（次数）是W＝{2，7，4，5}。若给每个字符以等长编码A：00T：10C：01S：11，则总编码长度为（2+7+4+5）*2=36。
若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为{2/18，7/18，4/18，5/18}，化整为{2，7，4，5}。以它们为各叶结点上的权值，建立霍夫曼树。左分支赋0，右分支赋1，得霍夫曼编码（变长编码）。A：0T：10C：110S：111。它的总编码长度：7*1+5*2+（2+4）*3=35。比等长编码的情形要短。霍夫曼编码是一种无前缀编码。解码时不会混淆。带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中，权值大的结点离根最近。
霍夫曼算法
2.重复以下步骤，直到F中仅剩下一棵树为止：
①在F中选取两棵根结点的权值最小的扩充二叉树，做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
②在F中删去这两棵二叉树。
③把新的二叉树加入F。
#include《stdio.h》
#include《stdlib.h》
#include《string.h》
#defineMAX32767
typedefchar*HuffmanCode;
typedefstruct
{
intWeight;//字母的权
intParent，Leftchild，Rightchild;
}HuffmanTree;
voidSelect（HuffmanTree*HT，intn，int*s1，int*s2）
intmin1=MAX;
intmin2=MAX;
intpos1，pos2;
inti;
for（i=0;i《n;i++）
if（HT［i］.Parent==-1）//选择还没有父亲的节点
if（HT［i］.Weight《=min1）
pos2=pos1;min2=min1;
pos1=i;min1=HT［i］.Weight;
}
elseif（HT［i］.Weight《=min2）
pos2=i;min2=HT［i］.Weight;
*s1=pos1;*s2=pos2;
intm=2*n-1;//总的节点数
ints1，s2;
for（i=0;i《m;i++）
if（i《n）
HT［i］.Weight=w［i］;
else
HT［i］.Weight=-1;
HT［i］.Parent=-1;
HT［i］.Leftchild=-1;
HT［i］.Rightchild=-1;
for（i=n;i《m;i++）
Select（HT，i，&s1，&s2）;//这个函数是从0到n-1中选两个权最小的节点
HT［i］.Weight=HT［s1］.Weight+HT［s2］.Weight;
HT［i］.Leftchild=s1;
HT［i］.Rightchild=s2;
HT［s1］.Parent=i;
HT［s2］.Parent=i;
voidPrint（HuffmanTree*HT，intm）
if（m！=-1）
printf（“%d”，HT［m］.Weight）;
Print（HT，HT［m］.Leftchild）;
Print（HT，HT［m］.Rightchild）;
char*cd;
intstart;
intCurrent，parent;
cd=（char*）malloc（sizeof（char）*n）;//用来临时存放一个字母的编码结果
cd［n-1］=‘\0’;
start=n-1;
for（Current=i，parent=HT［Current］.Parent;parent！=-1;Current=parent，parent=HT［parent］.Parent）
if（Current==HT［parent］.Leftchild）//判断该节点是父节点的左孩子还是右孩子
cd［--start］=‘0’;
cd［--start］=‘1’;
hc［i］=（char*）malloc（sizeof（char）*（n-start））;
strcpy（hc［i］，&cd［start］）;
free（cd）;
printf（“letters：%c，weight：%d，编码为%s\n”，letters［i］，HT［i］.Weight，hc［i］）;
printf（“\n”）;
voidEncode（HuffmanCode*hc，char*letters，char*test，char*code）
intlen=0;
inti，j;
for（i=0;test［i］！=‘\0’;i++）
for（j=0;letters［j］！=test［i］;j++）{}
strcpy（code+len，hc［j］）;
len=len+strlen（hc［j］）;
printf（“TheTest：%s\nEncodetobe：”，test）;
printf（“%s”，code）;
voidDecode（HuffmanTree*HT，intm，char*code，char*letters）
printf（“TheCode：%s\nDecodetobe：”，code）;
for（i=m-1;HT［i］.Leftchild！=-1&&HT［i］.Rightchild！=-1;position++）
if（code［position］==‘0’）
i=HT［i］.Leftchild;
i=HT［i］.Rightchild;
printf（“%c”，letters［i］）;
intmain（）
intn=27;
intm=2*n-1;
charletters［28］={‘a’，‘b’，‘c’，‘d’，‘e’，‘f’，‘g’，‘h’，‘i’，‘j’，‘k’，‘l’，‘m’，
‘n’，‘o’，‘p’，‘q’，‘r’，‘s’，‘t’，‘u’，‘v’，‘w’，‘x’，‘y’，‘z’，‘’};
intw［28］={64，13，22，32，103，21，15，47，57，1，5，32，20，
57，63，15，1，48，51，80，23，8，18，1，16，1，168};
charcode［200］;
chartest［50］={“thisisaboutbuildmylife”};
HuffmanTree*HT;
HuffmanCode*hc;
HT=（HuffmanTree*）malloc（m*sizeof（HuffmanTree））;
hc=（HuffmanCode*）malloc（n*sizeof（char*））;
CreateTree（HT，n，w）;
Print（HT，m-1）;
Huffmancoding（HT，n，hc，letters）;
Encode（hc，letters，test，code）;
Decode（HT，m，code，letters）;
return0;
推荐阅读：
下载发烧友APP
哈夫曼编码可以使得编码的总长最短，从而相同的位长可以传送更多的信息。下面来看看c语言是如何实现哈夫曼...
摘要：哈夫曼编码作为一种编码方式，已经在生活中得到了实际的运用，下面我们以java实现的哈夫曼编码...