About: クラフトの不等式

クラフトの不等式（クラフトのふとうしき、英: Kraft's inequality）は、符号理論における不等式の1つで可変長符号が一意復号可能である為の必要条件を与える。等号成立条件は符号が完全である事である。クラフトの不等式は可変長符号が一意復号可能である為の十分条件ではないが、クラフトの不等式を満たす任意のパラメータに対し、そのパラメータを実現する一意復号可能な可変長符号の存在性が保証される。 計算機科学や情報理論で利用される接頭符号やトライ木で応用されている。 元々のクラフトの結果は接頭符号に対してのものだった。後にマクミランは任意の一意復号可能符号でも同様の不等式が成立することを示した。このためクラフト・マクミランの不等式とも呼ばれる。