クラフトの不等式

クラフトの不等式（クラフトのふとうしき、英: Kraft's inequality）は、符号理論における不等式の1つで可変長符号が一意復号可能である為の必要条件を与える。等号成立条件は符号が完全である事である。クラフトの不等式は可変長符号が一意復号可能である為の十分条件ではないが、クラフトの不等式を満たす任意のパラメータに対し、そのパラメータを実現する一意復号可能な可変長符号の存在性が保証される。

計算機科学や情報理論で利用される接頭符号やトライ木で応用されている。

元々のクラフトの結果は接頭符号に対してのものだった。後にマクミランは任意の一意復号可能符号でも同様の不等式が成立することを示した。このためクラフト・マクミランの不等式とも呼ばれる。

記号と用語

クラフトの不等式について述べる為に、まず記号と用語を導入する。

集合Sに対し、Sの元を有限個並べてできる文字列全体の集合 $\coprod _{i=1}^{\infty }S^{i}$ を $S^{*}$ と書く。

$S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}\,$ 及び $T=\{\,t_{1},t_{2},\ldots ,t_{r}\,\}\,$ を二組のアルファベットとする。

本稿では、「符号」や「符号化関数」といった言葉は、1文字ずつ符号化する符号だけに用いるものとする。すなわち我々は符号化関数 $\phi :S^{*}\to T^{*}$ で以下の性質を満たすもののみを考える：

S上の任意の文字列 $s_{i_{1}}s_{i_{2}}\ldots s_{i_{m}}$ に対し、

$\phi (s_{i_{1}}s_{i_{2}}\ldots s_{i_{m}})=\phi (s_{i_{1}})\phi (s_{i_{2}})\ldots \phi (s_{i_{m}})$

φが単射であるとき、φは一意に復号可能であるという。

定理の形式的記述

$\phi :S^{*}\to T^{*}$ を符号化関数とし、 $\phi (s_{i})\in T^{*}$ の文字数を $\ell _{i}$ とする。

このとき、φが一意に復号可能なら、

$\sum _{i=1}^{n}r^{-\ell _{i}}\leq 1$

が成立する。この不等式をクラフトの不等式と呼ぶ。

（なおクラフトの不等式において等号が成立する必要十分条件は、φが完全な符号である事である。）

逆に自然数 $\ell _{1},\ell _{2},\ldots ,\ell _{n}\,$ がクラフトの不等式を満たすなら、ある一意に復号可能な符号化関数 $\phi :S^{*}\mapsto T^{*}$ が存在し、任意のiに対し $\phi (s_{i})\in T^{*}$ の文字数が $\ell _{i}$ となる。

接頭符号の場合の証明

一意に復号可能な符号の典型的な特殊例として接頭符号がある。上述の定理を接頭符号の場合に対して証明する。

よく知られているように、接頭符号は次のような $r$ -分木で表す事ができる：各頂点には $r$ 個のアルファベットのうち1つが割り振られ、各符号語は根から葉までの経路で表される。

この木の各頂点に以下のルールで0以上1以下のラベルを再帰的に割り振る：

根には1を割り振る。
頂点iにxが割り振られているとき、iの各々の子にx/rを割り振る。

各頂点はr個以下の子しか持たないので、頂点iの子に割り振られたラベルの総和は頂点iに割り振られたラベル以下である。この事実を葉から根に向かって再帰的に適応する事で次の事実が分かる：

葉に割り振られたラベルの総和は根に割り振られたラベル（＝1）以下である。

前述したように、各符号語は根から葉までの経路に対応している。今グラフは木であるから、根から葉までの経路は、経路の終点である葉と一対一対応している。従って各符号語は木の葉と自然に対応付けられる。

ラベルの定義より、深さ $\ell _{i}$ の頂点のラベルは $1/r^{\ell _{i}}$ である。木の作り方より符号語の長さは葉の深さに一致しているので、長さ $\ell _{i}$ の符号語に対応する葉のラベルは $1/r^{\ell _{i}}$ である。

