4.5 Shannon编码

Shannon编码

Shannon 编码（Shannon coding）是一种基于累积概率分布构造前缀码的方法。给定符号概率分布 $p_1,p_2,\dots ,p_m$，Shannon 编码的过程如下：首先计算每个符号的累积概率 $F_i={\sum }_{k<i}{p}_k$，然后取码长为 $l_i=\lceil -{\log }_D{p}_i\rceil$，最后将 $F_i$ 用 D 进制小数表示并取前 $l_i$ 位作为码字。

Shannon 编码相当于将概率分布补全为二分累积分布，进而将每个符号映射到该累积分布上的一个区间，通过读取区间的 D 进制表示来得到码字。这一构造方法也是证明 Kraft 不等式蕴涵前缀码存在性的重要思路——从累积分布出发，可以在 D 叉树上连贯地分配节点，确保所有码字不互为前缀。

Shannon 编码的平均码长满足 $H_D(X)\le \bar{L}<H_D(X)+1$。它虽然能够达到熵界但不一定是严格最优的（Huffman 编码通常具有更小的平均码长），其意义在于提供了从概率分布到前缀码的系统化构造方法，为后来更精细的算术编码等方案奠定了理论基础。

链接到

• 上一个知识点：4.4 最优编码长度
• 下一个知识点：4.6 二分分布