哈夫曼算法怎么用

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

参考： 哈夫曼编码

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

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

⑵ 哈夫曼编码码长怎么算

设某信源产生有五种符号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。

⑶ 如何写压缩软件，运用哈夫曼算法实现

到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。然而，还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构，以前还不知道他又什么用，其实他最大的用途就是用来做压缩，也是一些rar,zip压缩的祖先，称为哈弗曼压缩（什么你不知道谁是哈弗曼，也不知道哈弗曼压缩，不急等下介绍）。

随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

一、什么是哈弗曼压缩

Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

二、怎么实现哈弗曼压缩

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

故我们得了解几个概念：

1、二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。2、哈夫曼编码(Huffman Coding)：是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。三、哈夫曼编码生成步骤：

①扫描要压缩的文件，对字符出现的频率进行计算。

②把字符按出现的频率进行排序，组成一个队列。

③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。

④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。

⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。

⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。

既如 (a)、(b)、(c)、(d)几个图，就可以将离散型的数据转化为树型的了。

如果假设树的左边用0表示右边用1表示，则每一个数可以用一个01串表示出来。

则可以得到对应的编码如下：
1-->110
2-->111
3-->10
4-->0
每一个01串，既为每一个数字的哈弗曼编码。
为什么能压缩：
压缩的时候当我们遇到了文本中的1、2、3、4几个字符的时候，我们不用原来的存储，而是转化为用它们的01串来存储不久是能减小了空间占用了吗。（什么01串不是比原来的字符还多了吗？怎么减少？）大家应该知道的，计算机中我们存储一个int型数据的时候一般式占用了2^32-1个01位，因为计算机中所有的数据都是最后转化为二进制位去存储的。所以，想想我们的编码不就是只含有0和1嘛，因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
比如：
1这个数字，用整数写进计算机硬盘去存储，占用了2^32-1个二进制位
而如果用它的哈弗曼编码去存储，只有110三个二进制位。
效果显而易见。

⑷ 请问怎样使用哈夫曼树(pascal语言）

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

Program huffman_tree(input,output);
const max=32767;n=20;m=2*n-1
Type tnode=RECORD
data:integer;
Lc,Rc:integer;
END;
Var tree:ARRAY[0..m] of tnode;
weight:ARRAY[0..n] of integer;
im,num:integer;

procere initial;
var i:integer;
begin
write('First input nun(<',n:2,')');
readln(num);
writeln('Please input weight:');
for i:=0 to num-1 do read(weight[i])
end;

function minimum:integer;
var i:integer;
begin
min:=max;
for i:=0 to num-1 do
if (min>weight[i]) then
begin
min:=weight[i];
im:=i;
end;
weight[im]:=max;
minimum:=min;
end;

procere huffman;
var i,k:integer;
begin
for i:=num to 2*num-1 do
begin
tree[i].Lc:=minimum;
tree[i].Rc:=minimum;
tree[i].data:=tree[i].Lc:+tree[i].Rc;
weight[im]:=tree[i].data
end;
writeln;
writeln('The result of huffman tree:');
k:=1;
for i:=2*num-2 downto num do
begin
write(tree[i].data:6,':',tree[i].Lc:3,tree[i].Rc:3);
if (k mod 3=0) then writeln; k:=k+1;
end
writeln
end;

procere printd;
var i:integer;
begin
write('The weight of tree:');
for i:=0 to num-1 do
write{weight[i]:3}
end;

begin {main}
initial;
printd;
huffman;
end.

⑸ 什么是哈夫曼算法

有一种树形结构叫哈夫曼树，用哈夫曼树的方法解编程题的算法就叫哈夫曼算法，其实也没有哈夫曼算法这个专有名词了拉，你这么问我就这么跟你讲把。它产生的代码是
#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]);
}

⑹ 哈夫曼树算法

