接頭符号...

接頭符号

接頭符号（英: Prefix code）は、符号の一種で、通常可変長符号であり、語頭属性（prefix property）がある。語頭属性とは、全ての符号語が他の符号語の接頭部になっていないという属性である。例えば、{0, 10, 11} という符号語からなる符号は、語頭属性を持つ。{0, 1, 10, 11} という符号語からなる符号は語頭属性を持たない（"1" が "10" と "11" の接頭部になっている）。

日本語では他に語頭符号、英語では prefix-free code、prefix condition code、comma-free code、instantaneous code（日本語では瞬時復号可能符号）などとも呼ばれる。ハフマン符号は接頭符号を生成する数あるアルゴリズムの1つに過ぎないが、ハフマンのアルゴリズムを使わずに生成した接頭符号も「ハフマン符号」と呼ぶことがある。

接頭符号を使うと、メッセージは符号語を連結した並びとして転送でき、メッセージ内の符号語を区切るマーカーは不要である。受信側での復号は曖昧さがなく、先頭から順に符号語を切り出して復号していけばよい。これは語頭属性があるが故に可能となっていることで、例えば例に挙げた {0, 1, 10, 11} の場合、先頭に "1" があると、それが "1" という符号語なのか、それとも "10" なのか "11" なのか、決定できない。

可変長ハフマン符号、国際電話の国番号、ISBNのグループ記号と出版者記号、W-CDMAにおける2次同期コード (SSC) はいずれも接頭符号である。接頭符号は、可逆圧縮で使われるエントロピー符号の一種でもある。

接頭符号は誤り訂正符号ではない。実際には、メッセージはまず接頭符号で圧縮され、送信する前にさらに誤り訂正符号で符号化されることが多い。

接頭符号を構築する技法は、単純なものから極めて複雑なものまで様々である。

各符号語が全て同じ長さの符号を固定長符号と呼ぶ。例えば、ISO/IEC 8859-15 の文字コードは常に8ビットである。UTF-32/UCS-4 の文字コードは常に32ビットである。ATMパケットは常に424ビットである。固定長符号では接頭部という概念は意味を持たない（符号語の区切りは中身に依存しないため）。しかし、一部の符号語が他の符号語よりも出現確率が高い場合、固定長符号では効率が不十分である。

各符号語の後ろに特別なシンボル（カンマ）を付与する符号もある。カンマは通常のデータには決して出現しない^[1]。これは、通常の文章に出現する読点に似ている。全ての符号語にカンマが付与され、カンマがそれ以外の位置に出現しないなら、その符号は接頭符号と同等である（可変長符号で、先頭から曖昧さなく復号可能）。しかし、現代の通信システムでは、全ての符号は "1" と "0" の並びとして送信されるため、第3のシンボルを追加するのはコスト高につながるし、シンボルが3種類なのにそれを区切りにしか使わないのは非効率である。モールス符号はカンマ付きの可変長符号の代表例である。文字と文字の間は長めの間隔を開け、単語と単語の間はさらに長い間隔を開ける。それを人間が聴いて文字や単語の区切りを感じ取っている。同様に、フィボナッチ符号は "11" を各符号語の末尾のマークとしている。

ハフマン符号は、可変長接頭符号を構築するためのより洗練された技法である。ハフマン符号のアルゴリズムでは、各符号語の出現頻度を入力として、メッセージを符号化したときの長さが最小になるような（すなわち、出現する符号語の平均長が最小になるような）接頭符号を構築する。

クラフトの不等式は、接頭符号として可能な符号語の長さの特性を示している。