哈夫曼的编码

哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。） 而且哈夫曼编码是按照子树到父亲，而其读码则是完全相反的。 因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。

前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

哈夫曼树的构造算法。

const maxvalue= 10000; {定义最大权值}

maxleat=30; {定义哈夫曼树中叶子结点个数}

maxnode=maxleaf*2-1;

type HnodeType=record

weight: integer;

parent: integer;

lchild: integer;

rchild: integer;

end;

HuffArr:array[0..maxnode] of HnodeType;

var ……

procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼树的构造算法}

var i,j,m1,m2,x1,x2,n: integer;

begin

readln(n); {输入叶子结点个数}

for i:=0 to 2*n-1 do {数组HuffNode[ ]初始化}

begin

HuffNode.weight=0;

HuffNode.parent=-1;

HuffNode.lchild=-1;

HuffNode.rchild=-1;

end;

for i:=0 to n-1 do read(HuffNode.weight); {输入n个叶子结点的权值}

for i:=0 to n-1 do {构造哈夫曼树}

begin

m1:=MAXVALUE; m2:=MAXVALUE;

x1:=0; x2:=0;

for j:=0 to n+i-1 do

if (HuffNode[j].weight<m1) and (HuffNode[j].parent=-1) then

begin m2:=m1; x2:=x1;

m1:=HuffNode[j].weight; x1:=j;

end

else if (HuffNode[j].weight<m2) and (HuffNode[j].parent=-1) then

begin m2:=HuffNode[j].weight; x2:=j; end;

{将找出的两棵子树合并为一棵子树}

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;

end;

end;