设有以下指令及其概率，设计其huffman编码是。

来源：蜘蛛抓取(WebSpider) 时间：2019-10-11 07:14 标签： huffman编码是

拍照搜题秒出答案，一键查看所有搜题记录

拍照搜题秒出答案，一键查看所有搜题记录

拍照搜题秒出答案，一键查看所有搜题记录

拍照搜题秒出答案，一键查看所有搜题记录

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

VIP专享文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP專享文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

我要回帖

更多关于 huffman编码是 的文章

 

随机推荐