可変長符号
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/08/04 04:40 UTC 版)
符号理論において、可変長符号（かへんちょうふごう、英語: variable-length code）とは、情報源の記号に対して割り当てる符号を可変長とする符号である。
可変長符号は、情報源が誤りなしで圧縮および解凍（可逆圧縮）され、依然として記号として読み取られることを可能にする。正しい符号戦略により、 独立同分布の情報源は、そのエントロピーの近い符号長でほぼ任意に圧縮される。これは、データ圧縮が大量のデータブロックに対してのみ可能な固定長符号とは対照的であり、可能性の合計の対数を超える圧縮は、有限の（おそらく任意に小さい）失敗確率でもたらされる。
良く知られた可変長符号には、ハフマン符号、Lempel-Ziv符号、算術符号などがある。
符号とその拡張
符号の拡張は、元の符号によって生成された対応する符号語を、情報源配列の各シンボルに対して連結することによって得られる、有限長情報源配列の有限長ビット列へのマッピングである。
形式言語理論の用語を使用すると、正確な数学的定義は次のようになる。
可変長符号
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/21 09:30 UTC 版)
詳細は「可変長符号」を参照 ここでは、情報源のそれぞれの文字をなんらかの辞書に従って符号語に符号化し、それらを連結して符号化された文字列を形成する符号を扱う。可変長符号は、元の文書でそれぞれの文字が出現する頻度が異なる場合に特に便利である。詳しくはコンパクト符号とエントロピー符号を参照。 接頭符号は語頭属性 (prefix property) を満たす符号である。接頭符号ではそれぞれの符号語が決して他の符号語の接頭部にならない。ハフマン符号は接頭符号を作る最も一般的なアルゴリズムであり、そのため接頭符号をハフマン符号と呼ぶこともあるが、ハフマン符号のアルゴリズムを使わずに接頭符号を作ることもできる。接頭符号の他の例として国際電話の国番号、ISBNのグループ番号と出版者番号、W-CDMAで使われている2次同期コード (SSC) などがある。 クラフトの不等式は、可変長符号が一意に復号可能であるための必要条件を与える。
※この「可変長符号」の解説は、「符号」の解説の一部です。
「可変長符号」を含む「符号」の記事については、「符号」の概要を参照ください。
- 可変長符号のページへのリンク
