自适应Ｈｕｆｆｍａｎ压缩码的生成

　　摘要:随着现代社会信息量的增加,对数据进行压缩越来越有它的必要性。其中，Huffman编码作为一种高效的数据编码方法在文本、图象、音频等压缩有着广泛的应用。本文中，笔者根据Huffman编码的原理，实现对文本进行压缩与解压的功能。 
　　关键词：Huffman编码；数据压缩；解压；文本；自适应编码 
　　 
　　Huffman编码压缩是一种无损压缩技术。利用Huffman编码原理进行压缩的主要问题包括压缩的算法设计及程序实现、解压算法及程序实现。 
　　 
　　一、 Huffman编码介绍 
　　 
　　Huffman于1952年提出一种编码的方法，它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。 
　　 
　　二、自适应Huffman编码原理 
　　 
　　基于静态Huffman编码算法对输入的符号流进行编码，必须进行两次扫描，第一次扫描统计字符出现的概率，并创建Huffman树；第二次扫描是按照Huffman树的字符进行编码。并且在存储和传输Huffman编码时，必须先存储和传送Huffman树。这些问题使的静态Huffman编码在实际应用用的的较少。为了解决静态Huffman编码的缺点，产生了自适应Huffman编码，它只需要对输入的符号流进行一次扫描即可。它不仅涉及到编码树的构造过程，还与编码和解码有关。 
　　自适应Huffman编码过程 
　　初始化Huffman树 
　　对每个输入符号 
　　{对符号编码； 
　　更新Huffman树； 
　　} 
　　初始化Huffman树时，由于对字符流进行一次扫描，因此，不能预先知道各字符的概率，为了对所以字符一致对待，在这里使用符号为NYT，权值为0作为初始的Huffman树。NYT不同于任何一个将要传送的符号，在这里作为一个逸出码。NYT有两种作用：一是在编码时，当有一个还没在编码树出现的字符需要编码时，系统就输出NYT编码，然后跟着字符的原始表达；在解码时，当解码器读出NYT时，就知道下面的内容暂不是Huffman编码，而是一个从没在编码数据流出现的原始字符；二是作为新字符的插入点，在需要插入一个新字符时，总是构造一个新子树，子树包括NYT符号和新符号两个叶结点，然后将旧的NYT结点用新子树代替，并使原NYT和新符号结点的权值赋一。对符号编码与静态的一样。在每次编码完成之后，需要试图对包含的结点进行权值加一操作，为此在这里需要介绍两个概念：结点编号和所属块。结点编号是一个全局唯一的的值，不同的结点有不同的结点编号，它具有如下特性： 
　　(一) 权值越大的结点，结点编号越大。 
　　(二) 父结点的编号总是大于子结点的编号。 
　　以上两点称为兄弟属性，在每次调整结点权值时，都需要调整结点的编号，以避免兄弟属性破坏。在本课程设计中用数组来表示结点编号，根结点在数组的最大位置。所属块指权值相同的一组结点。在对每个结点进行权值加一时，首先检查该结点是否是所在块的最大结点，如果不是，将该结点与所在块的最大结点交换位置，在对该结点的权值加一，这样保证了结点的兄弟属性，由于结点的权值发生变化，必须递归对结点的夫结点执行加一操作。 
　　 
　　三、自适应Huffman压缩编码算法 
　　 
　　（一）判断字符在文本中是否出现 
　　由于自适应Huffman编码只对字符流扫描一次，因此，就需要判断该字符在前面的字符流是否出现过。 
　　（二）判断该字符是否是所属块的最大结点 
　　为了保证其兄弟属性不破坏，在进行加一操作时，必须判断该结点是否是所属快的最大结点，不是就必须交换当前结点与最大结点。 

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说计算机自适应Ｈｕｆｆｍａｎ压缩码的生成在线全文阅读。