霍夫曼 Huffman 编码简单了解

霍夫曼 Huffman 编码简单了解霍夫曼编码(也叫哈夫曼编码)即时码:必须是唯一可译码,对一组即时码来说,其中的任意一个码字都只能与一种信号存在对应关系,而且任意一个码字都不能是其他码字的前缀。即时码的产生常采用树形结构:是用上边的即时码,假设收到这样一组信号:100101001则可以唯一解析出以下4个码字:100

大家好,欢迎来到IT知识分享网。

霍夫曼编码(也叫哈夫曼编码)

即时码:必须是唯一可译码,对一组即时码来说,其中的任意一个码字都只能与一种信号存在对应关系,而且任意一个码字都不能是其他码字的前缀。

即时码的产生常采用树形结构:

霍夫曼 Huffman 编码简单了解

是用上边的即时码,

假设收到这样一组信号:100101001

则可以唯一解析出以下 4 个码字:

1 001 01 001

编码过程

  1. 设有一个图像序列,含有 8 个灰度级,$x1, x2, x3,,, x8$,概率分别为:
p1 p2 p3 p4 p5 p6 p7 p8
0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04
  1. 选取最小两个概率进行合并,形成一个新的概率集合,重新进行排序。重复此步骤直到最终只剩两个概率为止,得到霍夫曼树

霍夫曼 Huffman 编码简单了解

  1. 根据霍夫曼树分配码字,得到霍夫曼编码

霍夫曼 Huffman 编码简单了解

概率越大,码长越短;概率越小,码长越短

计算平均码长:每一个霍夫曼码长与它的概率乘积之和

霍夫曼 Huffman 编码简单了解

这里的平均码长为 2.61,小于自然码长为 3(表示 8 个数至少需要 3 位),说明进行了压缩

计算熵、编码效率

计算绝对冗余、相对冗余

总结

霍夫曼编码是无失真编码中效率较高的一种编码方法。

在分配码字过程中,随机赋 “0” 和 “1” 的不同,结果会使码字不同(不唯一),而码字长和平均码字长不会改变,他也是唯一可解码的。

但其缺点是信源缩减过程复杂,运算量大。

解决办法:(适应性 Huffman 编码 ⭐⭐)https://blog.csdn.net/qq_28829853/article/details/104111533

  1. 使用多叉树压缩编码长度,提高码元携带的信息
  2. 使用更少的字符来构建编码表,调高字符的频次
  3. 减少文件头部携带的信息,提高编码率

对于 1.

改进后的霍夫曼编码,不再是二进制的。它可以是多进制,例如26进制。操作方法:
把符号按出现概率排序,合并概率最小的 26 项,为新的节点。然后重复这一过程,剩下的步骤与经典霍夫曼编码相同。
应用:把汉语单字读音的416音按26进制进行霍夫曼编码,结果,像de,shi,yu这些概率高的读音分配了较短的编码;dia,den这些不常用的读音分配较长的编码。26进制对应键盘的26键,这样就诞生了一种新的输入法
原文链接:https://blog.csdn.net/proorck2019/article/details/109445764

参考:

  • 西安电子科技大学《现代图像分析 图像压缩便编码》https://haokan.baidu.com/v?pd=wisenatural&vid=16617709331236028375

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/27778.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信