以上の議論より、符号語に対応する葉のラベルの総和 $\sum _{i=1}^{n}r^{-\ell _{i}}$ は根に割り振られたラベル（＝1）以下である。よってクラフトの不等式が示せた。

また以上の議論から分かるように、頂点が丁度r個の子を持てば、その頂点の子に割り振られたラベルの総和は頂点iに割り振られたラベルに一致する。従って木が完全であるとき、葉に割り振られたラベルの総和は根に割り振られたラベル（＝1）に一致する。木の作り方より、木が完全である必要十分条件は、符号が完全である事である。よってクラフトの不等式の等号成立条件は符号が完全である事である。

最後に定理の逆を示す。今自然数 $\ell _{1},\ell _{2},\ldots ,\ell _{n}\,$ がクラフトの不等式を満たすとする。必要なら $\ell _{n+1},\ell _{n+2},\ldots$ を付け加える事で、等号 $\sum _{i=1}^{n}r^{-\ell _{i}}=1$ が成立していると仮定しても一般性を失わない。総和が1であるので、 $r^{-\ell _{i}}$ をなんらかの確率と解釈する事ができる。定理の逆は、i番目の符号語が生起する確率が $r^{-\ell _{i}}$ であるとしたときのハフマン符号を作る事で証明できる。

一般の場合の証明

接頭符号とは限らない一般の符号に対してクラフトの不等式を示す。なお、定理の逆は、既に接頭符号が構成できる事を示しているので、証明の必要がない。

さて、 $\phi :S^{*}\to T^{*}$ を符号化関数とし、以下の母関数を考える：

$F(X)=\sum _{i=1}^{n}X^{-|\phi (s_{i})|}$

ただしここで、 $|\phi (s_{i})|$ は $\phi (s_{i})$ のビット数を表す。

m を任意の自然数とするとき、

${\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}}$ が成立する。

右辺を次数毎にまとめたものを $\left(F(X)\right)^{m}=\sum _{\ell }q_{\ell }\,X^{-\ell }$ と書くと、φの単射性より、 $q_{\ell }$ は長さ $\ell$ の符号語の数に等しい。長さ $\ell$ の語は $r^{\ell }$ 個しかないので、

$q_{\ell }\leq r^{\ell }$

が成立する。

さて、 $\phi (s_{1}),\ldots ,\phi (s_{n})$ の中で最も短い語の長さをmin、最も長い語の長さをmaxとする。すると $F(X)$ の定義より、多項式 $\left(F(X)\right)^{m}=\sum _{\ell }q_{\ell }\,X^{-\ell }$ の最低次の項の次数はm minであり、最高次の項の次数はm maxである。

以上の議論より、

$\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)\leq 1$

が成立する。 $\ell _{i}=|\phi (s_{i})|$ とすれば、 $F(X)$ の定義より、

$1\geq F(r)=\sum _{i=1}^{n}r^{-\ell _{i}}$

が成立する。すなわち、クラフトの不等式が証明された。

例

二分木

9, 14, 19, 67, 76 は葉ノードで、その深さはそれぞれ 3, 3, 3, 3, 2 である

二分木について、クラフトの不等式を適用すると、次が成り立つ。

$\sum _{\ell \in \mathrm {leaves} }2^{-\mathrm {depth} (\ell )}\leq 1$

これは、木の葉ノードに関する総和である。深さとは、根からの距離を意味する。右図の木で言えば、この総和は次のようになる。

${\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leq 1$

チャイティンの定数

アルゴリズム的情報理論において、チャイティンの定数は次のように定義される。

$\Omega =\sum _{p\in P}2^{-|p|}$

これは、文法的に正しく停止する全てのプログラム毎にある被加数の総和である。|p| は p のビット列の長さを表す。プログラムは他のプログラムの接頭部とはならない。つまり、ある被加数は別の文法的に妥当で停止するプログラムを表す被加数の接頭部にはならない。従って、このビット列群は接頭符号であり、クラフトの不等式から $\Omega \leq 1$ が成り立つ。