shannon entropy

\[H=-\sum_{i=1}^n p_i\log_2(p_i)\]

假设 \(a_1,\cdots,a_{32}\in\set{0,1}\), 有且仅有一个为 \(1\)

如果要从中找到那个为 \(1\) 的 \(a_i\), 用二分可以在 \(5\) 轮求出

如果我们每次用 \(1\) 比特来存储我们二分的猜测 (\(0\) 表示猜 \([\text{left}, \text{mid}]\), \(1\) 表示猜 \((\text{mid}, \text{right}]\))

那么 "满足 \(a_i=1\) 的 \(i\)" 这条信息值 \(5\) 比特

猜测出来的 \(5\) 比特信息正好对应 \(i\) 的二进制

如果每个 \(a_i\) 为 \(1\) 的概率可以不同, 那么我们可能知道哪些 \(a_i\) 更可能取 \(1\)

那我们平均猜测的次数就可能少于 \(5\), 即所需的信息量更少

于是香农用 \(H\) 表达一条信息理论上的最小编码长度, 即所需的信息量

用 \(p_i\) 表示 \(a_i=1\) 的概率

可以算出上面的 \(p_i=1/32\) 时, \(H=5\)

进一步有 \(H\leq 5\)

Huffman encoding

上面的香农熵看起来很像哈夫曼编码

事实上, 如果哈夫曼编码平均长度为 \(L\), 那么

\[H\leq L < H+1\]

例如, 有 \(10\) 个符号, 出现频率为 \([0.25,0.20,0.15,0.10,0.08,0.08,0.05,0.04,0.03,0.02]\)

那么 \(H\approx 2.959,L=2.96\)

可以看到极为接近, 且满足 \(H\leq L\)