动态Huffman编码

哈尔滨工业大学（威海）12020/2/2动态Huffman编码1：Huffman编码2：Huffman编码存在的问题3：动态Huffman编码4：实例分析哈尔滨工业大学（威海）22020/2/2Huffman编码Huffman于1952年提出一种编码的方法，它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。哈尔滨工业大学（威海）32020/2/2基本思想首先，按照权重值的大小将符号集合排序。接着，取出权重值最小的两个集合元素作为叶节点组成一棵子树，子树的权重值为两个叶节点的权重值之和。然后将新产生的子树放回原来的集合，并保持集合有序。重复上述步骤，直至集合中只剩下一个元素，则Huffman编码树构造完成。哈尔滨工业大学（威海）42020/2/2实例：abcddbb最终结果：最终的编码结果：1000101111100哈尔滨工业大学（威海）52020/2/2存在的问题基于静态Huffman编码算法对输入的符号流进行编码，必须进行两次扫描，第一次扫描统计字符出现的概率，并创建Huffman树；第二次扫描是按照Huffman树的字符进行编码。并且在存储和传输Huffman编码时，必须先存储和传送Huffman树。这些问题使的静态Huffman编码在实际应用用的的较少。为了解决静态Huffman编码的缺点，产生了自适应Huffman编码，它只需要对输入的符号流进行一次扫描即可。哈尔滨工业大学（威海）62020/2/2动态Huffman编码AdaptiveHuffmancoding(alsocalledDynamicHuffmancoding)isanadaptivecodingtechniquebasedonHuffmancoding.这种方案在不需要事先构造Huffman树，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）哈尔滨工业大学（威海）72020/2/2伪代码初始化编码树；对每一个输入符号{对符号编码；更新编码树；}兄弟属性——(1)权重值较大的节点，节点编号也较大；(2)父节点的节点编号总是大于子节点的节点编号哈尔滨工业大学（威海）82020/2/2初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预先知道各种符号的出现频率。为了对所有符号一致对待，编码树的初始状态只包含一个叶节点，包含符号NYT（NotYetTransmitted，尚未传送），权重值为0.NYT是一个逸出码（escapecode），不同于任何一个将要传送的符号。当有一个尚未包含在编码树中的符号需要被编码时，系统就输出NYT编码，然后跟着符号的原始表达。当解码器解出一个NYT之后，它就知道下面的内容暂时不再是Huffman编码，而是一个从未在编码数据流中出现过的原始符号。哈尔滨工业大学（威海）92020/2/2开始哈尔滨工业大学（威海）102020/2/2哈尔滨工业大学（威海）112020/2/2哈尔滨工业大学（威海）122020/2/2实例：abcddbb哈尔滨工业大学（威海）132020/2/2实例：abcddbb哈尔滨工业大学（威海）142020/2/2实例：abcddbb哈尔滨工业大学（威海）152020/2/2实例：abcddbb哈尔滨工业大学（威海）162020/2/2实例：abcddbb哈尔滨工业大学（威海）172020/2/2abcddbb哈尔滨工业大学（威海）182020/2/2实例：abcddbb哈尔滨工业大学（威海）192020/2/2自适应Huffman编码的几个特征在步骤13得到的编码树与静态Huffman编码树基本相同，除了NYT节点和符号a节点组成的子树替代了静态Huffman编码树中的符号a的叶节点之外在每一次输入新的符号之前，Huffman树都处于完整可用的正常状态哈尔滨工业大学（威海）202020/2/2自适应Huffman编码的几个特征同一个输入符号，可能产生多种不同的输出。例如三次输入的符号b，产生的输出分别为0b、001和10同样的输出结果，可能由不同的输入产生。例如第二次输入的符号d与第二次输入的符号b，都产生了001作为输出结果