编码算法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。

② 语音编解码的723.1(双速率语音编码算法)

类型：Audio
制定衡埋者：ITU-T
所需频宽：5.3Kbps(22.9)
特性：能够对音乐和其他音频信号进行压缩和解压缩，但它对语音信号来说是最优的。G.723.1采用了执咐敏蚂行不连续传输的静音压缩，这就意味着在静音期间的比特流中加入了人为的噪声。除了预留带宽之外，这种技术使发信机的调制解调器保持连续工作，并且避免了载波信号的时通时断。
优点：避免了载波信号的时通时断。
缺点：语音质量一般
应用领域：voip
版税方式：Free
备注：G.723.1算法是 ITU-T建议的应用于低速率多媒体服务中语音或其它音频信号的压缩算法，其目标应用系统包括H.323、H.324等多媒体通信系统 。该算法已成为IP电话系统中的必选算法拿告之一。

③ 哈夫曼的编码

哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。） 而衫誉迹且哈夫曼编码是按照子树到父亲，而其读码则是完全相反的。 因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第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 ……
procere 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;

④ 哈夫曼编码

编码方案

． 编码和解码 数据压缩过程称为编码 即将文件中的每个字符均转换为一个惟一的二进制位串 数据解压过程称为解码 即将二进制位串转换为对应的字符

． 等长编码方案和变长编码方案 给定的字符集C 可能存在多种编码方案 （ ） 等长编码方案 等长编码方案将给定字符集C中每个字符的码长定为[lg|C|] |C|表示字符集的大小 【例】设待压缩的数据文件共有 个字符 这些字符均取自字符集C={a b c d e f} 等长编码需要三位二进制数字来表示六个字符 因此 整个文件的编码长度为 位

（ ）变长编码方案 变长编码方案将频度高的字符编码设置短 将频度低的字符编码设置较长 【例】设待压缩的数据文件共有 个字符 这些字符均取自字符集C={a b c d e f} 其中每个字符在文件中出现的次数(简称频度)见表 表 字符编码问题 字符 a b c d e f 频度（单位 千次） 定长编码 变长编码 根据计算公式 ( * + * + * + * + * + )* = 整个文件被编码为 位 比定长编码方式节约了约 ％的存储空间 注意 变长编码可能使解码产生二义性 产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同 【例】设E T W分别编码为 则解码时无法确定信息串 是ET还是W

． 前缀码方案 对字符集进行编码时 要求做举字符集中任一字符的编码都不是其它字符的编码的前缀 这种编码称为前缀(编)码 注意 等长编码是前缀码

．最优前缀码 平均码长或文件总长最小的前缀编码称为最优的前缀码 最优的前缀码对文件的压缩效果亦最佳

其中 pi为第i个字符得概率 li为码长【例】若将表 所示的文件作为统计的样本 则a至f六个字符的概率分别为 对变长编码求得的平均码长为 优于定长编码(平均码长为 )

根据最优二叉树构造哈夫曼编码

利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码 哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术 该技术一般可将数据文件压缩掉 ％至 ％ 其压缩效率取决于被压缩文件的特征

． 具体做法 （ ）用字符ci作为叶子 pi或fi做为叶子ci的权 构造一棵哈夫曼树 并将树中左分支和右分支分别标记为 和 （ ）将从根到叶子的路径上的标号依次相连 作为该叶子所表示字符的编码 该编码即为最优前缀码（也称哈夫曼编码）

． 哈夫曼编码为最优前缀码 由哈夫曼树求得编码为最优前缀码的原段胡肆因 ① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li 平均码长(或文件总长)又是二叉树的带权路径长度WPL 而哈夫曼树是WPL最小的二叉树 因此编码的平均码长(或文件总长)亦最小 ② 树中没有一片叶子是另一叶子的祖先 每片叶子对应的编码就不可能是其它叶子编码的前缀 即上述编码是二进制的前缀码

