自适应霍夫曼编码PPT演示课件

,论文题目,基于C语言的自适应Huffman编码算法分析及实现研究,主讲人：吴进强、杨村明,指导老师：周霆,组员：李洋、赵爱清、雷占勃、杨帆、刘骏、刘宝妹、叶楠,1,摘要,通过C语言程序，动态统计信源符号率，逐步构造Huffman编码树，实现了自适应Huffman编码，解决了静态编码树不能根据信源符号的局部变化做出相应变化的主要问题。结果表明，自适应Huffman编码算法压缩率很大，能进一步提高数据传输的效率。关键词:Huffman编码;自适应;无损压缩,2,引言Huffman编码概述静态Huffman编码树的构造原理自适应Huffman的编码原理过程自适应Huffman压缩编码的C语言实现及程序结果总结参考文献,目录,3,引言,随着信息技术的快速发展，日常需要处理或者传输的数据越来越多，由于数字化的多媒体信息尤其是数字音频、视频信号的数据量特别庞大，大数据量的信息会给存储器的存储容量、通讯干线信道的带宽以及计算机的处理速度增加极大的压力。如何采用有效的数据压缩技术来节省空间和网络传送时间已越来越引起人们的重视。,4,Huffman编码概述,Huffman算法是一种用于数据压缩的算法，它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。该编码的核心部分为Huffman编码树，一棵满二叉树。所有可能的输入符（通常对应为字节）在Huffman编码树上对应为一个叶节点，叶节点的位置就是该符号的Huffman编码。,5,具体来说，一个符号对应的Huffman编码就是从根节点开始，沿左子节点0或右子节点1前进，一直找到该符号叶节点为止的路径对应的二进制编码。在Huffman编码树的基础上，该算法的编码部分输入一系列的符号，根据Huffman树对符号进行翻译，以符号在Huffman树上的位置作为编码结果。解码部分反之，根据输入的Huffman编码，通过查询Huffman树翻译回原始符号。现在使用中的霍夫曼编码大致分为两种：静态霍夫曼编码和自适应霍夫曼编码。,6,静态Huffman编码树的构造原理,Huffman编码树是按照信源符号权重值大小将信源符号进行排序，取出权重值最小的两个信源符号作为叶节点组成一棵子树，子树的权重值为两个叶节点即权重值最小的两个信源符号权重值之和;然后将新产生的子树放回原来的集合，仍然按照信源符号权重值的大小将信源符号进行排序。重复以上方法，直至信源符号集合中只剩下一个符号。,7,以abcddbb作为待编码的原始信源数据串符号为例。首先，统计出a、b、c、d四个符号在原始数据串中的权重，结果如表1所示,8,按照前面提到的构造方法，可获得基于表1权重统计的静态Huffman编码树，如图1所示。,9,从Huffman编码树的根结点出发，经过右子树、左子树、左子树三步，到达包含字符a的叶结点，获得a字符的二进制编码:100。下一个字符b，从根节点出发向左子树前进一步，达到b的叶节点，二进制编码为0。类似，将所有的信源数据经编码后，得到编码结果为:1000101111100。,10,静态Huffman编码的缺点,在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中的符号出现概率，因此必须对输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。,11,其次，在存储和传送霍夫曼编码时，必须先存储和传送霍夫曼编码树。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。,12,自适应霍夫曼编码提出的意义,为了解决静态Huffman编码的缺点，人们提出了自适应Huffman编码，这种方案不需要事先扫描输入符号流，而是随着编码的进行同时构造Huffman树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量的图像和视频流传输中获得了广泛的应用。,13,这种方案在不需要事先构造Huffman树，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。,14,自适应霍夫曼编码的原理过程,在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则：（1）权重值大的节点，节点编号也较大。（2）父节点的节点编号总是大于子节点的节点编号。以上两点称为兄弟属性（siblingproperty）。,15,仍以abcddbb作为待编码的原始信源数据串为例，自适应Huffman编码过程如图所示。,16,17,18,19,20,21,22,23,24,25,26,27,28,通过观察以上步骤，容易发现自适应Huffman编码的几个特征:步骤13的编码树与静态Huffman编码树基本相同，除NYT节点和符号a节点组成的子树替代静态Huffman编码树中的符号a的叶节点之外;每一次输入新的符号之前，Huffman编码树都处于完整可用的正常状态;同一个输入符号，可能产生多种不同的输出;同样输出结果，可能由不同的输入产生。,29,这些特征首先说明了自适应Huffman编码树与静态Huffman编码树等同，完全符合树的定义。同时，由于每一个输入符号都对编码树产生了影响，因此解码过程无法从Huffman编码数据流的某一个中间位置开始进行，而必须从头至尾逐bit处理。,30,由于自适应Huffman编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的NYT节点的编码树作为初始状态，然后根据Huffman编码数据流，对符号进行还原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号之前，Huffman树都处于与进行编码时使用的Huffman树完全相同的状态，保证了解码的正确性。,31,自适应Huffman压缩编码的实现,自适应Huffman编码算法程序如下所示。初始化Huffman树:对每一个输入符号对符号编码;更新Huffman树;对一个输入符号进行Huffman编码并更新编码树的流程图如图所示,32,33,自适应Huffman编码算法的程序结果,34,总结,由此可见，自适应Huffman压缩编码算法在压缩比上尽管不能和有损压缩相比，但它改进了静态Huffman编码算法，更大程度上压缩了图像网络传输冗余信息而减小了网络传输的信息量，从而能进一步提高通信质量和网络传输数据的效率。,35,参考文献,1陈衍仪图像压缩的分形理论和方法M北京:国防工业出