Kraftの不等式(Kraft inequality)とは、$D$ 種類の文字の列を符号語とする符号の符号語の長さ $\ell_i$ が満たす条件 $\sum_iD^{-\ell_i}\le1$ のことで、一意に復号できる符号は必ずこれを満たし(McMillan)、逆にこれを満たす長さの組には、どの符号語もほかの符号語の先頭部分でない接頭符号がある(Kraft)。符号語が可算無限個でも成り立ち、有限の接頭符号で等号が成り立つことは、どの無限列もある符号語で始まることと同値である。平均の長さはエントロピーと、長さから決まる分布との Kullback–Leibler 情報量の和で表され、整数を $\log_2n+$ 定数 の長さで書く一意に復号できる符号がないことも従う。
Kraftの不等式(Kraft inequality)は、文字が $D$ 種類の列を符号語とする符号について、符号語の長さ $\ell_1,\ell_2,\dots$ が満たすべき条件
$$
\sum_iD^{-\ell_i}\le1
$$
である。どの符号語もほかの符号語の先頭部分にならない符号(接頭符号)の長さはこれを満たし、逆にこれを満たす長さの組には、その長さをもつ接頭符号がある。さらに、受け取った列を一通りにしか区切れない符号(一意に復号できる符号)の長さも同じ不等式を満たす(McMillan)。この 2 つを合わせて Kraft–McMillan の不等式 ともいう。長さ $\ell$ の符号語 1 つは「予算 $D^{-\ell}$」を使い、使える予算の総額が $1$ だと読める。
この記事では、符号の文字の種類 $D$ が一般で、符号語が可算無限個ある場合も含めて、両方向を証明する。$D=2$ で符号語が有限個の場合の不等式と逆向きの構成は 二分木 の定理「葉の深さの不等式」に、2 文字の場合の McMillan の不等式と平均の長さの下界は Huffman符号 と エントロピー にある。ここでは別の証明(区間による証明、母関数の和による証明、数え上げによる構成)を与え、等号の意味、平均の長さと Kullback–Leibler 情報量の関係、整数の符号などの無限の場合を扱う。
$D\ge2$ とし、符号の文字 の集合を $\mathcal A=\{0,1,\dots,D-1\}$ とする。$\mathcal A^*$ を $\mathcal A$ の文字の有限列(空列を含む)の全体、$\mathcal A^+$ を空でない有限列の全体、$\lvert w\rvert$ を列 $w$ の長さとする。$w$ が $w'$ の 接頭辞(先頭部分)であるとは、ある $v\in\mathcal A^*$ で $w'=wv$ となることをいう。
$\mathcal X$ を空でない有限集合または可算無限集合とする。
符号語は空でないので、空の列だけが空列に移る。よって一意に復号できることは、拡張が空列を含む有限列の全体で単射であることと同じである。接頭符号は一意に復号できる:受け取った列の先頭から読み、符号語に一致した時点で区切ると、接頭符号ではその区切り方しかないからである。接頭符号でなくても一意に復号できる符号はある($\{0,01\}$ は、各符号語を逆から読むと接頭符号になるので、後ろから区切れる)。
区間を使うと、接頭辞の関係が区間の包含に変わる。$w=w_1\cdots w_\ell\in\mathcal A^\ell$ に、$D$ 進小数 $0.w:=\sum_{j=1}^\ell w_jD^{-j}$ を左端とする長さ $D^{-\ell}$ の半開区間
$$
I(w):=\bigl[0.w,\ 0.w+D^{-\ell}\bigr)\subseteq[0,1)
$$
を対応させる。$I(w)$ は、$D$ 進展開の最初の $\ell$ 桁が $w$ である実数の全体である(展開は、末尾が $D-1$ の無限の並びにならないものをとる)。
$w,w'\in\mathcal A^*$ について、$w$ が $w'$ の接頭辞なら $I(w)\supseteq I(w')$ であり、どちらもどちらの接頭辞でもなければ $I(w)\cap I(w')=\emptyset$ である。
$I(w)$ が「最初の $\lvert w\rvert$ 桁が $w$ である数の全体」であることから従う。$w$ が $w'$ の接頭辞なら、最初の $\lvert w'\rvert$ 桁が $w'$ の数は最初の $\lvert w\rvert$ 桁が $w$ である。どちらも接頭辞でなければ、両者が初めて異なる位置 $j\le\min(\lvert w\rvert,\lvert w'\rvert)$ があり、第 $j$ 桁が $w_j$ かつ $w'_j$ である数はない。$\square$
$\mathcal X$ を空でない有限集合または可算無限集合とする。
1 は、区間の長さを比べるだけで分かる接頭符号の場合(prop-kraft-prefix)を先に示し、一般の一意に復号できる符号の場合を母関数で示す(prf-kraft-main-1)。2 は長さの小さい順に符号語を選んで示す(prf-kraft-main-2)。
接頭符号 $c$ では $\sum_xD^{-\ell_x}$ は、区間 $I(c(x))$($x\in\mathcal X$)の和集合の長さに等しく、とくに $1$ 以下である。
接頭符号なので、lem-kraft-interval により区間 $I(c(x))$ は互いに交わらない。$[0,1)$ の互いに交わらない区間の可算族の長さの和は、和集合の長さ(Lebesgue 測度)に等しく $1$ 以下である。$I(c(x))$ の長さは $D^{-\ell_x}$ である。$\square$
一意に復号できる符号では区間が交わりうる($\{0,01\}$ では $I(01)\subseteq I(0)$)ので、別の論法が要る。符号語の長さの母関数を使う。
$c$ を一意に復号できる符号とする。拡張は単射なので $c$ 自身も単射で、長さ $\ell$ の符号語は $D^\ell$ 個以下である。$0< t< \frac1D$ について
$$
f(t):=\sum_{x\in\mathcal X}t^{\ell_x}\le\sum_{\ell\ge1}D^\ell t^\ell< \infty
$$
とおく。$k\ge0$ について、$f(t)^k$ は非負の項の級数の積なので、項を並べ替えて
$$
f(t)^k=\sum_{(x_1,\dots,x_k)\in\mathcal X^k}t^{\ell_{x_1}+\cdots+\ell_{x_k}}
$$
と書ける($k=0$ では空の列 1 つの項 $1$)。$k$ について足し、長さ $n$ に移る記号の列の個数を $A_n$ とすると
$$
\sum_{k\ge0}f(t)^k=\sum_{n\ge0}A_nt^n
$$
である(どちらも非負の項の和で、値は $+\infty$ も許す)。拡張は空列を含む有限列の全体で単射なので、長さ $n$ に移る記号の列は長さ $n$ の文字列の個数 $D^n$ 以下で、$A_n\le D^n$ である。よって
$$
\sum_{k\ge0}f(t)^k\le\sum_{n\ge0}(Dt)^n=\frac1{1-Dt}< \infty
$$
となる。左辺は等比級数なので $f(t)< 1$ であり、$\frac1{1-f(t)}\le\frac1{1-Dt}$、すなわち
$$
f(t)\le Dt\qquad\Bigl(0< t< \frac1D\Bigr)
$$
を得る。$t\uparrow\frac1D$ とすると、各項 $t^{\ell_x}$ は単調に $D^{-\ell_x}$ に増加するので、単調収束定理により $f(t)\to K(c)$ で、$K(c)\le1$ である。$\square$
$\sum_xD^{-\ell_x}\le1$ なので、各 $\ell$ について $\ell_x=\ell$ となる $x$ は $D^\ell$ 個以下で、有限個である。よって $\mathcal X$ の元を、長さが小さい順(同じ長さの中では任意の順)に $x_1,x_2,\dots$ と並べられる。$\ell_i:=\ell_{x_i}$ とおくと $\ell_1\le\ell_2\le\cdots$ である。
$c(x_1),\dots,c(x_{i-1})$ を、どれもほかの接頭辞でない長さ $\ell_1,\dots,\ell_{i-1}$ の列として選んだとする。長さ $\ell_i$ の列のうち、ある $c(x_j)$($j< i$)を接頭辞にもつものは、各 $j$ について $D^{\ell_i-\ell_j}$ 個なので、合わせて
$$
\sum_{j< i}D^{\ell_i-\ell_j}=D^{\ell_i}\sum_{j< i}D^{-\ell_j}\le D^{\ell_i}\bigl(1-D^{-\ell_i}\bigr)=D^{\ell_i}-1
$$
個以下である($\sum_{j\le i}D^{-\ell_j}\le1$ による)。長さ $\ell_i$ の列は $D^{\ell_i}$ 個あるので、どの $c(x_j)$($j< i$)も接頭辞にもたない列 $w$ がある。これを $c(x_i)$ とする。$j< i$ では $\ell_j\le\ell_i$ なので、$w$ が $c(x_j)$ の接頭辞なら $w=c(x_j)$ となり、$w$ が $c(x_j)$ を接頭辞にもつことになって選び方に反する。よって $c(x_1),\dots,c(x_i)$ もどれもほかの接頭辞でない。帰納法により、すべての $i$ で $c(x_i)$ が定まり、$c$ は接頭符号である。$\square$
最後の主張は 1 と 2 から従う。一意に復号できる符号の長さは 1 により不等式を満たし、2 によりその長さの接頭符号がある。圧縮の効率を長さで測る限り、接頭符号に限っても何も失わない。
PW25 Theorem 10.9(pp. 207–208)は 2 文字の場合を可算な $\mathcal X$ で述べ、接頭符号の 1 を、一様な硬貨の列が符号語を書き終えて止まる確率として示し、一意に復号できる場合を $f(\frac12)^k\le k\ell_{\max}$ から(有限の $\mathcal X$ で示して有限部分集合に移って)示し、2 を $\sum_{j< i}2^{-\ell_j}$ の 2 進展開の最初の $\ell_i$ 桁を符号語にして示している。上の 1 の証明は $k$ について和をとって等比級数にするので、無限の $\mathcal X$ をそのまま扱え、$f(t)\le Dt$ という量的な形も得られる。不等式の名と帰属(逆向きの構成が Kraft、一意に復号できる場合が McMillan(1956 年))は Mac03 §5.2(pp. 94–95)による。
2 の証明は長さを小さい順に並べ替えてから符号語を選ぶ。長さの要求が任意の順に一つずつ届き、届いたその場で符号語を決めなければならない場合にも、区間の未使用部分を工夫して保てば同じ結論が得られる。これが Chaitinの定数 の記事の Kraft–Chaitin の補題で、接頭的な機械のプログラムを割り当てる道具として使われる。
Mac03 p. 95 は、Kraft の和がちょうど $1$ の一意に復号できる符号を 完全 な符号と呼んでいる。符号語が有限個の接頭符号では、等号は「もう符号語を足せない」ことと同じである。
$\mathcal X$ を有限集合、$c$ を接頭符号、$L:=\max_x\ell_x$ とする。次は同値である。
(a) $K(c)=1$。
(b) 長さ $L$ のどの列も、ある符号語を接頭辞にもつ。
(c) $\mathcal A$ の文字の無限列はどれも、ある符号語で始まる。
(d) どの $w\in\mathcal A^+$ を新しい符号語として足しても、接頭符号でなくなる。
長さ $L$ の列 $v$ の区間 $I(v)$ は $D^L$ 個で $[0,1)$ を分割し、lem-kraft-interval により各 $I(v)$ は、$v$ がある符号語を接頭辞にもてばその符号語の区間に含まれ、そうでなければどの符号語の区間とも交わらない(符号語の長さは $L$ 以下なので、$v$ が符号語の真の接頭辞になることはない)。よって符号語の区間の和集合は、(b) の条件を満たす $v$ の区間の和集合に等しく、prop-kraft-prefix によりその長さが $K(c)$ である。
(a)⇔(b):$K(c)$ は「符号語を接頭辞にもつ長さ $L$ の列の個数」の $D^{-L}$ 倍なので、$K(c)=1$ はその個数が $D^L$ であることと同じである。(b)⇔(c):無限列は最初の $L$ 文字で始まり、長さ $L$ のどの列も何かの無限列の最初の $L$ 文字である。(a)⇒(d):$w$ を足した符号が接頭符号なら、prop-kraft-prefix によりその Kraft の和 $1+D^{-\lvert w\rvert}$ は $1$ 以下のはずで矛盾する。(d)⇒(b):(b) が成り立たないなら、符号語を接頭辞にもたない長さ $L$ の列 $v$ がある。$v$ はどの符号語の接頭辞でもない(長さ $L$ 以下の列の接頭辞になるのは $v$ と長さが等しいときだけで、そのとき $v$ はその符号語に等しく、それを接頭辞にもつことになる)ので、$v$ を足しても接頭符号のままであり、(d) に反する。$\square$
符号語が無限個あると (a) と (c) は同値でない。prop-kraft-prefix から分かるのは、$K(c)$ が「一様に無作為な無限列が符号語で始まる確率」に等しいことで、$K(c)=1$ は「ほとんどすべての無限列が符号語で始まる」ことを意味するにとどまる(ex-kraft-unary)。
符号の文字が 3 種類以上のとき、完全な有限の接頭符号の符号語の個数には制約がある。
有限の符号 $c$ で $K(c)=1$ なら、符号語の個数 $m=\lvert\mathcal X\rvert$ は $m\equiv1\pmod{D-1}$ を満たす。
$L:=\max_x\ell_x$ とし、$\sum_xD^{-\ell_x}=1$ の両辺に $D^L$ を掛けると $\sum_xD^{L-\ell_x}=D^L$ である。$D\equiv1\pmod{D-1}$ なので、両辺を $D-1$ で割った余りを比べて $m\equiv1\pmod{D-1}$ を得る。$\square$
$D=2$ では制約はない。$D=3$ では完全な符号の符号語は奇数個で、4 個の記号には完全な 3 進の接頭符号がない(たとえば長さ $(1,1,2,2)$ の和は $\frac89$)。3 進の Huffman符号 を作るとき、確率 $0$ の記号を足して個数を $1+2j$ の形にしてから 3 つずつ併合するのはこのためである。
$p$ を $\mathcal X$ 上の確率分布で $p(x)>0$($x\in\mathcal X$)とし、符号 $c$ の平均の長さを $L(c):=\sum_xp(x)\ell_x$ とする。$\log$ は自然対数、$H(p):=-\sum_xp(x)\log p(x)$ を エントロピー(nat)、$D(p\Vert q):=\sum_xp(x)\log\frac{p(x)}{q(x)}$ を Kullback–Leibler情報量 とする。符号語の長さは $D$ 進の文字数なので、$L(c)\log D$ が nat で測った長さである。
$c$ を一意に復号できる符号とし、$L(c)< \infty$ とする。$K:=K(c)$、$r(x):=D^{-\ell_x}/K$ とおくと、$r$ は確率分布で、$H(p)< \infty$ であり
$$
L(c)\log D=H(p)+D(p\Vert r)-\log K
$$
が成り立つ。とくに $L(c)\ge H(p)/\log D$ であり、等号は $p(x)=D^{-\ell_x}$($x\in\mathcal X$)のときに限る。
thm-kraft-main の 1 により $0< K\le1$ である。各 $x$ で
$$
\ell_x\log D=-\log D^{-\ell_x}=-\log p(x)+\log\frac{p(x)}{r(x)}-\log K
$$
である。$b_x:=p(x)\log\frac{p(x)}{r(x)}$ とおくと、$\log u\ge1-\frac1u$ から $b_x\ge p(x)-r(x)$ なので、$b_x$ の負の部分の和は $\sum_x\lvert p(x)-r(x)\rvert\le2$ 以下で、$\sum_xb_x=D(p\Vert r)$ は $[0,\infty]$ の値として定まる($\ge0$ は Gibbs の不等式、エントロピー)。上の式に $p(x)$ を掛けて $-p(x)\log p(x)=p(x)\ell_x\log D-b_x+p(x)\log K$ と書き、$x$ について足すと、右辺の第 1 項の和は $L(c)\log D< \infty$、第 2 項の和は $-D(p\Vert r)$、第 3 項の和は $\log K$ なので、左辺の和 $H(p)$ は $L(c)\log D-D(p\Vert r)+\log K$ に等しい。$H(p)\ge0$ なので $D(p\Vert r)< \infty$ で、$H(p)\le L(c)\log D$ は有限であり、等式が成り立つ。$D(p\Vert r)\ge0$、$-\log K\ge0$ から下界が従う。等号は $D(p\Vert r)=0$ かつ $K=1$、すなわち $p=r$ かつ $K=1$ のときで、それは $p(x)=D^{-\ell_x}$ と同じである。$\square$
$D=2$ の同じ等式は PW25 p. 209(Theorem 10.10 の 2 つ目の証明)にある。等式は、符号の損失 $L(c)\log D-H(p)$ が「長さから決まる分布 $r$ と本当の分布 $p$ のずれ $D(p\Vert r)$」と「Kraft の和の余り $-\log K$」の 2 つに分かれることを示す。前者から次が分かる。
$\mathcal X$ は 2 個以上の元をもつとし、$q$ を $\mathcal X$ 上の確率分布で $q(x)>0$ とする。$\ell_x:=\lceil-\log_Dq(x)\rceil$ とおく($q(x)< 1$ なので $\ell_x\ge1$)。この長さの接頭符号 $c$ があり、本当の分布が $p$ で $H(p)$、$D(p\Vert q)$ が有限なら
$$
\frac{H(p)+D(p\Vert q)}{\log D}\le L(c)< \frac{H(p)+D(p\Vert q)}{\log D}+1
$$
である。
$\ell_x\ge-\log_Dq(x)$ から $D^{-\ell_x}\le q(x)$ で、$\sum_xD^{-\ell_x}\le1$ なので thm-kraft-main の 2 によりこの長さの接頭符号がある。$-\log_Dq(x)\le\ell_x< -\log_Dq(x)+1$ に $p(x)$ を掛けて足し、$-\sum_xp(x)\log q(x)=H(p)+D(p\Vert q)$ を使う。$\square$
$q=p$ とすると $H(p)/\log D\le L< H(p)/\log D+1$ で、エントロピー の定理「記号ごとの符号の平均の長さ」の $D$ 進版になる。分布を取り違えると、平均の長さはおよそ $D(p\Vert q)/\log D$ だけ増える。
$D=2$、$\mathcal X=\{a,b,c,d\}$、本当の分布を $p=(\frac12,\frac14,\frac18,\frac18)$ とする。一様分布 $q$ 用の長さ $(2,2,2,2)$ を使うと $L=2$ bit で、$H(p)=1.75$ bit、$D(p\Vert q)=0.25$ bit なので、cor-kraft-mismatch の下界にちょうど一致する。逆に、本当の分布が一様なのに $p$ 用の長さ $(1,2,3,3)$ を使うと $L=2.25$ bit で、$H=2$ bit、$D(q\Vert p)=0.25$ bit である。どちらも確率が 2 の冪なので切り上げの損がなく、損失はちょうど Kullback–Leibler 情報量になる。
$\mathcal X=\{1,2,3,\dots\}$、$D=2$ とし、$c(k):=0^{k-1}1$($0$ を $k-1$ 個並べて $1$ を付けた列)とする。どの符号語も最初の $1$ で終わるので接頭符号で、$K(c)=\sum_{k\ge1}2^{-k}=1$ である。しかし無限列 $000\cdots$ はどの符号語でも始まらない。符号語が無限個の場合には、prop-kraft-complete の (a) から (c) が導けない。分布 $p(k)=2^{-k}$ では $p(k)=2^{-\ell_k}$ なので、thm-kraft-redundancy の等号の場合で、$L=H(p)/\log2=2$ bit である。
正の整数 $n$ の 2 進表記(先頭は $1$)の桁数を $j+1$($j=\lfloor\log_2n\rfloor$)とし、$\gamma(n)$ を「$0$ を $j$ 個並べ、続けて $n$ の 2 進表記を書いた列」とする。$\gamma(1)=1$、$\gamma(2)=010$、$\gamma(3)=011$、$\gamma(4)=00100$ である。読む側は、最初の $1$ までの $0$ の個数 $j$ を数え、その $1$ から $j+1$ 文字を読めば $n$ が分かるので、$\gamma$ は接頭符号である。長さは $2j+1$ で、長さ $2j+1$ の符号語は $2^j$ 個あるので
$$
K(\gamma)=\sum_{j\ge0}2^j\cdot2^{-(2j+1)}=\sum_{j\ge0}2^{-(j+1)}=1
$$
である。$n$ を約 $2\log_2n$ 桁で書き、区切りの情報を自分で持っている。
(1):そのような符号があれば $\sum_n2^{-\ell_n}\ge2^{-C}\sum_n\frac1n=\infty$ となり、thm-kraft-main の 1 に反する。
(2):$n\ge1$ で $2^{-\ell_n}\le2^{-C}\,\frac1{n(\log_2(n+1))^2}$ である。$S:=\sum_{n\ge1}\frac1{n(\log_2(n+1))^2}$ は有限である。実際 $n=1$ の項は $1$ で、$n\ge2$ では $\frac1{n(\log_2(n+1))^2}\le\frac{(\log2)^2}{n(\log n)^2}$ で、$\sum_{n\ge2}\frac1{n(\log n)^2}$ は、$\frac1{t(\log t)^2}$ が $t\ge2$ で減少し $\int_2^\infty\frac{dt}{t(\log t)^2}=\frac1{\log2}< \infty$ なので収束する(積分判定)。$2^{-C}S\le1$ となる正の整数 $C$ をとれば $\sum_n2^{-\ell_n}\le1$ で、thm-kraft-main の 2 によりこの長さの接頭符号がある。$\square$
定義域が接頭自由なプログラムの集合では、prop-kraft-prefix と同じ理由で $\sum2^{-\lvert y\rvert}\le1$ が成り立つ。停止するプログラムについてのこの和が Chaitinの定数 で、同じ記事の接頭複雑性 $K(x)$(Kraft の和とは別の記号)についても $\sum_x2^{-K(x)}\le1$ となる(最短のプログラムは $x$ ごとに異なるので)。Kolmogorov複雑性 の理論で Kraft の不等式が繰り返し使われるのはこのためである。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 一意に復号できる(thm-kraft-main の 1) | 2 進の符号 $\{0,1,00\}$($00$ は「$0,0$」とも「$00$」とも読める) | $K=\frac54>1$ |
| 長さの和が $1$ 以下(thm-kraft-main の 2) | 2 進で長さ $(1,1,1)$(和 $\frac32$) | この長さの接頭符号はない(長さ $1$ の 2 進の列は 2 個しかない) |
| 符号を 2 の証明の手順で選ぶ | 2 進の符号 $\{0,01,10\}$(和 $1$) | 一意に復号できない:$010$ は $0\cdot10$ とも $01\cdot0$ とも読める。2 は長さの族について「ある符号」の存在を述べ、和が $1$ 以下の符号がどれも一意に復号できるとは言わない |
| 符号語が有限個(prop-kraft-complete) | 1 進符号(ex-kraft-unary) | $K=1$ だが $000\cdots$ はどの符号語でも始まらず、(a)⇒(c) が成り立たない |
| $K(c)=1$(prop-kraft-count) | 3 進の接頭符号 $\{0,1\}$ | 符号語は 2 個で、$2\not\equiv1\pmod2$ |
| 一意に復号できる(thm-kraft-redundancy) | 確率 $\frac12,\frac14,\frac14$ に 2 進の符号 $\{0,1,00\}$ | $L=1.25$ bit で $H=1.5$ bit を下回り、下界 $L\ge H/\log D$ が成り立たない |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する