霍夫曼编码简介

1霍夫曼编码简介

21.1前言1.2霍夫曼编码1.3有效的译码器1.4不等代价的编码法1.5错误更正能力1.7作业1.2.1静态式

1.3.1省空间式1.2.2动态式

1.3.2省时间式31.2霍夫曼编码

1.2.1静态式

图1.1先编S7和S8图1.2合并图1.1和S6图1.3合并S5和S4给定一符号集为，对应的频率为

4图1.4最终的霍夫曼树

符号码s100s210s3011s4111s5110s60101s701000s801001图1.5建成的码表

霍夫曼编码的确反应了常出现的符号所编成的码之长度较短，而不常出现的符号所编成的码之长度较长。

51.2.2动态式

给一符号集且其出现的对应频率集为，最佳的霍夫曼树需满足为最小，这里表示的高度。

将霍夫曼树上的节点从下层到上层和从左到右依序描扫，可得递增数列，且满足下式(1.1)图1.6

二种可能的霍夫曼树

(a)(b)6假设。若读入符号，则会变为4，由图1.7可知和的父亲节点之频率变为6，序列

就不具递增性了。

图1.7加入符号

(a)第一次调动

(b)第二次调动

图1.8经二次调动后的霍夫曼树

先将x4的子树和最右边编号且频率为5的子树对调得到图1.8(a)，接着将x8的子树和x9的子树对调而得到图1.8(b)。在图1.8(b)上加入一个s2，并不会破坏霍夫曼编码的最佳性。

7假设m为尚未出现过的字母个数；令，且k为其在未出现过字母中的顺位，则当时，可用个位元的来表示该字母，否则，用e个位元的来表示该字母。

动态式霍夫码的实作令字母集={A,B,C,D,…,Z,!,;}，一开始。假设待编码的讯息为CCHUNG。读入C

由，且因C为第个字母，并满足，所以将C编码成5(=4+1)位元的，即00010。读入C用位元‘1’编C即可。图1.9处理完符号C后的霍夫曼树(a)起始霍夫曼树(b)处理完符号C后图1.10处理完CC后的霍夫曼树8图1.12处理完CCHU后的霍夫曼树

图1.13处理完CCHUN后的霍夫曼树

读入H

，且H为第个字母，又满足，再加上霍夫曼树的0，所以H可编码为000111。读入U

，且U为第个字母，又，所以将U编码成4位元的，加上霍夫曼树的00，得U的码为

001010。

读入N

N可编成000101101

。

图1.11处理完CCH后的霍夫曼树91.3有效的译码器

1.3.1省空间式

图1.4最终的霍夫曼树

图1.14建构好的单边成长霍夫曼树令，，为单边成长霍夫曼树的之码。首先令且。根据式子，得到。

10代表第i层的外部节点数，，

内部节点数之序列为，储存符号集的阵列可安排为A[0…7]

。

假设收方收到的位元字符串为‘010’读出位元‘0’，，所以需再读入一个符号。读了‘01’，由可知路径是停在第二层的内部节点。再读入第三个符号‘0’，因为，且由，所以可知已达某一树叶了，译码出符号。定理1.1给一讯息且，在单边成长霍夫曼树上，解码工作可于的时间内完成。

符号码s111s210s3011s4010s5001s60001s700001s800000图1.15新建的码表111.3.2省时间式图1.4最终的霍夫曼树

在图1.4中，从树根所在的第零层到第二层形成了一个完全子树。利用广先搜寻方法，碰到外部节点时，就将对应的符号存入阵列；若碰到内部节点时，就存入的值，代表该内部节点左侧且同层的内部节点数，而代表该内部节点右侧的节点数。图1.4可表示成下列的矩阵型式：

假设收方收到的位元字符串为0101

首先读出二个位元01，接着读出。第三个读入的位元为0，所以推进三格，而得到。读入的第四个位元为1，所以阵列的指标往前推进五格，而得到。12给一以‘1’结尾的码，如果目前的刀子切在第j层且满足

，这里n可想成最终的码数。令C代表Tj中的一个码之平均位元数1.4不等代价的编码法以1结尾的霍夫曼编码

图1.16和

令t为一颗树，如图1.16所示。我们在树根处切一刀，如图中横线所示。则和，这里0代表切线(含)上的黑色叶子数为0，而1代表切线下的黑色叶子数为1。(1.2)可想成在第j层以下的未建立码的深度暂时以j代替。符号D代表深度；符号li代表黑色叶节点；Pi代表黑色叶节点li的机率。13建立以‘1’结尾的码，相当于最终所建立的树必需满足为最小。

假设目前的，令，则扩展到下一层，可表示为图1.18

的所有扩展可能(a)(b)(c)(d)14(e)图1.18的所有扩展可能由扩展到时，若属于的情形，则；若属于的扩展情形，则。

列出动态规划中的递回式起始时，令，对而言，我们有对而言，我们有指的是切线以下所有黑色节点的频率和。已知m介于0到n，而q介于0到2b。又已知b介于1到之间。分析后可得到共有组配对，因为每一个配对需的时间来决定最佳花费。故可推得，总共需的时间以完成‘1’为结尾的建码工作。

15不等代价编码法之应用

A˙－N－˙B－˙˙˙O－－－C－˙－˙P˙－－˙D－˙˙Q－－˙－E˙R˙－˙F˙˙－˙S˙˙˙G－－˙T－H˙˙˙˙U˙˙－I˙˙V˙˙˙－J˙－－－W˙－－K－˙－X－˙˙－L˙－˙˙Y－˙－－M－－Z－－˙˙图1.19摩斯码

假设长音的‘答’需要二单位的花费，而短音的‘嘀’需一个单位。那么LUCK总共需花费。在摩斯码中，句点‘˙’的音唸成‘嘀’，而较长的线‘－’唸成长音的‘答’。例如，‘嘀答嘀嘀嘀嘀答答嘀答嘀答嘀答’代表LUCK。假设存1需花费C单位，而存0需花费1单位，利用本节所叙的动态规划方法，这种不等代价的霍夫曼码之建置，可于的时间内完成。

161.5错误更正能力定义1.1矛盾配对码(AmbiguousCode-pair)：二个奇数等长度对称式霍夫曼码之间，只有中间位置的位元不同，则该二个码称为矛盾配对码。例如，(0010100,0011100)为矛盾配对码。

假设一种对称码，其各个码的长度为L位元，则共有个不同的对称码。考虑一个完全二分树T上的长度L之对称码个数，已选定从第一层到第i层为SRVLCs的目标码后，，可被定义如下

(1)，当。例如(2)，当且最右边位元为对称(3)，当为其它状况17令m(L)代表T在第L层中合法的对称码数，则(1.3)上式中代表在第i层已选定的对称码个数，而代表在第i层被选的对称码其最右边位元为对称之码数，这里。令长度为i的霍夫曼码之个数为n(i)。SRVLC的建构如下所示：步骤1：令。步骤2：若，则不变动，因为在第i层仍有多的可用对称码。否则的话，在这一层只有个SRVLC码被建立，不足的个留到下一阶段来建立，因而有步骤3：重覆步骤2直到每一个原始的霍夫曼码都找到一对应的

SRVLC。从步骤2中，可知，当时，共有种选择以建构SRVLCs。18式(1.4)中的p(L)代表在L层中的矛盾配对数。前面所叙的步骤2可修正如下：计算。若则不变；否则不足的留给下一层来建立，使得和。在个候选码中选取个对称码出来时，是依后置对称串(S