哈夫曼编译问题算法分析

A. 哈夫曼译码算法

C++的
#include<stdlib.h>
#include<fstream.h>
#include<iomanip.h>
#include<windows.h>
ofstream outstuf;
#define MAXBIT 50 // 哈夫曼编码的最大长度
#define MAXVALUE 50 // 最大权值
#define MAXLEAF 50 // 哈夫曼树中叶子结点个数
#define MAXNODE MAXLEAF*2-1 //树中结点总数
//哈夫曼树结点结构
typedef struct
{
char data ; //结点值
int weight; //权值
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}HNodeType;
HNodeType HuffNode[MAXNODE];
//存放哈夫曼编码的数据元素结构
typedef struct
{
int bit [MAXBIT]; //存放哈夫曼码
int start; //编码的起始下标
}HCodeType;
void Haffmanfile(int n); //保存文件
HNodeType *HaffmanTree(int n) ; //构造哈夫曼树
void Haffmancode(int n); //构造哈夫曼编码
HNodeType *HaffmanTree(int n) //构造哈夫曼树
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) //所有结点的初始化
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
cout<<"\t________________________________________"<<endl;
cout<<"\t输入叶子结点的值和权值"<<endl;
cout<<"\t________________________________________"<<endl;
for(i=0;i<n;i++)
{
cout<<"\t______________________"<<endl;
cout<<"\t输入第"<<i+1<<"个叶子节点的值: ";
cin>>HuffNode[i].data;
cout<<"\t输入第"<<i+1<<"个叶子节点的权值: ";
cin>>HuffNode[i].weight;
}
for(i=0;i<n-1;i++) //构造哈夫曼树
{ m1=m2=MAXVALUE; x1=x2=0;
for(j=0;j<n+i;j++)
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) //只在尚未构造二叉树的结点中查找
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//将找出的两棵权值最小的子树合并为一棵子树
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
return HuffNode;
}
//构造哈夫曼编码
void Haffmancode(int n)
{
int i,j,c,p;
HNodeType *HuffNode=new HNodeType[MAXNODE];
HCodeType *HuffCode=new HCodeType[MAXLEAF];
HCodeType *cd=new HCodeType;
HuffNode=HaffmanTree(n); //建立哈夫曼树
for(i=0;i<n;i++)
{
cd->start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) //循环直到树根结点
{
if(HuffNode[p].lchild==c)
cd->bit[cd->start]=0; //处理左孩子结点
else
cd->bit[cd->start]=1; //处理右孩子结点
cd->start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd->start+1;j<n;j++)
HuffCode[i].bit[j]=cd->bit[j];
HuffCode[i].start=cd->start; //指向哈夫曼编码最开始字符
}
cout<<"\n\t每个叶子结点的值及对应的哈夫曼编码"<<endl;
for(i=0;i<n;i++)
{ cout<<"\t****************************************"<<endl;
cout<<"\t第"<<i+1<<"个叶子结点的值和哈夫曼编码为:";
cout<<HuffNode[i].data<<" ";
for(j=HuffCode[i].start+1;j<n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
outstuf.open("bianma.txt",ios::out);
outstuf<<"____________\n哈夫曼编码:\n____________ "<<endl;
for(i=0;i<n;i++)
{
for(j=HuffCode[i].start+1;j<n;j++)
outstuf<<HuffCode[i].bit[j]<<" ";
outstuf<<endl;
}
cout<<"\t\t*******************"<<endl;
cout<<"\t\t哈夫曼编码保存成功!"<<endl;
cout<<"\t\t*******************"<<endl;
outstuf.close();
Haffmanfile(n);
}
void Haffmanfile(int n)
{
char s[80];
int a[20],i=0,r;
ifstream instuf("bianma.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打开!"<<endl;
abort();
}
instuf.getline(s,80);
while(instuf>>a[i])
i++;
for(r=0;r<i;r++) cout<<a[r]<<" ";
if(a[0]!=0&&a[0]!=1)
{
cout<<"此文件无内容!"<<endl;
abort();
}
instuf.close();
int p=0,j=0,k=0; char zu[10],ch;
system("pause");system("cls");
cout<<"\n\t\t*************************************"<<endl;
cout<<"\t\t是否要对原编码进行译码操作 (Y or N)?:\t";
cin>>ch;
if(ch=='N'||ch=='n') return;
for(r=0;r<n;r++)
{
p=2*n-2;
while(HuffNode[p].lchild!=-1&&HuffNode[p].rchild!=-1)
{
if(a[j]==0) p=HuffNode[p].lchild;
if(a[j]==1) p=HuffNode[p].rchild;
j++;
}
zu[k]=HuffNode[p].data;
k++;
}
outstuf.open("yima.txt",ios::out);
outstuf<<"译码为: "<<endl;
for(j=0;j<n;j++) outstuf<<HuffNode[j].data<<" ";
outstuf<<endl;
cout<<"\t\t**************\n\t\t译码保存成功!\n\t\t**************"<<endl;
outstuf.close();
instuf.open("yima.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打开!"<<endl;
abort();
}
instuf.getline(s,80);
i=0;
cout<<"\n\t\t哈夫曼编码的译码为: ";
while(instuf>>zu[i])
{cout<<zu[i]<<" ";
i++;
}
cout<<endl;
instuf.close();
}
void main()
{
int n,i;char choice;system("cls");system("color 80");
cout<<"\t _______________________________________________________"<<endl;
cout<<"\t 本演示系统可以良好的演示哈夫曼编码和译码的产生,"<<endl;
cout<<"\t 但本程序有一定的不完善，用户可以随时到CSDN社区关注更新!"<<endl;
cout<<"\t _______________________________________________________"<<endl;
loop:
cout<<"\t\t _________________________________\n\n";
cout<<"\t\t 1.哈夫曼演示系统 0.退出演示系统\n";
cout<<"\t\t _________________________________\n\n\t请选择\t";
cin>>choice;
switch(choice)
{case '1': system("cls");
cout<<"\t\t _____________________________\n\n";
cout<<"\t\t\t请输入叶子结点个数:\t";
cin>>n;
Haffmancode(n);
cout<<"\n\t*********输出哈夫曼树!**********"<<endl;
cout<<"\t字符 "<<"权值 "<<"左孩子指针 "<<"右孩子指针"<<endl;
for( i=0;i<2*n-1;i++)
{cout<<"\t";
cout<<setw(5)<<HuffNode[i].data<<setw(5)<<HuffNode[i].weight<<setw(5)<<
HuffNode[i].lchild<<setw(5)<<HuffNode[i].rchild<<setw(5)<<
HuffNode[i].parent<<endl;
}
system("pause");system("cls");goto loop;break;
case '0':break;
}
}

B. 哈夫曼编码原理

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。

(2)哈夫曼编译问题算法分析扩展阅读

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率
和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相
加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，
将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵为2.61bit，二者已经是很接近了。

C. 叙述哈夫曼算法的思想

运行过了没有任何问题,有什么问题可以交流下.
#include
#include
#define N 6
typedef struct
{

int W,P,R,L;
}HTNode;
typedef struct
{
char ch;
char code[10];
}HTCode;
HTCode HC[27];
void select(HTNode HT[],int *min1,int *min2,int *a,int *b)
{

int i;int mina=100,minb=100;
int m,n;

for(i=1;i

D. 请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。

这个讲的相当清楚。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）
然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。一般的数据结构的书中都可以找到其描述：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight; /*权值*/
union{
char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/
};
struct tree *right; /*树的右结点*/
};
struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/
};
例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。 静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

E. 哈夫曼编码码长怎么算

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。

实际应用中

除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。

按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。

F. 哈夫曼编码（贪心算法）

参考： 哈夫曼编码

哈夫曼编码是一种十分有效的编码方法，广泛应用于 数据压缩 中
通过采用 不等长 的编码方式，根据 字符频率的不同 ，选择 不同长度的编码 ，对频率 越高 的字符采用 越短 的编码实现数据的高度压缩。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。

下面看一个例子：
假如我们有一个包含1000个字符的文件，每个字符占1个byte(1byte=8bits)，则存储这100个字符一共需要8000bits。这还是有一些大的
那我们统计一下这1000个字符中总共有多少种字符，原来需要8bit来表示一个字符，如果使用更少的位数来表示这些字符，则可以减少存储空间。
假设这1000个字符中总共有a、b、c、d、e、f共6种字符，使用使用3个二进制位来表示的话，存储这1000个字符就只需要3000bits，比原来更节省存储空间。

或许还可以再压缩一下：
根据字符出现的 频率 给与字符 不等长 的编码，频率越高的字符编码越短，频率越低的字符编码越长。
它不能像等长编码一样直接按固定长度去读取二进制位，翻译成字符，为了能够准确读取翻译字符，它要求一个字符的编码不能是另外一个字符的前缀。

假设a、b、c、d、e、f这6个字符出现的频率依次降低，则我们可以给与他们这样的编码

假如字符的出现频率如图所示，按照这样的编码表示的话，总位数如图，一共2100bits，更加节省空间了

贪心策略：频率小的字符，优先入队。

步骤：
1.将每一个字符作为节点，以出现频率大小作为权重，将其都放入 优先队列 中（一个最小堆）；
2.每次出队两个节点并创建一个父节点，使其权值为刚刚出队的节点的权值和，并且为两个节点的父节点（合并）。然后将这个树入队。
3.重复操作2，直到队列中只有一个元素（此时这个元素表示形式应该为一个树）时，完成创建。

创建好了树，该怎么编码呢？
我们对一个哈夫曼树，从父节点开始的所有节点，往左边标0，右边标1。那么到达叶子节点的顺次编码就可以找到了。

C：字符集合
Q：优先队列
EXTRACT-MIN：传入一个队列，出队最小的元素
INSERT：将z插入到Q中

当for循环结束之后，此时队列中只有一个元素，就是我们需要的哈夫曼树，最后返回此树即可。

假设T树已经是一个最优的树，假设x、y的频率小于等于最低处的a、b，然后交换x、a，y、b。

计算代价是否发生变化。
比如这里比较 T 变成 T ’ 后代价是否变化，发现代价变小或不变。

同理T’到T’’，又因为T本来假设就是最优的，所以只能相等
所以T’’也应该符合条件，即贪婪算法，每次取最小的两个节点出来这种做法是正确的

G. 算法解析：哈夫曼（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 架构师之路还很漫长，与君共勉