题目的阐述：以N进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入0，1，2，．．．，N－1构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．如：N＝3英文原串为ABBCBADDACE其对应的一种编码方式为A：00B：01C：020D：021E：022原串对译后的编码为000101020010002102100020022其码长为27若输入编码串0102002200则对应的英文原串为BCEA 分析： 假设英文原串中的字符存放于字符集S中，‖S‖＝X，每个字符在字串中出现的概率为W［i］，L［i］为字符i的编码长．依题意得，对S集合中的不同字符进行N进制编码后要求1）新字串的码长最短WPL＝∑W［i］＊L［i］
（i∈1．．X）使得在WPL是所有编码方式中的最小值2）编码无二义性任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．N为此哈夫曼树的分叉数，S字符集里的元素即为此N叉哈夫曼树的叶子，概率W［i］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长L［i］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．但具体应该怎样建立起此N叉哈夫曼树呢？我们首先以N＝2为例：S＝｛A，B，C，D｝W＝［3，1，2，1］首先从W中选出两个最小权，1，1，将其删去，并以2（即1＋1）替代W＝［3，2，2］；再从新的W中取出两个最小权，2，2，将其删去，并以4（即2＋2）替代W＝［3，4］；依此类推，直到W中只一个值时合并结束，此时W＝［7］以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下： m0åæ1mmA0åæ1mmC0åæ1mmBD MIN－WPL＝3＊1＋1＊3＋2＊2＋1＊3＝13 从某一根结点出发走向其左子树标记为0，走向其右子树标记为1，则可以得到以下编码A，B，C，D对应的编码为A：0B：110C：10D：111
N＝3时又是怎样一种情况呢？设S＝｛A，B，C，D，E｝W＝［7，4，2，5，3｝则按权重排序可得S＝｛D，B，E，C，A｝W＝［7，5，4，3，2］那么此哈夫曼树的树形应为怎样呢？是以下的左图，还是右图，或是两者均不是mmåâæåæmmllmåæåæCAåælllllmADBEDåæ
lmBåællEC 显然，要带权路径长WPL最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满N叉树是最合理的，于是我们尽量使树每一层都为N个分枝．对于这道题的情况，我们具体来分析．按照哈夫曼树的思想，首先从W中取出权最小的三个值，即2，3，4，并以9（2＋3＋4）来代替，得到新的W＝［9，7，5］；再将这三个值合并成9＋7＋5＝21这个结点．于是得到三叉哈夫曼树如下：måâællmDBåâælllECAWPL＝1＊7＋1＊5＋2＊2＋2＊3＋2＊4＝30以0．．N－1依次标记每个根结点的N个分枝，则可以得到每个字符相对应的编码：A：22B：1C：21D：0E：20我们发现对于这种情况恰巧每层均为N个分枝，但事实上并非所有的N叉哈夫曼树都可得到每层N个分枝．例于当N＝3，‖S‖＝6时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢？最简单的处理方式就是添加若干出现概率为0的空字符填补在N叉树的最下一层，这些权为0的虚结点并无实际意义但却非常方全便于这棵N叉树的建立．空字符的添加个数add的计算如下：Y＝‖S‖mod（n－1）add＝0（Y＝1）add＝1（Y＝0）add＝N－Y（Y＞1） 虚结点的加入使得权重最小的N－add个字符构成了距根结点最远的分枝，使其它字符构成的N叉树保持了丰满的N叉结构．例：N＝3S＝｛A，B，C，D，E，F｝W＝［1，2，3，4，5，6｝则y：＝6mod（3－1）＝0add＝1于是构成N叉树如下：­为虚结点¡åâællmFEåâællmDCåâæBA­WPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33对应编码为：A：221B：220C：21D：20E：1F：0

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

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

⑻ 哈夫曼树算法

