哈夫曼压缩解压
我写过一个Huffman编码，但只是生成了编码表，没做成压缩，但可以利用查表做成文件压缩，另外用的是C++，改成C的话比较容易，只要把动下内存分配就行了，想要的话,msn:[email protected]
B. 有关哈夫曼编码压缩与解压缩的问题.
压缩代码非常简单，首先用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 node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(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 <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define M 10
typedef 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;i<e;i++)
{
sum1+=f.weight;
*m=fabs(sum-2*sum1)>fabs(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;j<i;j++)
{
if(FN.ch==FN[j].ch)
{
printf("Same node!!!\n");
break;
}
}
if(i==j)
i++;
}
for(i=1;i<=n;i++) /*排序*/
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN.weight<FN[max].weight)
{
w=FN.weight;
FN.weight=FN[max].weight;
FN[max].weight=w;
c=FN.ch;
FN.ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) /*初始化h*/
h=0;
EnterQueue(Q,1,n); /*1和n进队*/
while(Q->front->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';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*打印编码信息*/
{
printf("%c:",FN.ch);
printf("%s\n",fc);
}
system("pause");
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define N 100
#define M 2*N-1
typedef 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<i;j++)
if(ch[j]==ch)
{
tag=0;
break;
}
if(tag)
{
(*CW)[++*p].c=ch;
(*CW)[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch==ch[k])
(*CW)[*p].weight++;
}
}
*s=i;
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman *ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
for(i=1;i<=n;i++)
{
(*ht).weight =w.weight;
(*ht).parent=0;
(*ht).LChild=0;
(*ht).RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
(*ht).weight=0;
(*ht).parent=0;
(*ht).LChild=0;
(*ht).parent=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s1=j; /*找到第一个双亲不为零的结点*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s1=(*ht)[s1].weight>(*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 *h,WeightNode *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++)
{
start=n-1;
c=i;
p=ht.parent;
while(p)
{
start--;
if(ht[p].LChild==c)
cd[start]='0';
else
cd[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 *hc,WeightNode weight,int n,int m)
{
int i,j,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*从(*weight)[k].c中查找与ch相等的下标K*/
if(ch==weight[k].c)
break;
(*hc)=(char *)malloc((weight[k].num+1)*sizeof(char));
for(j=0;j<=weight[k].num;j++)
(*hc)[j]=h[k][j];
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;
for(j=0;hc[j]!='\0';j++)
{
if(hc[j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*打印原信息*/
i++;
}
}
main()
{
int i,n,m,s1,s2,j; /*n为叶子结点的个数*/
char ch[N],w[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*二叉数 */
HuffmanCode h,hc; /* h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,&weight,&n); /*产生叶子结点信息，m为字符串ch[]的长度*/
printf("***WeightInformation***\n Node "); /*输出叶子结点的字符与权值*/
for(i=1;i<=n;i++)
printf("%c ",weight.c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight.weight);
CreateHuffmanTree(&ht,weight,n); /*产生Huffman树*/
printf("\n***HuffamnTreeInformation***\n");
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf("\t%d %d %d %d\n",i,ht.weight,ht.parent,ht.LChild,ht.RChild);
CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*叶子结点的编码*/
printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight.c);
printf("%s\n",h);
}
CrtHuffmanCode(ch,h,&hc,weight,n,m); /*所有字符的编码*/
printf("***StringCode***\n"); /*打印字符串的编码*/
for(i=0;i<m;i++)
printf("%s",hc);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
system("pause");
}
C. 基于哈夫曼树的文件压缩/解压程序 源代码
哈夫曼的C++算法
#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include "stdio.h"
#include "string.h"
#include "malloc.h"
typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子
typedef char Elemtype;
typedef struct TNode{
Elemtype letter;
int weight;
int parent;
Which sigh;
char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//储存代码
char str[ENCODING_LENGTH];//保存要翻译的句子
void InitTreeNode(HuffmanTree &HT)
{//初始前N个结点,后M-N个结点置空
int i;int w;char c;
int m=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
printf("input %d database letter and weight",n);
p=HT;
getchar();
for (i=1;i<=n;i++){
scanf("%c%d",&c,&w);
p->code='\0';
p->letter=c;
p->parent=0;
p->sigh=none;
p->weight=w;
p++;
getchar();
}
for (;i<=m;i++,p++){
p->code='\0';
p->letter=' ';
p->parent=0;
p->sigh=none;
p->weight=0;
}
}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的结点序号
if (HT[i].parent==0&&HT[i].weight<min1){
*s1=i;
min1=HT[i].weight;
}
}
min2=INT_MAX;
for(i=0;i<=end;i++){//找次小结点的序号
if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
*s2=i;
min2=HT[i].weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree &HT)
{//建立HUFFMAN树
int i;int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left_child;
HT[s2].sigh=right_child;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void HuffmanTreeCode(HuffmanTree HT)
{//HUFFMAN译码
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
p=i;
s=n-1;
while (HT[p].parent!=0){//从结点回溯,左孩子为0,右孩子为1
if (HT[p].sigh==left_child)
temp[--s]='0';
else if (HT[p].sigh==right_child)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间
strcpy(HT[i].code,temp+s);
printf("%s\n",HT[i].code);
}
}
void GetCodingSen(char *sencence)
{//输入要编码的句子
int l;
gets(sencence);
l=strlen(sencence);
sencence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT)
{//将句子进行编码
int i=0;int j;
while(sen[i]!='\0'){
for(j=0;j<n;j++){
if (HT[j].letter==sen[i]) //字母吻合则用代码取代
{strcat(coding,HT[j].code);
break;
}
}
i++;
if (sen[i]==32) i++;
}
printf("\n%s",coding);
}
void HuffmanTreeDecoding(HuffmanTree HT,char code[])
{//HUFFMAN译码过程,将代码翻译为句子
char sen[100];
char temp[50];
char voidstr[]=" ";
int i;int j;
int t=0;int s=0;
for(i=0;i<strlen(code);i++){
temp[t++]=code[i];
for(j=0;j<n;j++){
if (strcmp(HT[j].code,temp)==0){//代码段吻合
sen[s]=HT[j].letter;s++;
strcpy(temp,voidstr);//将TEMP置空
t=0;
break;
}
}
}
printf("\n%s",sen);
}
void main()
{
HTNode hnode;
HuffmanTree huff;
huff=&hnode;
printf("input the letter for coding number\n");
scanf("%d",&n);
InitTreeNode(huff);
HuffmanTreeCreat(huff);
HuffmanTreeCode(huff);
GetCodingSen(str);
HuffmanTreeEncoding(str,huff);
HuffmanTreeDecoding(huff,coding);
}
D. 基于哈夫曼树的文件压缩与解压算法（C++版）
static unsigned int out = 0x01;
void write_bit(bool bit)
{
out <<= 1; // shift byte to make room
if (bit) out |= 0x01; // set lowest bit id desired
if (out & 0x100) { // was the sentinel bit shifted out?
write_byte(out & 0xff); // final output of 8-bit chunk
out = 0x01; // reset to sentinel vylue
}
}
void flush_bit()
{
while (out != 0x01) write_bit(false);
}
int main()
{
write_bit(1);
write_bit(0);
write_bit(1);
// ...
flush_bit();
return 0;
}
E. 如何用哈夫曼编码实现英文文本的压缩和解压缩
根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。
F. 算法解析：哈夫曼（huffman）压缩算法
本篇将介绍 哈夫曼压缩算法（Huffman compression）
众所周知，计算机存储数据时，实际上存储的是一堆0和1（二进制）。
如果我们存储一段字符：ABRACADABRA!
那么计算机会把它们逐一翻译成二进制，如A：01000001；B: 01000010; !: 00001010.
每个字符占8个bits, 这一整段字符则至少占12*8=96 bits。
但如果我们用一些特殊的值来代表这些字符，如：
图中，0代表A; 1111代表B；等等。此时，存储这段字符只需30bits，比96bits小多了，达到了压缩的目的。
我们需要这么一个表格来把原数据翻译成特别的、占空间较少的数据。同时，我们也可以用这个表格，把特别的数据还原成原数据。
首先，为了避免翻译歧义，这个表格需满足一个条件： 任何一个字符用的值都不能是其它字符的前缀 。
我们举个反例：A: 0; B: 01;这里，A的值是B的值的前缀。如果压缩后的数据为01xxxxxx,x为0或者1，那么这个数据应该翻译成A1xxxxxx, 还是Bxxxxxxx?这样就会造成歧义。
然后，不同的表格会有不同的压缩效果，如：
这个表格的压缩效果更好。
那么我们如何找到 最好的表格 呢？这个我们稍后再讲。
为了方便阅读，这个表格是可以写成一棵树的：
这棵树的节点左边是0，右边是1。任何含有字符的节点都没有非空子节点。（即上文提及的前缀问题。）
这棵树是在压缩的过程中建成的，这个表格是在树形成后建成的。用这个表格，我们可以很简单地把一段字符变成压缩后的数据，如：
原数据：ABRACADABRA!
表格如上图。
令压缩后的数据为S；
第一个字符是A，根据表格，A：11，故S=11;
第二个字符是B，根据表格，B：00，故S=1100;
第三个字符是R，根据表格，R：011，故S=1100011;
如此类推，读完所有字符为止。
压缩搞定了，那解压呢？很简单，跟着这棵树读就行了：
压缩后的数据S=11000111101011100110001111101
记住，读到1时，往右走，读到0时，往左走。
令解压后的字符串为D；
从根节点出发，第一个数是1，往右走：
第二个数是1，往右走：
读到有字符的节点，返回此字符，加到字符串D里。D:A;
返回根节点，继续读。
第三个数是0，往左走：
第四个数是0，往左走：
读到有字符的节点，返回此字符，加到字符串D里。D:AB;
返回根节点，继续读。
第五个数是0，往左走：
第六个数是1，往右走：
第七个数是1，往右走：
读到有字符的节点，返回此字符，加到字符串D里。D:ABR;
返回根节点，继续读。
如此类推，直到读完所有压缩后的数据S为止。
压缩与解压都搞定了之后 我们需要先把原数据读一遍，并把每个字符出现的次数记录下来。如：
ABRACADABRA!中，A出现了5次;B出现了2次;C出现了1次;D出现了1次;R出现了2次;!出现了1次。
理论上，出现频率越高的字符，我们给它一个占用空间越小的值，这样，我们就可以有最佳的压缩率
由于哈夫曼压缩算法这块涉及内容较多 ，文章篇幅很长；全文全方面讲解了Compose布局的各方面知识。更多Android前言技术进阶，我自荐一套《 完整的Android的资料，以及一些视频课讲解 》 现在私信发送“进阶”或者“笔记”即可免费获取
最后我想说：
对于程序员来说，要学习的知识内容、技术有太多太多，要想不被环境淘汰就只有不断提升自己，从来都是我们去适应环境，而不是环境来适应我们
技术是无止境的，你需要对自己提交的每一行代码、使用的每一个工具负责，不断挖掘其底层原理，才能使自己的技术升华到更高的层面
Android 架构师之路还很漫长，与君共勉
G. 霍夫曼 解压缩
哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由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 &nDesLen);
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 node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(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;
}
H. 哈夫曼压缩文件如何选中目标文件
方法如下：
1、首先，我们打开我们电脑上面的excel，然后我们在任意一个单元格中输入文字；
2、然后我们点击图示中的那个按钮；
3、然后我们任意点击一个单元格，之后我们点击图示中的下拉箭头，弹出的界面，我们点击粘贴；
4、之后我们就可以看到被我们粘贴了，我们点击任意的单元格，然后都可以按照之前的方法进行粘贴。
I. 如何用哈夫曼编码实现英文文本的压缩和解压缩
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列
J. Huffman编码可以破解加密的压缩文件嘛
你说的应该是WinRAR这个软件加密的压缩文件吧。
Huffman编码是不可也破解的，Huffman编码可以压缩与解压缩文件，只有用Huffman编码压缩的文件才能用Huffman编码解压缩。简单讲，就是用Huffman编码加密的文件，才能用Huffman编码解密。
WinRAR这个软件加密的压缩文件是目前比较安全的加密，目前网上已知的破解方法只有暴力破解。理论上讲，密码都可以用暴力破解出来；实际上，11位以上的密码，包含数字、字母、符号的密码是无法破解出来的。
如果你的密码是纯数字（9位以下，包含9位），一般可以破解出来。