接頭符号
接頭符号(せっとうふごう、英: Prefix code)は、語頭属性(prefix property)を満たす符号の事で、通常可変長符号である。主にデータ圧縮に使われる。接頭符号の例として可変長ハフマン符号がある。
日本語では他に語頭符号、英語では prefix-free code、prefix condition code、comma-free code、instantaneous code(日本語では瞬時復号可能符号)などとも呼ばれる。ハフマン符号は接頭符号を生成する数あるアルゴリズムの1つに過ぎないが、ハフマンのアルゴリズムを使わずに生成した接頭符号も「ハフマン符号」と呼ぶことがある。
接頭符号はエントロピー符号の一種で、従って可逆圧縮である。 またクラフトの不等式は、接頭符号として可能な符号語の長さの特性を示している。
以上のような不都合が生じるのは、文字「c」の符号語「10」が、文字「b」の符号語「100」の接頭部であるからである。
一方、接頭符号の場合は、ある文字の符号語が別の符号語の接頭部になっている事はないので、このような不都合は生じない。 実際、符号語の集合を W {\displaystyle W} とするとき、接頭符号の場合は以下の方法で復号できる。
符号化された文字列 X {\displaystyle X} を入力として受け取る
While( X ≠ {\displaystyle X\neq } 空列) X {\displaystyle X} の接頭部が w {\displaystyle w} になっているような w ∈ W {\displaystyle w\in W} を見つける。 符号語 w {\displaystyle w} に対応する文字を出力。 X {\displaystyle X} の先頭から w {\displaystyle w} を取り去ったものを新しく X {\displaystyle X} とする。
このように、符号語ごとに順次復号ができることから、接頭符号は「瞬時符号」とも呼ばれる。 接頭符号の復号計算は、入力の長さの線形時間であるため、効率的である。また復号計算アルゴリズムはオートマトンで記述できるほど単純である。
なお、語頭符号でなくても、符号語の切れ目にカンマをいれて「100,00」などとする事で瞬時符号に変換することもできるが、 カンマを何らかの方法で符号化する必要があるため、符号化後の長さが長くなってしまうという欠点がある。