記号と用語
編集
クラフトの不等式について述べる為に、まず記号と用語を導入する。
集合Sに対し、Sの元を有限個並べてできる文字列全体の集合∐ i = 1 ∞ S i {\displaystyle \coprod _{i=1}^{\infty }S^{i}} をS ∗ {\displaystyle S^{*}} と書く。
S = { s 1 , s 2 , … , s n } {\displaystyle S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}\,} 及びT = { t 1 , t 2 , … , t r } {\displaystyle T=\{\,t_{1},t_{2},\ldots ,t_{r}\,\}\,} を二組のアルファベット とする。
本稿では、「符号」や「符号化関数」といった言葉は、1文字ずつ符号化する符号だけに用いるものとする。すなわち我々は符号化関数ϕ : S ∗ → T ∗ {\displaystyle \phi :S^{*}\to T^{*}} で以下の性質を満たすもののみを考える:
S上の任意の文字列s i 1 s i 2 … s i m {\displaystyle s_{i_{1}}s_{i_{2}}\ldots s_{i_{m}}} に対し、
ϕ ( s i 1 s i 2 … s i m ) = ϕ ( s i 1 ) ϕ ( s i 2 ) … ϕ ( s i m ) {\displaystyle \phi (s_{i_{1}}s_{i_{2}}\ldots s_{i_{m}})=\phi (s_{i_{1}})\phi (s_{i_{2}})\ldots \phi (s_{i_{m}})}
φが単射であるとき、φは一意に復号可能 であるという。
定理の形式的記述
編集
ϕ : S ∗ → T ∗ {\displaystyle \phi :S^{*}\to T^{*}} を符号化関数とし、ϕ ( s i ) ∈ T ∗ {\displaystyle \phi (s_{i})\in T^{*}} の文字数をℓ i {\displaystyle \ell _{i}} とする。
このとき、φが一意に復号可能なら、
∑ i = 1 n r − ℓ i ≤ 1 {\displaystyle \sum _{i=1}^{n}r^{-\ell _{i}}\leq 1}
が成立する。この不等式をクラフトの不等式 と呼ぶ。
(なおクラフトの不等式において等号が成立する必要十分条件は、φが完全な符号である事である。)
逆に自然数ℓ 1 , ℓ 2 , … , ℓ n {\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}\,} がクラフトの不等式を満たすなら、ある一意に復号可能な符号化関数ϕ : S ∗ ↦ T ∗ {\displaystyle \phi :S^{*}\mapsto T^{*}} が存在し、任意のiに対しϕ ( s i ) ∈ T ∗ {\displaystyle \phi (s_{i})\in T^{*}} の文字数がℓ i {\displaystyle \ell _{i}} となる。
接頭符号の場合の証明
編集
一意に復号可能な符号 の典型的な特殊例として接頭符号 がある。上述の定理を接頭符号の場合に対して証明する。
よく知られているように、接頭符号は次のようなr {\displaystyle r} -分木で表す事ができる:各頂点には r {\displaystyle r} 個のアルファベットのうち1つが割り振られ、各符号語は根から葉までの経路で表される。
この木の各頂点に以下のルールで0以上1以下のラベルを再帰的に割り振る:
根には1を割り振る。
頂点iにxが割り振られているとき、iの各々の子にx/rを割り振る。 各頂点はr個以下の子しか持たないので、頂点iの子に割り振られたラベルの総和は頂点iに割り振られたラベル以下である。この事実を葉から根に向かって再帰的に適応する事で次の事実が分かる:
葉に割り振られたラベルの総和は根に割り振られたラベル(=1)以下である。 前述したように、各符号語は根から葉までの経路に対応している。今グラフは木であるから、根から葉までの経路は、経路の終点である葉と一対一対応している。従って各符号語は木の葉と自然に対応付けられる。
ラベルの定義より、深さℓ i {\displaystyle \ell _{i}} の頂点のラベルは1 / r ℓ i {\displaystyle 1/r^{\ell _{i}}} である。木の作り方より符号語の長さは葉の深さに一致しているので、長さℓ i {\displaystyle \ell _{i}} の符号語に対応する葉のラベルは1 / r ℓ i {\displaystyle 1/r^{\ell _{i}}} である。
以上の議論より、符号語に対応する葉のラベルの総和∑ i = 1 n r − ℓ i {\displaystyle \sum _{i=1}^{n}r^{-\ell _{i}}} は根に割り振られたラベル(=1)以下である。よってクラフトの不等式が示せた。
また以上の議論から分かるように、頂点が丁度r個の子を持てば、その頂点の子に割り振られたラベルの総和は頂点iに割り振られたラベルに一致する。従って木が完全であるとき、葉に割り振られたラベルの総和は根に割り振られたラベル(=1)に一致する。
木の作り方より、木が完全である必要十分条件は、符号が完全である事である。よってクラフトの不等式の等号成立条件は符号が完全である事である。
最後に定理の逆を示す。今自然数ℓ 1 , ℓ 2 , … , ℓ n {\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}\,} がクラフトの不等式を満たすとする。必要ならℓ n + 1 , ℓ n + 2 , … {\displaystyle \ell _{n+1},\ell _{n+2},\ldots } を付け加える事で、等号∑ i = 1 n r − ℓ i = 1 {\displaystyle \sum _{i=1}^{n}r^{-\ell _{i}}=1} が成立していると仮定しても一般性を失わない。総和が1であるので、r − ℓ i {\displaystyle r^{-\ell _{i}}} をなんらかの確率と解釈する事ができる。定理の逆は、i番目の符号語が生起する確率がr − ℓ i {\displaystyle r^{-\ell _{i}}} であるとしたときのハフマン符号 を作る事で証明できる。
一般の場合の証明
編集
接頭符号とは限らない一般の符号に対してクラフトの不等式を示す。なお、定理の逆は、既に接頭符号が構成できる事を示しているので、証明の必要がない。
さて、ϕ : S ∗ → T ∗ {\displaystyle \phi :S^{*}\to T^{*}} を符号化関数とし、以下の母関数 を考える:
F ( X ) = ∑ i = 1 n X − | ϕ ( s i ) | {\displaystyle F(X)=\sum _{i=1}^{n}X^{-|\phi (s_{i})|}}
ただしここで、| ϕ ( s i ) | {\displaystyle |\phi (s_{i})|} はϕ ( s i ) {\displaystyle \phi (s_{i})} のビット数を表す。
m を任意の自然数とするとき、
( F ( X ) ) m = ( ∑ i = 1 n X − | ϕ ( s i ) | ) m = ∑ i 1 = 1 n ∑ i 2 = 1 n ⋯ ∑ i m = 1 n X − ( | ϕ ( s i 1 ) | + | ϕ ( s i 2 ) | + ⋯ + | ϕ ( s i m ) | ) = ∑ i 1 = 1 n ∑ i 2 = 1 n ⋯ ∑ i m = 1 n X − | ϕ ( s i 1 ⋯ s i 2 s i m ) | {\displaystyle {\begin{alignedat}{2}\left(F(X)\right)^{m}&=\left(\sum _{i=1}^{n}X^{-|\phi (s_{i})|}\right)^{m}=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}X^{-\left(|\phi (s_{i_{1}})|+|\phi (s_{i_{2}})|+\cdots +|\phi (s_{i_{m}})|\right)}\\&=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}X^{-|\phi (s_{i_{1}}\cdots s_{i_{2}}s_{i_{m}})|}\end{alignedat}}} が成立する。
右辺を次数毎にまとめたものを
( F ( X ) ) m = ∑ ℓ q ℓ X − ℓ {\displaystyle \left(F(X)\right)^{m}=\sum _{\ell }q_{\ell }\,X^{-\ell }}
と書くと、φの単射性より、q ℓ {\displaystyle q_{\ell }} は長さℓ {\displaystyle \ell } の符号語の数に等しい。長さℓ {\displaystyle \ell } の語はr ℓ {\displaystyle r^{\ell }} 個しかないので、
q ℓ ≤ r ℓ {\displaystyle q_{\ell }\leq r^{\ell }}
が成立する。
さて、ϕ ( s 1 ) , … , ϕ ( s n ) {\displaystyle \phi (s_{1}),\ldots ,\phi (s_{n})} の中で最も短い語の長さをmin、最も長い語の長さをmaxとする。すると F ( X ) {\displaystyle F(X)} の定義より、多項式( F ( X ) ) m = ∑ ℓ q ℓ X − ℓ {\displaystyle \left(F(X)\right)^{m}=\sum _{\ell }q_{\ell }\,X^{-\ell }} の最低次の項の次数はm minであり、最高次の項の次数はm maxである。
以上の議論より、
( F ( r ) ) m = ∑ ℓ q ℓ r − ℓ ≤ ∑ ℓ r ℓ r − ℓ = ∑ ℓ 1 ≤ m ( m a x − m i n + 1 ) {\displaystyle \left(F(r)\right)^{m}=\sum _{\ell }q_{\ell }\,r^{-\ell }\leq \sum _{\ell }r^{\ell }\,r^{-\ell }=\sum _{\ell }1\leq m(max-min+1)}
が成立する。
mは任意だったので上の不等式は任意のmに対して成立する。mを無限大に飛ばしたとき、左辺は指数関数的に変化するのに対し、右辺は線形にしか増加しない。従って任意のmに対して上の不等式が成立する事から
F ( r ) ≤ 1 {\displaystyle F(r)\leq 1}
が成立する。
ℓ i = | ϕ ( s i ) | {\displaystyle \ell _{i}=|\phi (s_{i})|} とすれば、 F ( X ) {\displaystyle F(X)} の定義より、
1 ≥ F ( r ) = ∑ i = 1 n r − ℓ i {\displaystyle 1\geq F(r)=\sum _{i=1}^{n}r^{-\ell _{i}}}
が成立する。すなわち、クラフトの不等式が証明された。
9, 14, 19, 67, 76 は葉ノードで、その深さはそれぞれ 3, 3, 3, 3, 2 である 二分木 について、クラフトの不等式を適用すると、次が成り立つ。
∑ ℓ ∈ l e a v e s 2 − d e p t h ( ℓ ) ≤ 1 {\displaystyle \sum _{\ell \in \mathrm {leaves} }2^{-\mathrm {depth} (\ell )}\leq 1}
これは、木の葉ノードに関する総和である。深さとは、根からの距離を意味する。右図の木で言えば、この総和は次のようになる。
1 4 + 4 ( 1 8 ) = 3 4 ≤ 1 {\displaystyle {\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leq 1}
チャイティンの定数
編集
アルゴリズム的情報理論 において、チャイティンの定数 は次のように定義される。
Ω = ∑ p ∈ P 2 − | p | {\displaystyle \Omega =\sum _{p\in P}2^{-|p|}}
これは、文法的に正しく停止する全てのプログラム毎にある被加数の総和 である。|p | は p のビット列の長さを表す。プログラムは他のプログラムの接頭部とはならない。つまり、ある被加数は別の文法的に妥当で停止するプログラムを表す被加数の接頭部にはならない。従って、このビット列群は接頭符号であり、クラフトの不等式から Ω ≤ 1 {\displaystyle \Omega \leq 1} が成り立つ。
外部リンク
編集