霍夫曼编码的解题步骤_什么是哈夫曼编码

2024年 9月 16日上午11:28 • 激活谷笔记

消除编码冗余的几种编码　　霍夫曼编码　　书接上回大颠牛：图像压缩基础

对概率进行排序,从上到下是从大到小

霍夫曼编码的分配过程　　对于这幅图,可以计算其信息熵为　　
$H=-(0.4\log_2(0.4)+0.3\log_2(0.3)+0.1\log_2(0.1)+0.1\log_2(0.1)+0.06\log_2(0.06)+0.04\log_2(0.04))=2.1435$ 　　但是平均比特数为　　
$L_{avg}=0.4\times1+0.3\times2+0.1\times3+0.1\times4+0.06\times5+0.04\times5=0.4+0.6+0.3+0.4+0.5=2.2$ 　　香农第一定理已经揭示了可以构造一个编码列逼近信息熵,但是没有给出逼近的方法. 　　霍夫曼编码没有达到最低的信息熵的原因是,本人认为,在于对于概率差不多的字符,使用了几乎相同长度的编码.不够”精确”. 　　发现规律,一般的,对于具有
个字符的系统,概率从大到小为
$p_1,\cdots,p_N$ ,对应的霍夫曼编码比特数为　　
$1,2,\cdots,N-1,N-1$ . 　　并且霍夫曼编码是变长编码. 　　Golomb编码,一种用起来比霍夫曼编码还简单的编码. 　　这种编码的核心思想是选取合适的被除数,用商和余数表示被编码的正整数. 　　unary code:正整数
的unary code是
个
后面紧跟着一个
. 　　对于正整数
,选取一个
其进行编码,编码记为
.

　　计算
:

　　Golomb-Rice编码(进阶的) 　　记号为
$G_{\exp}^k(n)$ ,计算方法如下

　　举例子计算
$G_{\exp}^0(8)$ :

　　一些Golomb编码的具体值:

　　算术编码　　算术编码的思想，同霍夫曼编码一样,也是对于高频字符进行短编码，但是它的实现方式，完全和霍夫曼编码不同,使用区间
$\left[0,1\right)$ . 　　编码　　对于这段字符AABABCABAB 　　算术编码会对 0 -1 进行区间划分。　　AABABCABAB 的第 1 个字符为：A，那么选中了 A 的区间 [0, 0.5) 作为新的目标区间。　　对新目标区间，再按照 ABC 的概率占比进行划分。　　AABABCABAB 的第 2 个字符仍然为：A，那么再选中了 A 的区间 [0, 0.25) 作为新的目标区间。　　对新目标区间，再按 ABC 的概率占比进行划分。　　AABABCABAB 的第 3 个字符为：B，那么这次选中了 B 的区间 [0.125, 0.225) 作为新的目标区间。　　对新目标区间，再按照 ABC 的概率占比进行划分。　　AABABCABAB 的第 4 个字符为：A，那么再选中 A 的区间 [0.125, 0.175) 作为新的目标区间。　　重复上面的操作,一直到最后一个字符. 　　总的来说过程如下:当前字符当前目标区间A[0, 0.5)A[0, 0.25)B[0.125, 0.225)A[0.125, 0.175)B[0.15, 0.17)C[0.168, 0.17)A[0.168, 0.169)B[0.1685, 0.1689)A[0.1685, 0.1687)B[0.1686, 0.16868) 　　完成上面的操作后，最终的目标区间为：
$\left[0.1686, 0.16868\right)$ ，我们在这个区间内，任意选一个小数，便可以作为最终的编码小数。但是计算机只能识别 0 和 1，所以需要再将小数转成二进制。　　我们的诉求是进行最短压缩，所以要从
$\left[0.1686, 0.16868\right)$ 选一个二进制表示最短的小数。这里选定 0.875，二进制为：0.001，去掉整数位 0 以及小数点后，最终的二进制编码为 001，bit 长度为 14 位，比哈夫曼编码要更短 1 位,这是因为它选用小数,比霍夫曼编码精确.

　　解码　　先从初始区间中定位第一个字符：　　0.875 位于 A 区间，所以第一个字符为 A。接着对 A:
$\left[0,0.5\right)$ 再进行划分。　　0.875 仍然位于 A 区间，所以第二个字符仍然为 A。接着对 A:
$\left[0,0.25\right)$ 再进行划分。　　0.875 位于 B 区间，所以第三个字符为 B。接着对 B:
$\left[0.125,0.225\right)$ 再进行划分。　　0.875 位于 A 区间，所以第四个字符为 A。　　依次类推，可以从 0.875 将整个字符解码出来。　　自适应上下文的概率模型　　以上三种编码方法都需要一个概率模型,否则不能最好的工作,但是这样的工作量大,所以引入自适应上下文的概率模型.

Daniel：消除时间和空间冗余的几种编码

霍夫曼编码的解题步骤_什么是哈夫曼编码

相关推荐