《Huffman霍夫曼编码》由会员分享，可在线阅读，更多相关《Huffman霍夫曼编码（24页珍藏版）》请在金锄头文库上搜索。
1、4.2霍夫曼编码霍夫曼编码(Huffman Coding)是一种编码方法， 霍夫曼编码是可变字长编 码(VLC)的一种。 1952年 ，David A. Huffman在麻 省理工攻读博士时所提出 一种编码方法，并发表于 一种构建极小多余编码 的方法（A Method for the Construction of Minimum-Redundancy Codes）一文。霍夫曼编码介绍David A. Huffman该方法完全依据字符出现概率来构造异字头的 均长度最短的码字，有时称之为最佳编码， 一般就叫作Huffman编码。在计算机数据处理中，霍夫曼编码使用变长 编码表对源符号（如文件中的一
2、个字母）进行 编码，其中变长编码表是通过一种评估来源符 号出现机率的方法得到的，出现机率高的字母 使用较短的编码，反之出现机率低的则使用较 长的编码，这便使编码之后的字符串的均长 度、期望值降低，从而达到无损压缩数据的目 的。1951年，霍夫曼和他在MIT信息论的同学 需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目 是，查找最有效的二进制编码。由于无法证明 哪个已有编码是最有效的，霍夫曼放弃对已有 编码的研究，转向新的探索，最终发现了基于 有序频率二叉树编码的想法，并很快证明了这 个方法是最有效的。由于这个算法，学生终于 青出于蓝，超过了他那曾经和
3、信息论创立者克 劳德香农共同研究过类似编码的导师。霍夫曼 使用自底向上的方法构建二叉树，避免了次优 算法Shannon-Fano编码的最大弊端自顶 向下构建树。霍夫曼（Huffman）编码是一种统计编码。 属于无损（lossless）压缩编码。 以霍夫曼树即最优二叉树，带权路径长 度最小的二叉树，经常应用于数据压缩。根据给定数据集中各元素所出现的频率来 压缩数据的一种统计压缩编码方法。这些 元素(如字母)出现的次数越多，其编码的位 数就越少。广泛用在JPEG, MPEG, H.2X等各种信息编 码标准中。霍夫曼编码的步骤霍夫曼编码的具体步骤如下：）将信源符号的概率按减小的顺序排队。）把两个最小
4、的概率相加，并继续这一步骤 ，始终将较高的概率分支放在上部，直到最后 变成概率。3）将每对组合的上边一个指定为1，下边一个 指定为0（或相反）。）画出由概率处到每个信源符号的路径， 顺序记下沿路径的和，所得就是该符号的 霍夫曼码字。 信源熵的定义：概率空间中每个事件所含有的自信息量的数学期 望称信源熵或简称熵(entropy)，记为： 单位:以2为底的对数时是比特/符号(bit/symbol);以e为底的对数时是奈特/符号(nat/symbol);以10为底的对数时是哈特/符号( hart/symbol) 其中 表示某个事 件的信息量。I()=logp()均码长编码效率例：现有一个由5个不同符
5、号组成的30个符号的字 符串： BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的均码长H(S)=(8/30)log2(30/8) + (10/30)log2(30/10) +(3/30)log2(30/3) + (4/30)log2(30/4) +(5/30)log2(30/5)= ( 44.313624.5592)/ 9.0308 2.1874 (Sh)例 ：均码长： (28210333425)/302.233 位/符号类似书中例4-600001111霍夫曼编码的主要特点： 1.霍夫曼编码构造的码字不唯一
6、； 2.霍夫曼编码是变长编码，硬件实现比较困难 ； 3.采用霍夫曼编码，要传送编码表，占用传送 时间； 4.霍夫曼编码是变长编码，出错时难以识别； 霍夫曼编码方法不唯一，因为编码时的0和1是任 意给的，另外在两个符号有相同概率时的编码过 程不唯一，造成编码结果不同，但均码长相 同。其次对信源进行缩减时两个概率最小的符号 合并后的概率与其他信源符号的概率相同时，这 两者在缩减信源中进行概率排序，其位置放置次序 是可以任意的，故会得到不同的霍夫曼码此时将 影响码字的长度，一般将合并的概率放在上面， 这样可以获得较小的码方差。 霍夫曼树1、有关霍夫曼树的相关概念霍夫曼树：指所有叶子结点的二叉树中带
7、权路径长度最小的二叉树。节点的带权路径长度：从树的根节点到该 节点的路径长度与该节点权的乘积。树的带权路径长度：树中所有叶子结点的 带权路径长度之和。2、霍夫曼算法 （1）根据给定的n个权值w1,w2,.,wn构造n棵 二叉树的集合F=T1,T2,.,Tn，其中每棵二叉 树Ti中只有一个带权为wi的根结点，其左右子树 均空。 （2）在F中选取两棵根结点的权值最小的树作 为左右子树构造一棵新的二叉树，且置新的二 叉树的根结点的权值为其左、右子树上根结点 的权值之和。 （3）在F中删除这两棵树，同时将新得到的二 叉树加入F中。 （4）重复（2)和（3)，直到F中只含一棵树为 止。这棵树便是最优二叉
8、树。当信源符号的出现概率为2的整数次幂时霍夫曼编码的效率才能达到100%。当符号出现概率不是2的整数次幂时编码效率下降。香农第一定理：（又称为变长编码定理）设离散无记忆信源S包含r个符号，信源发出N重符号序列 ，则此信源可发 出 个不同的符号序列消息，其中第 j 个符号序列消息的出现概率为 ，其信源编码后所得的 信源编码基本定理二进制代码组长度为 ，代码组的均长度为它满足当 N 趋于无限大时， 和 H(S) 之间的关系为书中例4-8JEPEG采用将码字截断为“前缀码（SSSS）+ 尾码”的方法，对码表进行了简化：霍夫曼编码不仅适用于压缩文本文件，经过符 号合并后也可用于二进制文件。但在实用中，
9、 霍夫曼编码的输入符号数常受限于可实现的码 表大小。 截断霍夫曼编码尾码为DIFF的B位原码，若DIFF0反码，若DIFF0前缀码用来指明尾码的有效位数（设为B位） ，用标准的霍夫曼编码；尾码则直接采用B位自 然二进码（对于给定的前缀码它为定长码，高位 在前）。对于8位量化的图像，SSSS值的范围为 011，故其码表只有12项。根据DIFF的幅度范 围由表4.2查出前缀码字和尾码的位数后，则可按 以下规则直接写出尾码的码字,即在静态霍夫曼编码中，要构造编码树必须提前统计 被编码对象中的符号出现概率，因此必须对输入符 号流进行两遍扫描，第一遍统计符号出现概率并构 造编码树，第二遍进行编码，这在很
10、多实际应用的 场合中之不能接受的。其次，在存储和传送霍夫曼按此规则，当DIFF0时，尾码的最高位是“1” ；而当DIFF0时则为“0”。解码时则可借此来 判断DIFF的正负。书中例49 自适应霍夫曼编码提出的目的和意义：编码时，必须先存储和传送霍夫曼编码树。再次， 静态编码树构造方案不能对输入符号流的局部统计 规律变化做出反应。这些问题使得静态霍夫曼编码 在实际中并未得到广泛的应用。为了解决静态 Huffman编码的缺点，人们提出了自适应Huffman 编码这种方案不需要事先扫描输入符号流，而是随 着编码的进行同时构造Huffman树，因此，只需要 进行一次扫描即可。在接收端伴随着解码过程同时
11、 进行着编码树的构造。自适应霍夫曼编码解决了静 态编码树所面临的主要问题，因此在实际领域比如 在高质量的图像和视频流传输中中获得了广泛的应 用。自适应霍夫曼编码的原理：这种方案在不需要事先构Huffman 树，而是随 着编码的进行，逐步构造 Huffman 树。同时，这 种编码方案对符号的统计也动态进行，随着编码的 进行，同一个符号的编码可能发生改变（变得更长 或更短）。由于自适应 Huffman 编码算法采用 了先编码，后调整编码树的方案，相应的解码算 法比较简单。解码算法也使用仅有唯一的 NYT 节 点的编码树作为初始状态，然后根据Huffman编 码数据流，对符号进行还原。每次处理完一个
12、符 号，就使用这个符号调整编码树。这样，在每一 次输入新的符号之前，Huffman 树都处于与进行编码时使用的的 Huffman 树完全相同的状态，保证了解码的正确 性。自适应霍夫曼编码是一种扩展的熵编码方法，相 比于先前的静态霍夫曼编码，自适应霍夫曼编码 具有仅需单遍扫描、无需传送编码树、能够对输 入符号流的局部统计规律变化做出反应等一系列 优点，具有更高的压缩效率。这些优点使得它在 一些实时性、可靠性要求比较高的场合得到了广 泛的应用，被称为近代压缩算法的灵魂。 利用霍夫曼编码，每个符号的编码长度只能 为整数，所以如果源符号集的概率分布不是 2负n次方的形式，则无法达到熵极限。输入符号数受限于可实现的码表尺寸译码复杂需要实现知道输入符号集的概率分布没有错误保护功能霍夫曼编码的局限性THANKTHANKYOU!YOU!
