1 引言
霍夫曼码是一种无损编码，而且是最优的符号码。但是，它有两个缺点：（1）每个符号至少需要一个比特；（2）当符号的概率分布变化时，使用不方便。
用一个例子来看看霍夫曼编码的第一个缺点（即每个符号至少需要1个比特）。
信源从符号集 A = { a 1 , a 2 , a 3 } A = \{a_1, a_2,a_3 \} A={a1,a2,a3}中选择独立同分布的符号，概率分布为𝑃(𝑎_1 )=0.95,𝑃(𝑎_2 )=0.02,𝑃(𝑎_3 )=0.03。它的熵为0.335比特/符号。才3个符号，所以这个霍夫曼码很简单，如下所示。
它的平均码长为1.05比特/符号，远大于熵（0.335比特/符号）。原因是符号
a
1
a_1
a1的信息量为
−
log
0.95
=
0.074
-\log{0.95}= 0.074
−log0.95=0.074比特，远小于其码长（1比特）。给
a
1
a_1
a1分配长度为1的码是很浪费的。
为了减小平均码长，下面将两个符号（独立同分布的）合并为一个扩展符号，进行霍夫曼编码。扩展符号的概率分布如下图。
其霍夫曼码的构造过程如下图所示。
2个扩展符号的平均码长为1.222比特/扩展符号。相当于单个符号的平均码长为0.611比特，这比前面针对单个符号编码的平均码长短了许多，但是仍然很长，约为熵的2倍。
我们可以进一步扩展，当扩展为8个符号时，单个符号的平均码长与熵接近。但符号集大小为 3 8 = 6561 3^8=6561 38=6561。对于许多应用，如此规模的霍夫曼码是不现实的。
该例子表明，为符号序列（符号组）生成码字，比为单个符号生成码字，码率更优。但是，为了给长为
m
m
m的某符号序列指定霍夫曼码，需要为所有长为
m
m
m的符号序列构造编码树。即需要构建整个码本，其大小随
m
m
m指数增长！
而算术编码能做到：能为特定的符号序列（当前要压缩的数据）指定码字，同时又不需要为所有的符号序列（当前数据中不出现的）指定码字。当 m m m很大时，该属性很重要。
2 算术编码
对于信源输出的符号序列，算术编码是对整个符号序列进行编码。为了实现无损编码，不同的符号序列需要映射为不同的标签（tag）。我们可以用[0,1)区间的实数（二进制形式）作为标签。由于[0,1)区间有无穷多个实数，足够给每个序列分配一个唯一的标签。那么，如何将符号序列映射为[0,1)区间的实数？利用累积分布函数（CDF）。
一个随机试验（如抛硬币、扔色子）所有可能结果组成一个基本空间Ω。 随机变量𝑋是定义在基本空间Ω上的、取值为实数的函数。 即随机试验每个可能结果都有实轴上的点与之对应。 为了统一起见和方便起见，随机变量采用下面的映射： X ( a i ) = i , a i ∈ A X(a_i )=i, a_i \in A X(ai)=i,ai∈A。其中， A = { a 1 , a 2 , … , a n } A=\{a_1,a_2,…,a_n \} A={a1,a2,…,an}为离散信源的符号集。
例如，随机抛硬币，可能的结果有正面朝上、反面朝上两种 。当正面朝上时， X X X取值1；当反面朝上时， X X X取值2。 又如，随机扔色子，所有可能结果是1点、2点、3点、4点、5点和6点， X X X分别取值1，2，3，4，5，6。 又如，随机从英文文本（已经过处理，只有小写字母和空格，无标点符号）中抽取字母，所有可能结果是abcd…z-，X分别取值1,2,…,27。
随机变量 X X X的概率函数为 P ( X = i ) = P ( a i ) P(X=i)=P(a_i) P(X=i)=P(ai)。累积密度函数 F X ( i ) = ∑ k = 1 i P ( X = k ) F_X (i)=∑_{k=1}^i P(X=k) FX(i)=k=1∑iP(X=k)
假设没有概率为0的符号，每个符号都对应一个唯一的 F X ( i ) F_X (i) FX(i)。可按照 F X ( i ) F_X (i) FX(i)对[0,1)区间切分。
如果只需对单个符号编码，那么在对应子区间随便取一个值作为标签（码字即二进制表示）。
2.1 生成标签
例如，某信源的符号集为 A = { a 1 , a 2 , a 3 } A=\{a_1,a_2,a_3 \} A={a1,a2,a3}，概率为 P ( a 1 ) = 0.7 P(a_1 )=0.7 P(a1)=0.7, P ( a 2 ) = 0.1 P(a_2 )=0.1 P(a2)=0.1, P ( a 3 ) = 0.2 P(a_3 )=0.2 P(a3)=0.2。
编码开始前，没有任何符号，我们只知道标签对应的是整个[0,1)区间。当收到第1个符号后，区间缩小到该符号对于的子区间。然后，按照累积分布函数对该子区间做同样的切分。当收到第2个符号后，区间缩小到子区间中的子区间。对于所有符号依次做以上区间切分，直到最后一个符号，就得到一个很小的子区间，该子区间内任何一个数字（后面讲，用哪个数字的压缩率高）都可以作为序列的标签（其二进制表示即编码结果）。
前面对确定符号序列的标签所在区间，做了直观解释。下面给出具体的计算公式。假设取区间的中点作为标签。先考虑单个符号。 符号 a i a_i ai的标签为 T X ( a i ) = ∑ k = 1 i − 1 P ( X = k ) + 0.5 P ( X = i ) = F X ( i − 1 ) + 0.5 P ( X = i ) T_X (a_i )=∑_{k=1}^{i−1} P(X=k) +0.5P(X=i) =F_X (i−1)+0.5P(X=i) TX(ai)=k=1∑i−1P(X=k)+0.5P(X=i)=FX(i−1)+0.5P(X=i)
下表为掷色子时单个符号的标签。
长为𝑚的符号序列 x i x_i xi的标签为 T X ( m ) ( x i ) = ∑ y < x i P ( y ) + 0.5 P ( x i ) T_X^{(m)} (x_i )=∑_{y<x_i} P(y)+0.5P(x_i) TX(m)(xi)=∑y<xiP(y)+0.5P(xi) 其中， y y y是排在 x i x_i xi之前的等长序列。
以色子为例，𝑚=2。序列的排序方法如下：11,12,13,14,15,16,21,22,23,…,64,65,66。例如，色子序列13的标签为 T X ( 2 ) ( 13 ) = P ( x = 11 ) + P ( x = 12 ) + 0.5 P ( x = 13 ) = 1 ∕ 36 + 1 ∕ 36 + 1 ∕ 72 = 5 ∕ 72 。 T_X^{(2)} (13)=P(x=11)+P(x=12)+0.5P(x=13)=1∕36+1∕36+1∕72=5∕72。 TX(2)(13)=P(x=11)+P(x=12)+0.5P(x=13)=1∕36+1∕36+1∕72=5∕72。
如果序列很长，求和项包含的序列非常多（指数增长）。上述式子不适合计算。
对于序列
x
=
(
x
1
x
2
.
.
.
x
n
)
x=(x_1 x_2 ... x_n)
x=(x1x2...xn)，可用递归的方法计算区间的上下限。
下限
l
(
n
)
=
l
(
n
−
1
)
+
(
u
(
n
−
1
)
−
l
(
n
−
1
)
)
F
X
(
x
n
−
1
)
l^{(n)}=l^{(n-1)}+(u^{(n-1)}-l^{(n-1)})F_X(x_n-1)
l(n)=l(n−1)+(u(n−1)−l(n−1))FX(xn−1)
上限
u
(
n
)
=
l
(
n
−
1
)
+
(
u
(
n
−
1
)
−
l
(
n
−
1
)
)
F
X
(
x
n
)
u^{(n)}=l^{(n-1)}+(u^{(n-1)}-l^{(n-1)})F_X(x_n)
u(n)=l(n−1)+(u(n−1)−l(n−1))FX(xn)
标签为上下限的中点。
例如，
A
=
{
a
1
,
a
2
,
a
3
}
A=\{a_1,a_2,a_3 \}
A={a1,a2,a3}，概率为
P
(
a
1
)
=
0.8
P(a_1 )=0.8
P(a1)=0.8,
P
(
a
2
)
=
0.02
P(a_2 )=0.02
P(a2)=0.02,
P
(
a
3
)
=
0.18
P(a_3 )=0.18
P(a3)=0.18。
对于序列𝟏𝟑𝟐𝟏，计算其标签。
F
X
(
0
)
=
0
,
F
X
(
1
)
=
0.8
,
F
X
(
2
)
=
0.82
,
F
X
(
3
)
=
1
F_X (0)=0,F_X (1)=0.8, F_X (2)=0.82, F_X (3)=1
FX(0)=0,FX(1)=0.8,FX(2)=0.82,FX(3)=1
l
(
0
)
=
0
,
u
(
0
)
=
1
l^{(0)}=0,u^{(0)}=1
l(0)=0,u(0)=1
l
(
1
)
=
0
+
(
1
−
0
)
0
=
0
,
u
(
1
)
=
0
+
(
1
−
0
)
0.8
=
0.8
l^{(1)}=0+(1−0)0=0, u^{(1)}=0+(1−0)0.8=0.8
l(1)=0+(1−0)0=0,u(1)=0+(1−0)0.8=0.8
l
(
2
)
=
0
+
(
0.8
−
0
)
F
X
(
2
)
=
0.656
l^{(2)}=0+(0.8−0)F_X (2)=0.656
l(2)=0+(0.8−0)FX(2)=0.656,
u
(
(
2
)
)
=
0
+
(
0.8
−
0
)
F
X
(
3
)
=
0.8
u^((2))=0+(0.8−0) F_X (3)=0.8
u((2))=0+(0.8−0)FX(3)=0.8
l
(
3
)
=
0.656
+
(
0.8
−
0.656
)
F
X
(
1
)
=
0.7712
l^{(3)}=0.656+(0.8−0.656) F_X (1)=0.7712
l(3)=0.656+(0.8−0.656)FX(1)=0.7712,
u
(
3
)
=
0.656
+
(
0.8
−
0.656
)
F
X
(
2
)
=
0.77408
u^{(3)}=0.656+(0.8−0.656) F_X (2)=0.77408
u(3)=0.656+(0.8−0.656)FX(2)=0.77408
l
(
4
)
=
0.7712
+
(
0.77408
−
0.7712
)
F
X
(
0
)
=
0.7712
l^{(4)}=0.7712+(0.77408−0.7712) F_X (0)=0.7712
l(4)=0.7712+(0.77408−0.7712)FX(0)=0.7712,
u
(
4
)
=
0.7712
+
(
0.77408
−
0.7712
)
F
X
(
1
)
=
0.773504
u^{(4)}=0.7712+(0.77408−0.7712) F_X (1)=0.773504
u(4)=0.7712+(0.77408−0.7712)FX(1)=0.773504
标签为
(
0.7712
+
0.773504
)
/
2
=
0.772352
。
(0.7712+0.773504)/2=0.772352。
(0.7712+0.773504)/2=0.772352。
2.2 解码
还是上面的例子。对于标签0.772352，解码原序列。按顺序一次确定一个符号。那么何时解码结束？已知序列长度或者使用特殊的结束符。
2.3 为什么可以压缩？
前面为了容易理解，用十进制小数表示标签；而具体实现时，用二进制表示。许多小数需要无限长二进制表示（如0.1,0.2），不能实现压缩。在⌈log 1/(𝑃(𝑥))⌉+1处截断，数字仍在同一区间内，所以仍唯一可译。
为什么数字仍在同一区间内？因为原始数字是区间的中点，区间的大小是𝑃(𝑥)，截断误差2^(−(⌈log 1/(𝑃(𝑥))⌉+1) )≤0.5𝑃(𝑥)。假设信源为i.i.d.随机变量𝑋，𝑚个符号所构成序列的信息量log 1/(𝑃(𝑥))=𝑚𝐻(𝑋) ⌈log 1/(𝑃(𝑥))⌉+1≤𝑚𝐻(𝑋)+2。即𝑚个符号压缩为至多𝑚𝐻(𝑋)+2比特。
3 具体实现问题
3.1 比例调整
实际实现时，还有一个问题需要考虑。随着符号数增加，区间会越来越小，小数点后的数字越来越多。如何在计算机上存储极高精度的数字？用办法：比例调整编码时，按照一定规则对数字进行放大。解码时，用同样规则进行缩小即可。
3.2 自适应算术编码
算术编码可以是静态的或是自适应的。在静态算术编码中（前面介绍的），信源符号的概率是固定的。但是很多时候事先不知道精确的信源符号概率。需要自适应算术编码，根据编码时符号出现的频繁程度，动态修改符号概率。在编码期间，估算信源符号概率的过程叫建模（modeling）。
每来一个符号，符号概率进行更新，区间切分随着概率的变化而变化。编码和解码的概率更新方法保持一致，即可正确解码。文章来源：https://www.toymoban.com/news/detail-714442.html
4. 对比算术编码与霍夫曼编码
假设用两种编码方法对长度𝑚的符号序列进行编码，假设使用扩展符号（𝑚个符号）进行霍夫曼编码。算术编码码率范围为： H ( X ) ≤ l A ≤ H ( X ) + 2 ∕ m H(X)≤l_A≤H(X)+2∕m H(X)≤lA≤H(X)+2∕m。霍夫曼编码码率范围为： H ( X ) ≤ l A ≤ H ( X ) + 1 ∕ m H(X)≤l_A≤H(X)+1∕m H(X)≤lA≤H(X)+1∕m。相比之下，霍夫曼编码的上限更低。但是，对于算术编码，序列长度𝑚可以取很大；而霍夫曼编码的𝑚不能很大。因此，算术编码可以实现更高的压缩比。但是，算术编码的不足是算法复杂、专利多。因此，实际中二者的应用都很多。文章来源地址https://www.toymoban.com/news/detail-714442.html
到了这里，关于信息论基础：算术编码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
