4.4 最优编码长度

最优编码长度

最优编码长度问题是指在满足 Kraft 不等式 $\sum D^{-l_i}\le 1$ 的约束下，最小化平均编码长度 $\bar{L}=\sum p_i{l}_i$。这是一个典型的约束优化问题，可用拉格朗日乘数法求解。构造拉格朗日函数：

$$J=\sum p_i{l}_i+\lambda \left(\sum D^{-l_i}-1\right)$$

对 $l_i$ 求偏导并令其为零，得到 $p_i-\lambda D^{-l_i}\ln D=0$，解得最优实数码长为 $l_i^{\ast }=-{\log }_D{p}_i$。代入 Kraft 不等式可确定 $\lambda$，最终得到 $l_i^{\ast }=-{\log }_D{p}_i$。由于码长必须为整数，实际可取 $l_i=\lceil -{\log }_D{p}_i\rceil$，由此得到的平均码长满足：

$$H_D(X)\le \bar{L}<H_D(X)+1$$

左边的不等式由 Gibbs 不等式保证，右边则由取整操作自然得出。$H_D(X)$ 是以 $D$ 为底的信源熵，也是任何码长分配方案平均码长的理论下界。

一个重要的推广情形是：当编码所基于的概率分布 $q$ 与实际分布 $p$ 不一致时（即猜测分布为 $q$ 而真实分布为 $p$），平均编码长度会增加一个额外的开销。设按分布 $q$ 分配码长 $l_i=\lceil -{\log }_D{q}_i\rceil$，则实际平均码长满足：

$$\bar{L}\approx H_D(p)+D_{KL}(p\Vert q)$$

其中 $D_{KL}(p\Vert q)=\sum p_i{\log }_D\frac{p_i}{q_i}$ 是以 $D$ 为底的 KL 散度。这一结果揭示了 KL 散度的重要实际意义——它定量衡量了因分布不匹配造成的编码效率损失。分布估计越准确，KL 散度越小，编码越接近理论极限 $H_D(p)$。

链接到

• 上一个知识点：4.3 Kraft不等式
• 下一个知识点：4.5 Shannon编码