． 求哈夫曼编码的算法 （ ）思想方法 给定字符集的哈夫曼树生成后 求哈夫曼编码的具体实现过程是 依次以叶子T[i]( ≤i≤n )为出发点 向上回溯至根为止 上溯时走左分支则生成代码 走右分支则生成代码 注意握轿 ① 由于生成的编码与要求的编码反序 将生成的代码先从后往前依次存放在一个临时向量中 并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置） ② 当某字符编码完成时 从临时向量的start处将编码复制到该字符相应的位串bits中即可 ③ 因为字符集大小为n 故变长编码的长度不会超过n 加上一个结束符 bits的大小应为n+

（ ）字符集编码的存储结构及其算法描述 typedef struct { char ch //存储字符 char bits[n+ ] //存放编码位串 }CodeNode typedef CodeNode HuffmanCode[n] void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H) {//根据哈夫曼树T求哈夫曼编码表H int c p i;//c和p分别指示T中孩子和双亲的位置 char cd[n+ ] //临时存放编码 int start //指示编码在cd中的起始位置 cd[n]= //编码结束符 for(i= i<n i++){ //依次求叶子T[i]的编码 H[i] ch=getchar() //读入叶子T[i]对应的字符 start=n //编码起始位置的初值 c=i //从叶子T[i]开始上溯 while((p=T[c] parent)>= ){//直至上溯到T[c]是树根为止 //若T[c]是T[p]的左孩子 则生成代码 否则生成代码 cd[ start]=(T[p) child==C)? c=p //继续上溯 } strcpy(H[i] bits &cd[start]) //复制编码位串 }//endfor }//CharSetHuffmanEncoding文件的编码和解码有了字符集的哈夫曼编码表之后 对数据文件的编码过程是 依次读人文件中的字符c 在哈夫曼编码表H中找到此字符 若H[i] ch=c 则将字符c转换为H[i] bits中存放的编码串 对压缩后的数据文件进行解码则必须借助于哈夫曼树T 其过程是 依次读人文件的二进制码 从哈夫曼树的根结点(即T[m ])出发 若当前读人 则走向左孩子 否则走向右孩子 一旦到达某一叶子T[i]时便译出相应的字符H[i] ch 然后重新从根出发继续译码 直至文件结束 文件的编码和解码算法【参见练习】

lishixin/Article/program/sjjg/201311/22941

⑤ G.711编码原理

本文目的：
1、熟悉G711a/u两种格式的基本原理
2、熟悉两种压缩算法的友悔实现步骤及提供源码实现

G.711是国际电信联盟ITU-T定制出来的一套语音压缩标准，它代表了对数PCM（logarithmic pulse-code molation）抽样标准，是主流的波形声音编解码标准，主要用于电话。

G.711 标准下主要有两种压缩算法。

G.711将14bit(uLaw)或者13bit(aLaw)采样的PCM数据编码成8bit的数据流，播放的时候在将此8bit的数据还原成14bit或者13bit进行播放，不同于MPEG这种对于整体或者一段数据进行考虑再进行编解码的做法，G711是波形编解码算法，就是一个sample对应一个编码，所以压缩比固定为：

G.711是将语音模拟信号进行一种非线性量化， 详细的资料可以在ITU 上下到相关的spec 。下面主要列出一些性能参数：
G.711（PCM方式）

算法原理：
A-law的公式如下，一般采用A=87.6

画出图来则是如下图，用x表示输入的采样值，F(x)表示通过A-law变换后的采样值，y是对F(x)进行量化后的采样值。

由此可见

对应反量化公式(即上面函数的反函数)：

G.711A输入的是13位（S16的高13位），这种格式是经过特别设计昌拍的，便于数字设备进行快速运算。

A-law如下表计算。

示例：

输入pcm数据为1234，二进制对应为（0000 0100 1101 0010）
二进制变换下排列组合方式（0 00001 0011 010010）
1、获取符号位最高位为0，取反，s=1
2、获取强度位00001，查表，编码制应该是eee=011
3、获取高位样本wxyz=0011
4、组合为10110011，逢偶数为取反为11100110，得到E6

使用在北美和日本，输入的是14位，编码算法就是查表，计算出：基础值+平均偏移值

μ-law的公式如下，μ取值一般为255

相应的μ-law的计算方法如下表

示例：
输入pcm数据为1234
1、取得范围值，查表得 +2014 to +991 in 16 intervals of 64
2、得到基础值为0xA0
3、得到间隔数为64
4、得到区间基本值2014
5、当前值1234和区间基本值差异2014-1234=780
6、偏移值=780/间隔数=780/64，取整得到12
7、输出为0xA0+12=0xAC

A-law和u-law画在同一个坐标轴中就能发现A-law在低强度信号下，精度要稍微高一些。

实际应用中，我们确实可以用浮点数计算的方式把F(x)结果计算出来，然后进行量化，但是这样一来计算量会比较大耐告羡，实际上对于A-law（A=87.6时），是采用13折线近似的方式来计算的，而μ-law（μ=255时）则是15段折线近似的方式。

G711尽管是一种非常古老的话音编码算法，原理和计算也比较简单，但是其中用到的一些基本原理同样在其他编码算法中得到了应用，对其进行深入的了解有助于更好的理解其他的算法。

⑥ 遗传算法的编码方法有几种

常用的编码介绍
1、二进制编码：
（1）定义：二进制编码方法是使用二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
（2）举例：0≤x≤1023,精度为1,m表示二进制编码的长度。则有建议性说法：使 2m-1≤1000（跟精度有关）≤2m-1。取m=10
则X:0010101111就可以表示一个个体，它所对应的问题空间的值是x=175。
（3）优缺点
优点：符合最小字符集原则，便于用模式定理分析；
缺点：连续函数离散化时的映射误差。
2、格雷码编码
（1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种变形。
十进制数0—15之间的二进制码和相应的格雷码分别编码如下。
二进制编码为：0000，0001，0010，001 1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷码编码为：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）举例：对于区间[0。1023]中两个邻近的整数X1=175和X2=176，若用长度为10位的二进制编码，可表示为X11：0010101111和X12 0010110000，而使用同样长度的格雷码，它们可分别表示为X21：0010101111和X22：0010101000。
（3）优点：增强了遗传算法的局部搜索能力，便于连续函数的局部控件搜索。
3、浮点数(实数)编码
（1）定义：浮点数编码是指个体的每个基因值用某一范围内的一个浮点数来表示，而个体的编码长度等于其决策变量的个数。因为这种编码方法使用的决策变量的真实值，也称之为真值编码方法。
（2）举例：
（3）优点：实数编码是遗传算法中在解决连续参数优化问题时普遍使用的一种编码方式，具有较高的精度，在表示连续渐变问题方面具有优势。
4、排列编码
排列编码也叫序列编码，是针对一些特殊问题的特定编码方式。排序编码使问题简洁，易于理解。该编码方式将有限集合内的元素进行排列。若集合内包含m个元素，则存在m!种排列方法，当m不大时，m!也不会太大，穷举法就可以解决问题。当m比较大时，m!就会变得非常大，穷举法失效，遗传算法在解决这类问题上具有优势。如解决TSP问题时，用排列编码自然、合理。
5、其它编码方式
多参数级联编码等

⑦ IP视频通信中视频压缩编码方法介绍【详解】

和一般的业务不同，视频是流特性业务，数据量很大。例如，数字电视图像中的SIF格式、NTSC制式、彩色、4∶4∶4采样，每帧的数据量为2028Kb，每秒的数据流量可达60.8Mb;CCIR格式、PAL制式、4∶4∶4采样的彩色视频的数据流量可达148.8Mbps。实验表明，176& TI mes;144的YUV原始视频在10Mbps的LAN上传送速率是3帧/秒左右。可见，未压缩的视频在Internet上传输的效果是无法容忍的，而且会很容易地将Internet资源吞没，造成网络拥塞甚至崩溃。因此，IP视频通信的第一步就是视频压缩。

视频压缩编码的理论基础是信息论。压缩就是从时域、空域两方面去除冗余信息，即将可推知的确定信息去掉。编码方法大致可分为三类：

1.考虑到图像信源的统计特性采用的预测编码方法、变换编码方法、液谨矢量量化编码方法、子带-小波编码方法及神经网络编码方法等;

2.考虑到视觉特性采用的基于方向滤波的图像编码方法、基于图像轮廓/纹理的编码方法;

3.考虑到图像传递的景物特征，采用的分形编码、基于模块的编码方法。

在IP视频通信应用中，编码方法的选择不但要考虑到压缩比、信噪比，还要考虑到算法的复杂性。太复杂的编码算法可能会产生较高的压缩比，但也会带来较大的计算开销，软件实现时会影响通信的实时性。目前，在众多视频编码算法中，影响最大并被广泛应用的算法是MPEG和H.26x。

MPEG编码

MPEG是国际标准化组织ISO/IEC下的一个制定动态 视频压缩 编码标准的组织，它为视频压缩编码技术的标准化、实用化做出了巨大贡献。如针对CD-ROM的1.5Mbps传输率的MPEG-1、针对HDTV的6Mbps以上传输速率的MPEG-2都已成功地得到应州橘用，并创造了巨大的商业价值。MPEG-4是针对视频会议、可视电话的甚低速率编码标准，它闹迹基融入了基于内容的检索与编码，可对压缩数据内容直接访问;即将于2001年制定完毕的MPEG-7标准被称为"多媒体内容描述接口"，这种标准化的描述可以加到任何类型的媒体信息上。不管视频信息的表达形式或压缩形式如何，具有这种标准化描述的多媒体数据均可被检索。因此，MPEG-7的应用领域主要是数字化图书馆和广播式媒体。

H.263编码

H.261编码是一种帧间预测减少时域冗余、变换编码减少空域冗余的混合编码方法，具有压缩比高、算法复杂度低等优点，得到较为广泛的应用。Mbone的重要应用工具之一IVS的视频编码采用的就是H.261编码算法。在H.261的基础上，1996年ITU-T推出了H.263编码标准。H.263在许多方面对H.261进行了改进和扩充，如在编码算法复杂度增加很少的基础上，H.263能提供更好的图像质量、更低的速率，十分适合于IP视频会议、可视电话应用。目前，H.263编码是IP视频通信采用最多的一种编码方法，并已被许多多媒体通信终端标准所吸收, 如：ITU-TH.310(B-ISDN)、H.320(ISDN)、H.324(PSTN)、H.323(LAN、 WAN、Internet)。

随着计算机性能的快速提高，对于可视电话和视频会议等应用(一般使用QCIF图像)，纯软件编码器(codec)即可以满足应用要求。我们实现的H.263纯软件编码器在主频为166MHz的主机上编码帧率可达60帧/秒以上，平均图像质量(用信噪比表示)大于38dB。

1998年ITU-T推出的H.263+是H.263建议的第二版，它提供了12个新的可协商模式和其他特征，进一步提高了压缩编码性能。如H.263只有5种视频源格式，H.263+允许使用更多的源格式，图像形状和时钟频率也有多种选择，拓宽了应用范围;另一重要的改进是可扩展性，它允许多显示率、多速率及多分辨率，增强了视频信息在易误码、易丢包异构网络环境下的传输。另外，H.263+的图像分段依赖性也可以是受限的，以减少差错传播。H.263+对H.263中的不受限运动矢量模式进行了改进，加上12个新增的可选模式，不仅提高了编码性能，而且增强了应用的灵活性。

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

参考： 哈夫曼编码

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

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

⑨ 哈夫曼编码码长怎么算

假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。

哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000

用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。

因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，

就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。

(9)编码算法T扩展阅读：

实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，

例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），

这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。

⑩ 哈夫曼编码原理

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

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

(10)编码算法T扩展阅读

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