クラフトの不等式

ウィキペディア

クラフトの不等式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/03 01:29 UTC 版)

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

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

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

記号と用語

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

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

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

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

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

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

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

チャイティンの定数

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

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

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

外部リンク

• Kraft's inequality (NIST)