题目的阐述：以Ｎ进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入０，１，２，．．．，Ｎ－１构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．如：Ｎ＝３英文原串为ＡＢＢＣＢＡＤＤＡＣＥ其对应的一种编码方式为Ａ：００Ｂ：０１Ｃ：０２０Ｄ：０２１Ｅ：０２２原串对译后的编码为０００１０１０２００１０００２１０２１０００２００２２其码长为２７若输入编码串０１０２００２２００则对应的英文原串为ＢＣＥＡ 分析： 假设英文原串中的字符存放于字符集Ｓ中，‖Ｓ‖＝Ｘ，每个字符在字串中出现的概率为Ｗ［ｉ］，Ｌ［ｉ］为字符ｉ的编码长．依题意得，对Ｓ集合中的不同字符进行Ｎ进制编码后要求１）新字串的码长最短ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］ （ｉ∈１．．Ｘ）使得在ＷＰＬ是所有编码方式中的最小值２）编码无二义性任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．Ｎ为此哈夫曼树的分叉数，Ｓ字符集里的元素即为此Ｎ叉哈夫曼树的叶子，概率Ｗ［ｉ］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长Ｌ［ｉ］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．但具体应该怎样建立起此Ｎ叉哈夫曼树呢？我们首先以Ｎ＝２为例：Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ｝Ｗ＝［３，１，２，１］首先从Ｗ中选出两个最小权，１，１，将其删去，并以２（即１＋１）替代Ｗ＝［３，２，２］；再从新的Ｗ中取出两个最小权，２，２，将其删去，并以４（即２＋２）替代Ｗ＝［３，４］；依此类推，直到Ｗ中只一个值时合并结束，此时Ｗ＝［７］以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下： m０�0�2�0�3１mmＡ０�0�2�0�3１mmＣ０�0�2�0�3１mmＢＤ ＭＩＮ－ＷＰＬ＝３＊１＋１＊３＋２＊２＋１＊３＝１３ 从某一根结点出发走向其左子树标记为０，走向其右子树标记为１，则可以得到以下编码Ａ，Ｂ，Ｃ，Ｄ对应的编码为Ａ：０Ｂ：１１０Ｃ：１０Ｄ：１１１ Ｎ＝３时又是怎样一种情况呢？设Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝Ｗ＝［７，４，２，５，３｝则按权重排序可得Ｓ＝｛Ｄ，Ｂ，Ｅ，Ｃ，Ａ｝Ｗ＝［７，５，４，３，２］那么此哈夫曼树的树形应为怎样呢？是以下的左图，还是右图，或是两者均不是mm�0�2�0�9�0�3�0�2�0�3mmllm�0�2�0�3�0�2�0�3ＣＡ�0�2�0�3lllllmＡＤＢＥＤ�0�2�0�3 lmＢ�0�2�0�3llＥＣ 显然，要带权路径长ＷＰＬ最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满Ｎ叉树是最合理的，于是我们尽量使树每一层都为Ｎ个分枝．对于这道题的情况，我们具体来分析．按照哈夫曼树的思想，首先从Ｗ中取出权最小的三个值，即２，３，４，并以９（２＋３＋４）来代替，得到新的Ｗ＝［９，７，５］；再将这三个值合并成９＋７＋５＝２１这个结点．于是得到三叉哈夫曼树如下：m�0�2�0�9�0�3llmＤＢ�0�2�0�9�0�3lllＥＣＡＷＰＬ＝１＊７＋１＊５＋２＊２＋２＊３＋２＊４＝３０以０．．Ｎ－１依次标记每个根结点的Ｎ个分枝，则可以得到每个字符相对应的编码：Ａ：２２Ｂ：１Ｃ：２１Ｄ：０Ｅ：２０我们发现对于这种情况恰巧每层均为Ｎ个分枝，但事实上并非所有的Ｎ叉哈夫曼树都可得到每层Ｎ个分枝．例于当Ｎ＝３，‖Ｓ‖＝６时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢？最简单的处理方式就是添加若干出现概率为０的空字符填补在Ｎ叉树的最下一层，这些权为０的虚结点并无实际意义但却非常方全便于这棵Ｎ叉树的建立．空字符的添加个数ａｄｄ的计算如下：Ｙ＝‖Ｓ‖ｍｏｄ（ｎ－１）ａｄｄ＝０（Ｙ＝１）ａｄｄ＝１（Ｙ＝０）ａｄｄ＝Ｎ－Ｙ（Ｙ＞１） 虚结点的加入使得权重最小的Ｎ－ａｄｄ个字符构成了距根结点最远的分枝，使其它字符构成的Ｎ叉树保持了丰满的Ｎ叉结构．例：Ｎ＝３Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝Ｗ＝［１，２，３，４，５，６｝则ｙ：＝６ｍｏｄ（３－１）＝０ａｄｄ＝１于是构成Ｎ叉树如下：�0�2为虚结点�0�3�0�2�0�9�0�3llmＦＥ�0�2�0�9�0�3llmＤＣ�0�2�0�9�0�3ＢＡ�0�2ＷＰＬ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３对应编码为：Ａ：２２１Ｂ：２２０Ｃ：２１Ｄ：２０Ｅ：１Ｆ：０

⑼ 哈夫曼编码的应用

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

⑽ 哈夫曼算法

计算过程如图所示：