哈夫曼编码的原理

霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[ ]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i]parent，如果i是myHuffmantree[i]parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了

哈夫曼编码规则：

哈夫曼编码是一种可变长度的编码方式，其特点是给予出现频率较高的字符更短的编码，以此达到压缩的目的。

拓展：

哈夫曼编码可以用于文件压缩，以有效减少文件大小。它也可以用来加速网络传输，以便更快地传输数据。此外，哈夫曼编码还可以用于错误检测和纠正，因为编码的模式可以帮助检测和纠正错误。

比较如下：

1、码字不同。

哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。

2、长度不同

哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。

3、稳定性不同

哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。

参考资料来源：百度百科-哈夫曼编码

参考资料来源：百度百科-二进制编码

假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{007,019,002,006,032,003,021,010}。

哈夫曼编码 根据上面可得编码表：  a:1001  b:01  c:10111  d:1010  e:11  f:10110  g:00  h:1000

用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4007+2019+5002+4006+2032+5003+2021+4010=261  261/3=087=87%其平均码长是等长码的87%，所以平均压缩率为13%。

因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，

就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。

扩展资料：

实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，

例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），

这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。

参考资料来源：百度百科-哈夫曼编码

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：02×2+019×2+018×3+017×3+015×3+01×4+001×4=272 bit

可以算出本例的信源熵为261bit，二者已经是很接近了。

哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。例如：用三位二进行数进行的等长编dao码平均长度为3，而根据哈夫曼树编码的平均码长为：

4007+2019+5002+4006+2032+5003+2021+4010=261 

261/3=087=87% 

其平均码长是等长码的87%，所以平均压缩率为13%。

扩展资料：

霍夫曼编码的基本方法先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。

赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。

参考资料来源：百度百科-哈夫曼编码

参考资料来源：百度百科-压缩率

编码方案

． 编码和解码 数据压缩过程称为编码 即将文件中的每个字符均转换为一个惟一的二进制位串 数据解压过程称为解码 即将二进制位串转换为对应的字符

． 等长编码方案和变长编码方案 给定的字符集C 可能存在多种编码方案 （ ） 等长编码方案 等长编码方案将给定字符集C中每个字符的码长定为[lg|C|] |C|表示字符集的大小例设待压缩的数据文件共有 个字符 这些字符均取自字符集C={a b c d e f} 等长编码需要三位二进制数字来表示六个字符 因此 整个文件的编码长度为 位

（ ）变长编码方案 变长编码方案将频度高的字符编码设置短 将频度低的字符编码设置较长例设待压缩的数据文件共有 个字符 这些字符均取自字符集C={a b c d e f} 其中每个字符在文件中出现的次数(简称频度)见表      表               字符编码问题          字符                      a     b     c     d      e      f     频度（单位 千次）                                    定长编码                                        变长编码                                            根据计算公式       ( + + + + + ) = 整个文件被编码为 位 比定长编码方式节约了约 ％的存储空间 注意 变长编码可能使解码产生二义性 产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同例设E T W分别编码为 则解码时无法确定信息串 是ET还是W

． 前缀码方案                                       对字符集进行编码时 要求字符集中任一字符的编码都不是其它字符的编码的前缀 这种编码称为前缀(编)码 注意 等长编码是前缀码

．最优前缀码 平均码长或文件总长最小的前缀编码称为最优的前缀码 最优的前缀码对文件的压缩效果亦最佳

  其中 pi为第i个字符得概率 li为码长　例若将表 所示的文件作为统计的样本 则a至f六个字符的概率分别为 对变长编码求得的平均码长为 优于定长编码(平均码长为 )

根据最优二叉树构造哈夫曼编码

利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码 哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术 该技术一般可将数据文件压缩掉 ％至 ％ 其压缩效率取决于被压缩文件的特征

． 具体做法（ ）用字符ci作为叶子 pi或fi做为叶子ci的权 构造一棵哈夫曼树 并将树中左分支和右分支分别标记为 和（ ）将从根到叶子的路径上的标号依次相连 作为该叶子所表示字符的编码 该编码即为最优前缀码（也称哈夫曼编码）

． 哈夫曼编码为最优前缀码 由哈夫曼树求得编码为最优前缀码的原因 ① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li 平均码长(或文件总长)又是二叉树的带权路径长度WPL 而哈夫曼树是WPL最小的二叉树 因此编码的平均码长(或文件总长)亦最小 ② 树中没有一片叶子是另一叶子的祖先 每片叶子对应的编码就不可能是其它叶子编码的前缀 即上述编码是二进制的前缀码

． 求哈夫曼编码的算法 （ ）思想方法 给定字符集的哈夫曼树生成后 求哈夫曼编码的具体实现过程是 依次以叶子T[i]( ≤i≤n )为出发点 向上回溯至根为止 上溯时走左分支则生成代码 走右分支则生成代码 注意 ① 由于生成的编码与要求的编码反序 将生成的代码先从后往前依次存放在一个临时向量中 并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置） ② 当某字符编码完成时 从临时向量的start处将编码复制到该字符相应的位串bits中即可 ③ 因为字符集大小为n 故变长编码的长度不会超过n 加上一个结束符 \ bits的大小应为n+

