锐客网

  1. 首页 > 睿知 > >

哈夫曼编码 最优前缀码 算法分析

经验分享睿知

【哈夫曼编码 最优前缀码 算法分析】平均代码长度相当于二叉树的加权路径长度 。从这个意义上说，树生成的哈夫曼一定是最优 前缀 code，所以通常是不加区分，哈夫曼 编码，又称霍夫曼编码，是一个编码模式，哈夫曼 编码是一个可变词，等长编码Yes最优Before编码在(平均码长为2.24)的情况下，等长编码Before最优 。

1、请描述 哈夫曼 算法,并用图描述构造 哈夫曼树的过程 。这个挺清楚的 。首先介绍一下什么是哈夫曼 tree 。哈夫曼 tree又称最优二叉树，是一种加权路径长度最短的二叉树 。所谓树的加权路径长度，就是树中所有叶节点的权重乘以到根节点的路径长度(如果根节点有0层，那么从叶节点到根节点的路径长度就是叶节点的层数) 。树的加权路径长度被表示为wpl (w1 * L1 w2 * L2 w3 * L3 ... wn * ln)，以及n个权重Wi(i1，

...n).可以证明哈夫曼 tree的WPL最小 。哈夫曼这种编码在20世纪50年代初提出时 ， 平均长度最短的编码是根据字符出现的概率构造的 。是一种变长编码 。在编码中，如果每个码字的长度按照该码字对应的符号出现概率的逆序排列，则编码的平均长度最小 。(注:码字在符号后是哈夫曼 编码 ， 其长度因符号的概率不同而不同，所以哈夫曼编码是可变的 。

2、 哈夫曼 编码的原理是什么?假设某个信源产生五种符号u1、u2、u3、u4、u5，对应概率P10.4、P20.1、P3P40.2、P50.1，首先将符号按概率降序排列 ， 如图所示 。编码，从概率最小的两个符号开始，可以选择一个分支为0 ， 另一个分支为1 。这里，我们选择上分支为0，下分支为1 。然后合并已经编码的两条路的概率，重新排队 。重复上述方法多次，直到合并概率归一化 。

一般来说，如果将新合并的分支以等概率排列在最上面的分支，将有利于缩短码长的方差，编译后的码更接近等长码 。这里 ， 图(a)中的编码比(b)更好 。扩展数据发展史哈夫曼编码(霍夫曼编码)，又称霍夫曼编码 。1951年，哈夫曼和他麻省理工学院信息论的同学们必须选择是完成学期报告还是期末考试 。导师罗伯特给他们的学期报告的标题 。Fano就是找最有效的二进制编码 。

3、数据结构(14首先我们来看四个与树相关的概念:如上图所示，二叉树A中 ， 节点A到节点B的路径长度为3，树的路径长度为1 1 2 2 3 4 420，树的加权路径长度为5 * 1 15 * 2 40 * 3 30 * 。二叉树B中，节点A到节点B的路径长度为2，树的路径长度为1 2 2 3 1 2 216 ， 树的加权路径长度为5*3 15*3 40*2 30*2 10*2220 。

图中红色节点是原始节点，黑色节点是新生成的节点 。总结步骤如下:哈夫曼 Tree主要是为了解决当年远距离通信的数据传输问题最优而发明的 。比如要传输的电报是BADCADFEED，只用了六个字符，我们可以用对应的二进制数来表示:编码传输后是00100011 。

4、在什么情况下,等长 编码是 最优前的 编码在(平均码长为2.24)的情况下，等长编码Yes最优Previous编码 。常见等长编码 is 。所谓最优 前缀 code是指前缀编码called最优具有最小的平均代码长度或文件总长度 。改变编码的长度可能会使解码产生歧义，而前缀 code的出现很好地解决了这个问题 。平均代码长度相当于二叉树的加权路径长度 。从这个意义上说 ， 树生成的哈夫曼一定是最优 前缀 code，所以通常是不加区分 。

5、什么是 哈夫曼 编码?对比如下:1 。暗语不一样 。哈夫曼构造的码字不唯一 。对于同一个信息源，无论上述顺序如何，其平均码长都不会改变，所以其优点是编码效率唯一性 。二进制编码构造的码字是唯一的 。2.不等长哈夫曼 编码是基于字符出现概率的平均长度最短的码字，比较准确 。二进制编码是通过预定的方法将字符、数字或其他对象编码成二进制数，或将信息和数据转换成指定的二进制数 。

6、霍夫曼 编码器JPEG(联合摄影专家组)是由ISO和IEC两个组织组成的专家组 ， 负责制定静态数字图像数据压缩标准编码 。这个专家组开发的算法被称为JPEG 算法并成为国际标准 。JPEG是一种广泛适用的静止图像数据压缩标准，可用于灰度图像和彩色图像 。

7、求高手写个关于 哈夫曼 编码的 算法楼主走运了 ， 我这里有现成的C语言代码:#include#defineN7/*叶子数，需要的话可以更改这个值*/#defineM2*N1/*总节点数*/typedefstruct { charbits[N]；/* 编码 storage ， 位串*/int start；/* 编码位串中的位置*/} codetype；typedefstruct { floatweightintlchild，
父母；} hufmtreevoid Huffman(tree 1)hufmtreetree 1[]；{inti，p1 ， p2；floatsmall1，small2 ， f；hufmtree *树；treetree1for(i0； 。

    推荐阅读


    上一篇：青桔单车的内部资源分析

    下一篇：openresty 源码分析