クラフトの不等式により、構成できる符号長の条件が分かりました。では、情報源が与えられたとき、どこまで平均長を下げることができるでしょうか？平均長の下界は一次エントロピーという簡単な量で記述できます。また、シャノン・ファノ符号という単純な符号を用いることで、下界に近い符号を構成することができます。
情報源記号を \(\mathcal{X}\) とし、符号アルファベットを \(\Sigma = \{0, 1\}\) とします。
情報源からは記号 \(x \in \mathcal{X}\) が確率 \(p(x)\) で生じるとします。
瞬時符号 \(f\colon \mathcal{X} \to \Sigma^*\) であって、平均長 \(\mathbb{E}_{x \sim p}[|f(x)|]\) が小さいものを構築するのが目的です。
平均符号長はいくらでも小さくできるわけではありません。たとえば、情報源記号が \(3\) 要素以上のとき、平均長を \(1\) にしようとする、つまり \(f(x) = 0 \text{ or } 1\) としようとすると、必ず符号が衝突するので、平均長を \(1\) とすることはできません。
よりタイトな平均符号長の限界を与えてくれるのが以下の定理です。
情報源 \((\mathcal{X}, p)\) のエントロピーを $$H(\mathcal{X}, p) = – \sum_{x \in \mathcal{X}} p(x) \log_2 p(x)$$ で定義する。
任意の瞬時符号 \(f\) について、$$\mathbb{E}_{x \sim p}[|f(x)|] \ge H(\mathcal{X}, p)$$ が成り立つ。
\(f\) を瞬時符号とする。\(l_x = |f(x)|\) とすると、クラフトの不等式より $$\sum_{x \in \mathcal{X}} 2^{-l_x} \le 1 \tag{1}$$ が成り立つ。式 (1) が成り立つ範囲で \(\sum_{x \in \mathcal{X}} p(x) l_x\) が最小となる \(l \in \mathbb{R}^{\mathcal{X}}\) を考える。ラグランジュ乗数を \(\lambda \ge 0\) とすると、ラグランジアンは $$L = \sum_{x \in \mathcal{X}} p(x) l_x + \lambda \left(\left(\sum_{x \in \mathcal{X}} 2^{-l_x}\right) – 1\right)$$ となる。これを \(l_x\) について微分すると、$$\frac{\partial L}{\partial l_x} = p(x) – \lambda (\log_e 2) 2^{-l_x}$$ となる。これをゼロとおくと、\(l_x = – \log_2 \frac{p(x)}{\lambda log_e 2}\) となり、これを制約に代入すると、\(\lambda = \frac{1}{\log_e 2}\) のとき、すなわち、\(l_x = – \log_2 p(x)\) のとき最小となる。よって、$$\begin{align*}\mathbb{E}_{x \sim p}[|f(x)|] &= \sum_{x \in \mathcal{X}} p(x) |f(x)| \\ &=\sum_{x \in \mathcal{X}} p(x) l_x \\ &\ge – \sum_{x \in \mathcal{X}} p(x) \log_2 p(x) \\ &= H(\mathcal{X}, p)\end{align*}$$ が成り立つ。
平均符号長には限界があることが分かりました。しかし、ちょうど限界を達成する符号は存在するとは限りません。なぜなら、\(- \log_2 p(x)\) は一般に整数ではなく、\(l_x \neq – \log_2 p(x)\) であれば証明中の不等号の等号が成り立たないからです。では、この限界に近いような符号は構成できるでしょうか？シャノン・ファノ符号は簡単かつ効果的な構成法を与えます。
情報源記号 \(x \in \mathcal{X}\) に対して長さ \(l_x = \text{ceil}\left(\log_2 \frac{1}{p(x)}\right)\) の符号語を割り当てる瞬時符号をシャノン・ファノ符号という
任意の情報源に対してシャノン・ファノ符号を構成できる
\(l_x = \text{ceil}\left(\log_2 \frac{1}{p(x)}\right)\) とすると、\(l_x\) は正整数であり、$$\begin{align*} \sum_{x \in \mathcal{X}} 2^{-l_x} &= \sum_{x \in \mathcal{X}} 2^{-\text{ceil}\left(\log_2 \frac{1}{p(x)}\right)} \\ &\le \sum_{x \in \mathcal{X}} 2^{-\log_2 \frac{1}{p(x)}} \\ &= \sum_{x \in \mathcal{X}} p(x) \\ &= 1\end{align*}$$ より、\(l_x\) はクラフトの不等式の条件を満たす。よって、このような瞬時符号を構成できる。
クラフトの不等式の証明では、構成的に符号を示していたことを思い出してください。よって、\(p(x)\) さえ分かれば、シャノン・ファノ符号を構築することができます。
また、シャノン・ファノ符号の平均符号長は限界値と高々 \(1\) しか違いません。
\(f\colon \mathcal{X} \to \Sigma^*\) をシャノン・ファノ符号とすると、$$\mathbb{E}_{x \sim p}[|f(x)|] < H_1(\mathcal{X}, p) + 1$$ が成り立つ。
\(l_x = \text{ceil}\left(\log_2 \frac{1}{p(x)}\right)\) とすると、$$\begin{align*} \mathbb{E}_{x \sim p}[|f(x)|] &= \sum_{x \in \mathcal{X}} p(x) l_x \\ &= \sum_{x \in \mathcal{X}} p_x \text{ceil}\left(\log_2 \frac{1}{p(x)}\right) \\ &< \sum_{x \in \mathcal{X}} p_x \left(\left(\log_2 \frac{1}{p(x)}\right) + 1\right) \\ &= \left(-\sum_{x \in \mathcal{X}} p_x \log_2 p(x)\right) + \sum_{x \in \mathcal{X}} p(x) \\ &= H_1(\mathcal{X}, p) + 1\end{align*}$$
平均符号長の限界とあわせると、以下のようにまとめられます。
平均符号長が最小となる瞬時符号 \(f\) は $$H_1(\mathcal{X}, p) \le \mathbb{E}_{x \sim p}[|f(x)|] < H_1(\mathcal{X}, p) + 1$$ を満たす。
- 瞬時符号の平均符号長の下界はエントロピーにより与えられる
- シャノン・ファノ符号により下界に近い平均符号長の符号を構成できる