（ ）字符集编码的存储结构及其算法描述   typedef struct {      char ch //存储字符      char bits[n+ ] //存放编码位串    }CodeNode   typedef CodeNode HuffmanCode[n]   void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H)     {//根据哈夫曼树T求哈夫曼编码表H      int c p i;//c和p分别指示T中孩子和双亲的位置      char cd[n+ ] //临时存放编码      int start //指示编码在cd中的起始位置      cd[n]= \ //编码结束符      for(i= i<n i++){ //依次求叶子T[i]的编码         H[i] ch=getchar() //读入叶子T[i]对应的字符         start=n //编码起始位置的初值         c=i //从叶子T[i]开始上溯         while((p=T[c] parent)>= ){//直至上溯到T[c]是树根为止               //若T[c]是T[p]的左孩子 则生成代码 否则生成代码             cd[ start]=(T[p) child==C)             c=p //继续上溯           }         strcpy(H[i] bits &cd[start]) //复制编码位串       }//endfor      }//CharSetHuffmanEncoding文件的编码和解码有了字符集的哈夫曼编码表之后 对数据文件的编码过程是 依次读人文件中的字符c 在哈夫曼编码表H中找到此字符 若H[i] ch=c 则将字符c转换为H[i] bits中存放的编码串 对压缩后的数据文件进行解码则必须借助于哈夫曼树T 其过程是 依次读人文件的二进制码 从哈夫曼树的根结点(即T[m ])出发 若当前读人 则走向左孩子 否则走向右孩子 一旦到达某一叶子T[i]时便译出相应的字符H[i] ch 然后重新从根出发继续译码 直至文件结束 文件的编码和解码算法参见练习

lishixinzhi/Article/program/sjjg/201311/22941

哈夫曼编码是我在得到app中吴军老师的《信息论40讲》中了解到的，虽然是一个关于信息论的编码方法， 但是对于我们的生活和工作也是很有帮助的，所以记了下来。

关于哈夫曼编码，是从摩尔斯电码说起的，这种电码是用点（嘀）和长线（嗒）对英文的26个字母进行编码的，按照对信息度量的方法，如果对26个字母采用等长度析编码，比如进行进制编码就需要log26（这里的log函数是以2为底的），也就是约5比特信息，而采用摩尔斯电码的方法，平均只需要3比特，这样效率就高了很多，发报时间也节省了大约1/3左右。

在战争时期，能够节省发电报的时间对情报人员的安全是很重要的，因为谍战片里情报人员没法完电报就被别人闯进来带走的情形在现实中是真的很常见的，尤其是在二战时期欧洲的德占区。另外就算是除去战争的因素，能够节省1/3的发报成本也是一个很大的改进。

但是，如果按照哈夫曼编码的方法来看摩尔斯电码，就会发现虽然摩尔斯电码不自觉的采用了哈夫曼编码的方法，但还不是最简洁的编码方法，依然有改进的空间。

事实证明，越长出现的信息采用较短的编码，不常出现的信息采用较长的编码相比于所有信息都采用相同长度编码的方法更合算的。我们可以按照这样一个推倒步骤来看一下：

（对于我个人来讲，虽然数学学得不怎么样，但是这种推导过程我还是很喜欢的，因为通过自己动手来将一个结论推导出来时间很开心的事。)

哈夫曼编码从本质上讲就是讲最宝贵的资源（最短的编码）给出现概率最大的信息。而至于如何分配，其中的一个原则就是一条信息编码的长度和出现概率的对数成正比。 按我的理解就是出现的概率越大，投入的资源就越多。

那么哈夫曼编码的原则对于我们有什么用处呢？可以这样讲，只要是需要分配资源的工作，它都有指导意义。

课程中给我印象最深就是美国私立学校哈克学校的前校长尼科诺夫博士的一句话：在孩子小时候，要让他们尝试各种兴趣爱好，但是最终他们要在一个点上实现突破，就好比用圆规画圆，一方面有一个扎得很深的中心，另一方面有足够广的很浅的覆盖面。我觉得这是我能够听明白并且能够实践应用的最简单直接的方法。而且吴军老师就是用哈夫曼编码的方法来指导行动的，不排斥尝试新东西，但也对那些看样子不太能做成的事坚决停止投入，然后将更多的精力投入到成功率最高的事情上。

吴军老师有句话很好，“理论不在学得多，而在于学以致用”。而我们大多数人都是学得多，用得少，我也是一样。也许我可以从学着用哈夫曼编码开始，试着将学到的理论指导实践，踏踏实实的往前走。

以上就是关于哈夫曼编码的原理全部的内容，包括:哈夫曼编码的原理、哈夫曼编码规则、哈夫曼编码和二进制编码优缺点比较等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！