瞬時符号とクラフトの不等式: 情報理論入門 3

$$\forall x^*, y^* \in \mathcal{X}^*, f(x^*) = f(y^*) \Rightarrow x^* = y^*$$ とすると、\(x^* = x, y^* = y\) ととれば、$$\forall x, y \in \mathcal{X}, f(x) = f(y) \Rightarrow x = y$$ が成立する。

$$\forall x^*, y^* \in \mathcal{X}^*, \forall w^* \in \Sigma^*, f(x^*)w^* = f(y^*) \Rightarrow x^* = y^*$$ とすると、\(w^* = \varepsilon\) ととれば、$$\forall x^*, y^* \in \mathcal{X}^*, f(x^*) = f(y^*) \Rightarrow x^* = y^*$$ が成り立つ。

\(\Rightarrow\): $$\forall x^*, y^* \in \mathcal{X}^*, \forall w^* \in \Sigma^*, f(x^*)w^* = f(y^*) \Rightarrow x^* = y^*$$ とする。\(x^* = x, y^* = y\) ととると、$$\forall x, y \in \mathcal{X}, \forall w^* \in \Sigma^*, f(x)w^* = f(y) \Rightarrow x = y$$ が成り立つ。

\(\Leftarrow\): $$\forall x, y \in \mathcal{X}, \forall w^* \in \Sigma^*, f(x)w^* = f(y) \Rightarrow x = y \tag{1}$$とする。\(x^* = x_1, x_2, \cdots, x_n \in \mathcal{X}^*, y^* = y_1, y_2, \cdots, y_m \in \mathcal{X}^*\) に対して \(f(x^*) = f(y^*)\) であったとする。一般性を失うことなく \(|f(x_1)| \le |f(y_1)|\) を仮定する。このとき、仮定 (1)と \(f(x_1)w^* = f(y_1)\) より \(x_1 = y_1\) が成立。また、先頭の共通する記号を取り除くと \(f(x_2 \cdots x_n) = f(y_2 \cdots y_l)\) となるので、同様の議論により \(x_2 = y_2, \cdots, x_n = y_n, n = l\) と確定させられる。

\(\Rightarrow\): \(f\) を瞬時符号とし、\(L = \max_{x \in \mathcal{X}} |f(x)|\) を符号語の最大長とする。深さ \(L\) の符号の木を考える。各情報源記号 \(x \in \mathcal{X}\) について、\(f(x)\) に対応する頂点の部分木に印を付ける。接頭語符号性より、同じ頂点は二度印を付けられることがない。また、\(f(x)\) の部分木には \(2^{L – |f(x)|}\) 個の葉が含まれる。葉は全体で \(2^L\) 個しかないので、$$\begin{align*} \sum_{x \in \mathcal{X}} 2^{L – |f(x)|} &\le 2^L \\ \sum_{x \in \mathcal{X}} 2^{- |f(x)|} &\le 1 \end{align*}$$ が成り立つ。

\(\Leftarrow\): \(l \in \mathbb{N}^\mathcal{X}\) に対して $$\sum_{x \in \mathcal{X}} 2^{-l_x} \le 1 \tag{1}$$ が成り立つとする。一般性を失うことなく、\(\mathcal{X} = \{1, 2, \cdots, n\}\) かつ \(l_1 \le l_2 \le \cdots \le l_n\) であると仮定する。深さ \(l_n\) の印のない符号の木を構築し、\(i = 1, \cdots, n\) に対して順番に、深さ \(i\) のまだ印が付けられていない頂点を \(i\) の符号語とし、部分木全ての頂点に対して印をつける。構成法より明らかに接頭辞符号である。また、\(i\) の符号語を構築する際、深さ \(l_i\) の既に印の付いた頂点の数は $$\begin{align*} \sum_{k = 1}^{i-1} 2^{l_i – l_k} &= \left(\sum_{k = 1}^{n} 2^{l_i – l_k}\right) – \left(\sum_{k = i}^{n} 2^{l_i – l_k}\right) \\ &\le \left(\sum_{k = 1}^{n} 2^{l_i – l_k}\right) – \left(\sum_{k = i}^{i} 2^{l_i – l_k}\right) \\ &= \left(\sum_{k = 1}^{n} 2^{l_i – l_k}\right) – 1 \\ &= \left(2^{l_i} \sum_{k = 1}^{n} 2^{- l_k}\right) – 1 \\ &\le 2^{l_i} – 1\end{align*}$$ である。ただし、最後の不等式では式 (1) を用いた。よって、\(i\) の符号語を構築する際、深さ \(l_i\) には常にまだ印の付いていない頂点があるので、常にこのような符号は構成できる。