哈夫曼编码（Huffman Coding）是一种编码方式，哈夫曼编码是可变字 长编码（VL C）的一种Huffman于1952年提出一种编码方法，该方 法完全依据字符出现概率 来构造异字头 的平均长 度最短的码字，有时 称之为最佳编码，一般就叫作 Huffman 编码以哈夫曼树一即最优二叉树，带权路径长度最小 的二叉树，经常应用于数据压 缩在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"）， 用于数据的无 损耗压缩这一术语是指使 用一张特殊的编码表将源字符（例如某文件 中的一个符号）进行编 码这张编码表的特殊之处在于，它是根据每 一个源字符出现 的估算概率而 建立起来的（出现概率高的 字符使用较短的编码，反之 出现概率低的则 使用较长的编 码，这便使编码之后的字符 串的平均期望长度降低，从 而达到无损压缩 数据的目的） 这种方法是由 David.A.Huffman 发展起来的 例如，在英文中， e 的出现概率很 高，而z的出现概率则最低当利用哈夫曼编码对一篇英文进行压缩时， e极有可能用一个位（bit）来表示，而z则可能花去25个位（不是26）用普通的表 示方法时，每 个英文字母均占用一个字节（byte），即8个位。
二者相比，e使用了 一般编码的1/8的长度，z则使用了 3倍多倘若我们能实现 对于英文中各个字母出 现概率的较准 确的估算，就可以大幅度提高无 损压缩的比例本文描述 在网上能够找到的最简单，最快速的哈夫曼编码本方 法不使用任何扩 展动态库，比如 STL 或者组 件只使用简单的 C 函数，比如： memset， memmove qsort ， malloc ， realloc 和 memcpy因此，大 家都会发现，理解甚至修改这个 编码都是很容易的背景哈夫曼压 缩是个无损的压缩算法，一 般用来压缩文本和程序文件 哈夫曼压缩属 于可变代码长 度算法一族意思是个体符号（例如，文本文件中的字符 ）用一个特定 长度的位序列 替代因此，在文件中出现 频率高的符号，使用短的位序 列，而那些很 少出现的符号 ，则用较长的位序列编码使用我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便你可以 将他们放到类 中，或者直接使用这个函数并且我使用了简 单的格式，仅仅输入输出 缓冲区，而不 象其它文章中那样，输入输出文 件bool CompressHuffman（BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nD esLen）;bool DecompressHuffman（BYTE *pSrc, int nSrcLen, BYTE *&pDes, int & nDesLen）;要点说明速度为了让它 （huffman.cpp） 快速运行，我花了很长时间。
同时，我没 有使用任何动态 库，比如STL或者MFC它压缩1M数据少于100ms（ P3处理器，主频1G）压缩压缩代码 非常简单，首先用 ASCII 值初始化 511 个哈夫曼节点：CHuffmanNode nodes[511];for(int nCount = 0; nCount < 256; nCount++)nodes[nCount].byAscii = nCount;然后，计 算在输入缓冲区数据中，每个 ASCII 码出现的 频率：for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++;然后，根 据频率进行排序：qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);现在，构 造哈夫曼树，获取每个 ASCII 码对应的位序列 ：int nNodeCount = GetHuffmanTree(nodes);构造哈夫 曼树非常简单，将所有的节 点放到一个队列中，用一个 节点替换两个频 率最低的节点，新节点 的频率就是这两个节点的频率 之和。
这样，新节点就是两个被 替换节点的父 节点了如此循环，直到队列中 只剩一个节点(树根)// parent nodepNode = &nodes[nParentNode++];// pop first childpNode->pLeft = PopNode(pNodes, nBackNode--, false);// pop second childpNode->pRight = PopNode(pNodes, nBackNode--, true);// adjust parent of the two poped nodespNode->pLeft->pParent = pNode->pRight->pParent = pNode;// adjust parent frequencypNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFre quency;这里我用 了一个好的诀窍来避免使用任何 队列组件我先前就直到 ASCII 码只有 256 个，但我分配了 511 个(CHuffma nN ode n odes[511])，前 255 个记录 ASCII 码， 而用后 255 个记录哈夫曼树中的父 节点。
并且在构造树的时候 只使用一个指针数组 (C huffmanNode *pNodes[256]) 来指向这些节点同样使用两 个变量来操作队列索引 (i nt nParentNode = nNodeCount;nBackNode = nNodeCount -)接着，压 缩的最后一步是将每个 ASCII 编码写入输出缓 冲区中：int nDesIndex = 0;// loop to write codesfor(nCount = 0; nCount < nSrcLen; nCount++){*(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7);nDesIndex += nodes[pSrc[nCount]].nCodeLength;}(nDesIndex>>3): >>3 以 8 位为 界限右移后到达右边字节的前面(nDesIndex&7): &7 得到最 高位 .注意：在压缩缓冲 区中，我们必须保存哈夫曼树的节点 以及位序列，这样我们才 能在解压缩时 重新构造哈夫曼树(只需保存 ASCII 值和对应 的位序列)。
解压缩解压缩比 构造哈夫曼树要简单的多 ，将输入缓冲区中的每 个编码用对应的 ASCII 码逐个替换就 可以了只要记住 ，这里的输入缓冲区是 一个包含每个 ASCII 值的编码 的位流因此，为了用 ASCII 值替换编码，我们必须用位 流搜索哈夫曼树，直到发现 一个叶节点， 然后将它的 ASCII 值添加到输出缓冲区中：int nDesIndex = 0;DWORD nCode;while(nDesIndex < nDesLen){nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);pNode = pRoot;while(pNode->pLeft){pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;nCode >>= 1;nSrcIndex++;}pDes[nDesIndex++] = pNode->byAscii;}过程#include #include#include#include#include#define M 10typedef struct Fano_Node{char ch;float weight;}FanoNode[M];typedef struct node{int start;int end; struct node *next;}LinkQueueNode;typedef struct{LinkQueueNode *front;LinkQueueNode *rear;}LinkQueue;void EnterQueue(LinkQueue *q,int s,int e){LinkQueueNode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL){NewNode->start=s;NewNode->end=e; NewNode->next=NULL;q->rear->next=NewNode; q->rear=NewNode;}else printf("Error!");}//*** 按权分组 ***//void Divide(FanoNode f,int s,int *m,int e){int i;float sum,sum1;sum=0; for(i=s;i<=e;i++) sum+=f.weight;*m=s;sum1=0; for(i=s;ifabs(sum-2*sum1-2*f.weight)?(i+1):*m; if(*m==i)break;}}main(){int i,j,n,max,m,h[M];int sta,mid,end;float w;char c,fc[M][M];FanoNode FN;LinkQueueNode *p;LinkQueue *Q;//*** 初始化队 Q***//Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); Q->rear=Q->front;Q->front->next=NULL;printf("\t***FanoCoding***\n");printf("Please input the number of node:"); /* 输入信息 */ scanf("%d",&n);i=1;while(i<=n){printf("%d weight and node:",i);scanf("%f %c",&FN.weight,&FN.ch);for(j=1;jfront->next! =NULL) { p=Q->front->next; /*出队 */ Q->front->next=p->next;if(p==Q->rear) Q->rear=Q->front; sta=p->start; end=p->end; free(p);Divide(FN,sta,&m,end); /* 按权分组 */ for(i=sta;i<=m;i++){ fc[h]='0'; h++;} if(sta!=m) EnterQueue(Q,sta,m); else fc[sta][h[sta]]='\0'; for(i=m+1;i<=end;i++) { fc[h]='1'; h++;}if(m==sta&&(m+1)==end) //如果分 组后首元素的下标与中间元素的 相等 { // 并且 和最后元素的下标相差为 1 ，则 编码码字字符串结束 fc[m][h[m]]='\0';fc[end][h[end]]='\0';}elseEnterQueue(Q,m+1,end);}for(i=1;i<=n;i++) /* 打印编码信息 */{ printf("%c:",FN.ch);printf("%s\n",fc);} system("pause");}#include#include#include #include#define N 100#define M 2*N-1typedef char * HuffmanCode[2*M];typedef struct{char weight;int parent;int LChild;int RChild; }HTNode,Huffman[M+1]; typedef struct Node{int weight; /*叶子结 点的权值 */char c; /*叶子结点 */int num; /*叶 子结点的二进制码的长度 */ }WNode,WeightNode[N];/*** 产生叶子结点的字符和权值 ***/void CreateWeight(char ch[],int *s,WeightNode *CW,int *p){int i,j,k;int tag;*p=0;for(i=0;ch!='\0';i++){tag=1;for(j=0;j(*ht)[j].weight?j:s1; (*ht)[s1].parent=i;(*ht).LChild=s1;for(j=1;j<=i-1;j++) if(!(*ht)[j].parent) break;s2=j; /*找到第 一个双亲不为零的结点 */for(;j<=i-1;j++)if(!(*ht)[j].parent) s2=(*ht)[s2].weight>(*ht)[j].weight?j:s2; (*ht)[s2].parent=i;(*ht).RChild=s2;(*ht).weight=(*ht)[s1].weight+(*ht)[s2].weight; }/*********** 叶 子结点的编码***********/void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode de *weight,int m,int n){int i,j,k,c,p,start;char *cd;cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0';for(i=1;i<=n;i++)*h,WeightNo*hc,WeightNhc,int n,intstart=n-1;c=i;p=ht.parent;while(p){start--;if(ht[p].LChild==c) cd[start]='0';elsecd[start]='1';c=p;p=ht[p].parent;}(*weight).num=n-start;(*h)=(char *)malloc((n-start)*sizeof(char));p=-1;strcpy((*h),&cd[start]);}system("pause");}/********* 所有字符的编码 *********/void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode ode weight,int n,int m){int i,j,k;for(i=0;i=n display('Error! You did not input this number.');break end end if k>=n break end r=[];while hf(k,5)==1 kc=n+1;while hf(kc,3)~=k&hf(kc,4)~=k kc=kc+1;end if hf(kc,3)==k r=[0 r];elser=[1 r]; end k=kc;end r else a=input('Please input the metrix you want to Decoding: '); sa=size(a);sa=sa(:,2); k=2*n-1;while sa~=0 if a(:,1)==0 k=hf(k,3);else k=hf(k,4);end a=a(:,2:sa); sa=sa-1;if k==0display('Error! The metrix you entered is a wrong one.');breakendendif k==0breakendr=hf(k,2);rendDecoding\nchoose=input('Please choose what you want: \n1: Encoding\n2: 3:.Exit\n');clcendif choose~=1&choose~=2clc;end。