可変長符号
符号理論において、可変長符号(かへんちょうふごう、英語: variable-length code)とは、情報源の記号に対して割り当てる符号を可変長とする符号である。
可変長符号は、情報源が誤りなしで圧縮および解凍(可逆圧縮)され、依然として記号として読み取られることを可能にする。正しい符号戦略により、 独立同分布の情報源は、そのエントロピーの近い符号長でほぼ任意に圧縮される。これは、データ圧縮が大量のデータブロックに対してのみ可能な固定長符号とは対照的であり、可能性の合計の対数を超える圧縮は、有限の(おそらく任意に小さい)失敗確率でもたらされる。
良く知られた可変長符号には、ハフマン符号、Lempel-Ziv符号、算術符号などがある。
拡張が非特異である場合、符号が一意復号可能(uniquely decodable)であるという。符号が一意復号可能であるかどうかは、サーディナス=パターソンのアルゴリズム(英語版)によって決定することができる。
写像 M 3 = { a ↦ 0 , b ↦ 01 , c ↦ 011 } {\displaystyle M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}} は一意復号可能である。これは、0が符号語の先頭にしか現れないので、符号文字列中に0が現れたら、それが符号語の区切りであることが明白だからである。
ここで前節の符号 M 2 {\displaystyle M_{2}} を再度検討する。この符号(実例はにある)は一意復号可能ではない。符号文字列 011101110011 は、符号語 01110-1110-011 の列として解釈できるほか、符号語 011-1-110 の列としても解釈できるからである。よって、この符号文字列は cdb と babe の2通りに復号しうる。しかし、このような符号は、全て可能な情報源シンボルの集合が完全に既知で有限である場合、またはこの拡張の情報源要素が受け入れられるかどうかを決定する制限(たとえば正式な構文)がある場合に便利である。そのような制限は、同じシンボルに写像される可能性のある情報源シンボルのどれがこれらの制限の下で有効であるかをチェックすることによって、元のメッセージを復号することが可能になる。