哈夫曼算法的基本思路

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

这个讲的相当清楚。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为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就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

❷ 霍夫曼算法

霍夫曼算法的步骤是这样的：

·从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。
·然后从节点序列中去除这两个节点，加入它们的父节点到序列中。

重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。

仍以上面的例子来看霍夫曼树的建立过程。
最初的节点序列是这样的：
a(6) b(15) c(2) d(9) e(1)

把最小的c和e结合起来
| (3)
a(6) b(15) d(9) +------+------+
| |
c e

不断重复，最终得到的树是这样的：

根
|
+-----33-----+
| |
15 +----18----+
| |
9 +------9-----+
| |
6 +--3--+
| |
2 1

这时各个字符的编码长度和前面我们说过的方法得到的编码长度是相同的，因而文件的总长度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼树的建立过程中的每一步的节点序列的变化：

6 15 2 9 1
6 15 9 3
15 9 9
15 18
33

下面我们用逆推法来证明对于各种不同的节点序列，用霍夫曼算法建立起来的树总是一棵最优二叉树：

对霍夫曼树的建立过程运用逆推法：
当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。
然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：
1.按照霍夫曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。
2.这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。
3.只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。

这样一步步逆推下去，在这个过程中霍夫曼树每一步都始终保持着是一棵最优二叉树。

由于每一步都从节点序列中删除两个节点，新增一个节点，霍夫曼树的建立过程共需 (原始节点数 - 1) 步，所以霍夫曼算法不失为一种精巧的编码式压缩算法。

附：对于 huffman 树，《计算机程序设计艺术》中有完全不同的证明，大意是这样的：
1．二叉编码树的内部节点（非叶子节点）数等于外部节点（叶子节点）数减1。
2．二叉编码树的外部节点的加权路径长度（值乘以路径长度）之和，等于所有内部节点值之和。（这两条都可以通过对节点数运用数学归纳法来证明，留给大家做练习。）
3．对 huffman 树的建立过程运用逆推，当只有一个内部节点时，肯定是一棵最优二叉树。
4．往前步进，新增两个最小的外部节点，它们结合在一起产生一个新的内部节点，当且仅当原先的内部节点集合是极小化的，加入这个新的内部节点后仍是极小化的。（因为最小的两个节点结合在一起，并处于最低层，相对于它们分别和其他同层或上层节点结合在一起，至少不会增加加权路径长度。）
5．随着内部节点数逐个增加，内部节点集合总维持极小化。

2．实现部分
如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析 zip 算法是如何解决这些难题的，其中很多问题带有普遍意义，比如查找匹配，比如数组排序等等，这些都是说不尽的话题，让我们深入其中，做一番思考。

❸ 叙述哈夫曼算法的思想

运行过了没有任何问题,有什么问题可以交流下.
#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

❹ 哈夫曼编码与译码的算法思想

最基本的思想是出现的多的字符用短编码表达，出现的少的用长编码表达
目的是最小化 \sum_{所有字符} freq(字符)×codelen(字符)

更进一步是通过贪心保证编码在上述意义上最优
具体的重复每次选取两个出现频率最低的字符将之合并作为一个整体，其出现频率为原始两者相加。直到只剩一个整体为止，之后再根据合并将各个字符展开，每个字符的编码极为从根到该字符的路径。

❺ 哈夫曼树译码的算法思路，语言描述即可

你讲的是实现时的语言注释，还是他的实现过程

❻ 什么是哈夫曼算法

有一种树形结构叫哈夫曼树，用哈夫曼树的方法解编程题的算法就叫哈夫曼算法，其实也没有哈夫曼算法这个专有名词了拉，你这么问我就这么跟你讲把。它产生的代码是
#include"stdio.h"
#include"stdlib.h"
#include"string.h"

typedef char ElemType;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // save the information of the symbolizes;

void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);

Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;

printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}

HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;

}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1)
return;

m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;++i)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}

for(;i<=m;++i)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}

for(i=n+1;i<=m;++i)
{
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}

(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
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';
else cd[--start]='1';
}

(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}

void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;

}

if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
} // end of else if
} // end of if
} // end of for

if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
return;
}

void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}

❼ 哈夫曼编码压缩概念的基本思想如何回答(精简的说)

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

❽ 哈夫曼编码（贪心算法）

参考： 哈夫曼编码

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

下面看一个例子：
假如我们有一个包含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’’也应该符合条件，即贪婪算法，每次取最小的两个节点出来这种做法是正确的

❾ 哈夫曼编码原理

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

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

(9)哈夫曼算法的基本思路扩展阅读

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率
和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成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，二者已经是很接近了。

❿ 哈夫曼压缩算法的内容是什么

注:哈夫曼和lzss算法不是同一种算法,先用哈夫曼再用lzss算法压缩后会发现经哈夫曼压缩后再用lzss压缩文件会变大,具体原因不明
lzss原理:
把编码位置置于输入数据流的开始位置。
在前向缓冲器中查找窗口中最长的匹配串
①
pointer
：=匹配串指针。
②
length
：=匹配串长度。
判断匹配串长度length是否大于等于最小匹配串长度(min_length)
，
如果“是”：输出指针，然后把编码位置向前移动length个字符。
如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。
如果前向缓冲器不是空的，就返回到步骤2。
例：编码字符串如表03-05-3所示，编码过程如表03-05-4所示。现说明如下：
“步骤”栏表示编码步骤。
“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
“匹配”栏表示窗口中找到的最长的匹配串。
“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
“输出”栏的输出为：
①
如果匹配串本身的长度length
>=
min_length，输出指向匹配串的指针，格式为(back_chars，
chars_length)。该指针告诉译码器“在这个窗口中向后退back_chars个字符然后拷贝chars_length个字符到输出”。
②
如果匹配串本身的长度length
>=
min_length，则输出真实的匹配串。
表:输入数据流
位置
1234567891011
字符
aabbcbbaabc
表:编码过程(min_length
=
2)
步骤位置匹配串输出
11--a
22aa
33--
b
44bb
55--c
66b
b(3,2)
78
a
a
b(7,3)
811cc