可変長符号

符号理論において、可変長符号（かへんちょうふごう、）とは、情報源の記号に対して割り当てる符号を可変長とする符号である。
可変長符号は、情報源が誤りなしで圧縮および解凍（可逆圧縮）され、依然として記号として読み取られることを可能にする。正しい符号戦略により、 独立同分布の情報源は、そのエントロピーの近い符号長でほぼ任意に圧縮される。これは、データ圧縮が大量のデータブロックに対してのみ可能な固定長符号とは対照的であり、可能性の合計の対数を超える圧縮は、有限の（おそらく任意に小さい）失敗確率でもたらされる。
良く知られた可変長符号には、ハフマン符号、Lempel-Ziv符号、算術符号などがある。
符号とその拡張.
符号の拡張は、元の符号によって生成された対応する符号語を、情報源配列の各シンボルに対して連結することによって得られる、有限長情報源配列の有限長ビット列へのマッピングである。 
形式言語理論の用語を使用すると、正確な数学的定義は次のようになる。
formula_1 と formula_2 という2つの有限集合があり、formula_1 を情報源アルファベット、formula_2 を符号アルファベットとする。符号 formula_5 は、formula_1 の個々のシンボルが formula_2 の元を使ったワード（シンボルの並び）に対応する全域写像であり、formula_8 から formula_9 への準同型写像に拡張すれば、情報源アルファベットの並びを符号アルファベットの並びへと自然に写像できる。
可変長符号の分類.
可変長符号は、一般性が低下する順に、非特異符号、一意復号可能な符号、接頭符号として厳密に入れ子状に分類することができる。接頭符号は常に一意復号可能であり、かつ非特異である。
非特異符号.
情報源の各シンボルが異なる符号語に写像される場合、すなわち、情報源シンボルから符号語への写像が単射である場合、符号が非特異(non-singular)であるという。
一意復号可能な符号.
拡張が非特異である場合、符号が一意復号可能(uniquely decodable)であるという。符号が一意復号可能であるかどうかは、によって決定することができる。
接頭符号.
写像内のターゲットビット列が、同じ写像内の異なる情報源シンボルのターゲットビット列の接頭部でない場合、その符号は接頭符号(prefix code)である。つまり、シンボルは、符号語全体が受信されると即時に復号することができる。そのため、接頭符号は瞬時復号可能符号とも呼ばれる。
ブロック符号は接頭符号の特別な場合である。ブロック符号では、符号語が固定長である。ブロック符号は情報源符号化においてはそれほど有用ではないが、通信路符号化において誤り訂正符号として役立つ。
任意の大きな整数を一連のオクテットとして符号化する（すなわち、すべての符号語は8ビットの倍数である）可変長数値表現もまた、接頭符号の特別な場合である。
利点.
可変長符号の利点は、あまり出現しない情報源シンボルには長い符号語を、よく出現する情報源シンボルには短い符号語を割り当てることができ、それによって符号長の期待値が短くなることである。前節の接頭符号の例で、(a, b, c, d) の出現確率が formula_15 であったとき、情報源シンボルを表すのに必要な符号文字列の符号長の期待値は、次のようになる。
この情報源のエントロピーは1シンボル当たり1.7500ビットであるので、この符号は情報源を誤りなしで復号できるように情報源を可能な限り圧縮する。