可変長符号

符号理論において、可変長符号（かへんちょうふごう、英語: variable-length code）とは、情報源の記号に対して割り当てる符号を可変長とする符号である。

可変長符号は、情報源が誤りなしで圧縮および解凍（可逆圧縮）され、依然として記号として読み取られることを可能にする。正しい符号戦略により、独立同分布の情報源は、そのエントロピーの近い符号長でほぼ任意に圧縮される。これは、データ圧縮が大量のデータブロックに対してのみ可能な固定長符号とは対照的であり、可能性の合計の対数を超える圧縮は、有限の（おそらく任意に小さい）失敗確率でもたらされる。

良く知られた可変長符号には、ハフマン符号、Lempel-Ziv符号、算術符号などがある。

符号とその拡張

符号の拡張は、元の符号によって生成された対応する符号語を、情報源配列の各シンボルに対して連結することによって得られる、有限長情報源配列の有限長ビット列へのマッピングである。

形式言語理論の用語を使用すると、正確な数学的定義は次のようになる。

$S$ と $T$ という2つの有限集合があり、 $S$ を情報源アルファベット、 $T$ を符号アルファベットとする。符号 $C:\,S\to T^{*}$ は、 $S$ の個々のシンボルが $T$ の元を使ったワード（シンボルの並び）に対応する全域写像であり、 $S^{*}$ から $T^{*}$ への準同型写像に拡張すれば、情報源アルファベットの並びを符号アルファベットの並びへと自然に写像できる。

可変長符号の分類

可変長符号は、一般性が低下する順に、非特異符号、一意復号可能な符号、接頭符号として厳密に入れ子状に分類することができる。接頭符号は常に一意復号可能であり、かつ非特異である。

非特異符号

情報源の各シンボルが異なる符号語に写像される場合、すなわち、情報源シンボルから符号語への写像が単射である場合、符号が非特異(non-singular)であるという。

例えば、写像 $M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}$ は、"a"と"b"の両方が同じビット列"0"に写像されるため、非特異ではない（特異(singular)である）。この写像を拡張すると、非可逆符号になる。このような特異符号は、情報の損失が許容可能である場合（音声や映像の圧縮など）には有用である。
写像 $M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}$ は非特異である。その拡張は可逆圧縮となり、一般的なデータ送信に有用である（ただし、この機能は必ずしも必要ではない）。非特異符号は情報源よりも必ずしも小さくなる必要はない。多くの応用において、符号長が長くなることが有用な場合もある。例えば、符号化や伝送時の誤りを検出・復旧するため、セキュリティアプリケーションでは検出不能な改竄から情報を保護するためなどである。

一意復号可能な符号

拡張が非特異である場合、符号が一意復号可能(uniquely decodable)であるという。符号が一意復号可能であるかどうかは、サーディナス＝パターソンのアルゴリズム（英語版）によって決定することができる。

写像 $M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}$ は一意復号可能である。これは、0が符号語の先頭にしか現れないので、符号文字列中に0が現れたら、それが符号語の区切りであることが明白だからである。
ここで前節の符号 $M_{2}$ を再度検討する。この符号（実例は^[1]にある）は一意復号可能ではない。符号文字列 011101110011 は、符号語 01110-1110-011 の列として解釈できるほか、符号語 011-1-110 の列としても解釈できるからである。よって、この符号文字列は cdb と babe の2通りに復号しうる。しかし、このような符号は、全て可能な情報源シンボルの集合が完全に既知で有限である場合、またはこの拡張の情報源要素が受け入れられるかどうかを決定する制限（たとえば正式な構文）がある場合に便利である。そのような制限は、同じシンボルに写像される可能性のある情報源シンボルのどれがこれらの制限の下で有効であるかをチェックすることによって、元のメッセージを復号することが可能になる。

接頭符号

→詳細は「接頭符号」を参照

写像内のターゲットビット列が、同じ写像内の異なる情報源シンボルのターゲットビット列の接頭部でない場合、その符号は接頭符号(prefix code)である。つまり、シンボルは、符号語全体が受信されると即時に復号することができる。そのため、接頭符号は瞬時復号可能符号とも呼ばれる。

前節の符号 $M_{3}$ は接頭符号ではない。符号文字列の"0"を受信した時点で、それが情報源シンボル a に対応する符号語なのか、情報源シンボル b や c に対応する符号語の接頭部なのかが判別できないからである。
接頭符号の例を以下に示す。

シンボル	符号語
a	0
b	10
c	110
d	111

符号化と復号の例

aabacdab → 00100110111010 → |0|0|10|0|110|111|0|10| → aabacdab

ブロック符号は接頭符号の特別な場合である。ブロック符号では、符号語が固定長である。ブロック符号は情報源符号化においてはそれほど有用ではないが、通信路符号化において誤り訂正符号として役立つ。

任意の大きな整数を一連のオクテットとして符号化する（すなわち、すべての符号語は8ビットの倍数である）可変長数値表現もまた、接頭符号の特別な場合である。

利点

可変長符号の利点は、あまり出現しない情報源シンボルには長い符号語を、よく出現する情報源シンボルには短い符号語を割り当てることができ、それによって符号長の期待値が短くなることである。前節の接頭符号の例で、(a, b, c, d) の出現確率が $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$ であったとき、情報源シンボルを表すのに必要な符号文字列の符号長の期待値は、次のようになる。

1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}

.

この情報源のエントロピーは1シンボル当たり1.7500ビットであるので、この符号は情報源を誤りなしで復号できるように情報源を可能な限り圧縮する。

脚注

^ Berstel et al. (2009), Example 2.3.1, p. 63

出典

Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001 Draft available online

[1] Berstel et al. (2009), Example 2.3.1, p. 63

[1]