接頭符号の場合の証明

ウィキペディア小見出し辞書

接頭符号の場合の証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/05/01 12:28 UTC 版)

「クラフトの不等式」の記事における「接頭符号の場合の証明」の解説

一意に復号可能な符号の典型的な特殊例として接頭符号がある。上述の定理を接頭符号の場合に対して証明する。 よく知られているように、接頭符号は次のような-分木で表す事ができる：各頂点には 個のアルファベットのうち1つが割り振られ、各符号語は根から葉までの経路で表される。 この木の各頂点に以下のルールで0以上1以下のラベルを再帰的に割り振る： 根には1を割り振る。 頂点iにxが割り振られているとき、iの各々の子にx/rを割り振る。 各頂点はr個以下の子しか持たないので、頂点iの子に割り振られたラベルの総和は頂点iに割り振られたラベル以下である。この事実を葉から根に向かって再帰的に適応する事で次の事実が分かる： 葉に割り振られたラベルの総和は根に割り振られたラベル（＝1）以下である。 前述したように、各符号語は根から葉までの経路に対応している。今グラフは木であるから、根から葉までの経路は、経路の終点である葉と一対一対応している。従って各符号語は木の葉と自然に対応付けられる。 ラベルの定義より、深さの頂点のラベルはである。木の作り方より符号語の長さは葉の深さに一致しているので、長さの符号語に対応する葉のラベルはである。 以上の議論より、符号語に対応する葉のラベルの総和は根に割り振られたラベル（＝1）以下である。よってクラフトの不等式が示せた。 また以上の議論から分かるように、頂点が丁度r個の子を持てば、その頂点の子に割り振られたラベルの総和は頂点iに割り振られたラベルに一致する。従って木が完全であるとき、葉に割り振られたラベルの総和は根に割り振られたラベル（＝1）に一致する。 木の作り方より、木が完全である必要十分条件は、符号が完全である事である。よってクラフトの不等式の等号成立条件は符号が完全である事である。 最後に定理の逆を示す。今自然数がクラフトの不等式を満たすとする。必要ならを付け加える事で、等号が成立していると仮定しても一般性を失わない。総和が1であるので、をなんらかの確率と解釈する事ができる。定理の逆は、i番目の符号語が生起する確率がであるとしたときのハフマン符号を作る事で証明できる。