接頭符号

接頭符号（英: Prefix code）は、語頭属性（prefix property）を満たす符号の事で、通常可変長符号である。主にデータ圧縮に使われる。接頭符号の例として可変長ハフマン符号がある。

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

接頭符号はエントロピー符号の一種で、従って可逆圧縮である。 またクラフトの不等式は、接頭符号として可能な符号語の長さの特性を示している。

接頭符号の定義とその意義

符号が語頭属性を満たすとは、任意の符号語が他のいかなる符号語の接頭部にもなっていないという属性である。ここで符号語$s_1\ldots s_n$の接頭部とはある$l \le n$を用いて$s_1\ldots s_{\ell}$の形にかける語の事である。語頭属性を満たす符号を接頭符号という。

例えば、00、1000、11という符号語からなる符号は、語頭属性を持つが、一方00、1000、10 という符号語からなる符号は語頭属性を持たない。（"10" が "1000"の接頭部になっている為）。

語頭属性のない符号を使って複数文字からなる文章を符号化すると、符号語から元の文書を一意に複号できなくなってしまう場合がある。 たとえば文字a,b,cをそれぞれ00, 1000, 10に符号化した場合、「ba」、「caa」のいずれも「100000」に対応してしまう為、符号語「100000」から元の文書を復元するのは不可能になってしまう。

このような符号であっても、語の切れ目にカンマをいれて「1000,00」などとする事で原理的にはもとの文書を特定できるが、この場合カンマ自身もなんらかの方法で数値に符号化する必要がある為、この解決方法は常に簡単というわけではない。

以上のような問題が生じるのは、「1000」がアルファベット「b」の符号語である。にもかかわらず、「1000」の接頭部である「10」が別のアルファベット「a」の符号語であるからである。これが原因で「1000…」ではじまる符号語に対応する文書の最初の文字が「b」であるのか「a」であるのかがわからなくなってしまうのである。

一方接頭符号の場合は、アルファベットの符号語が別のアルファベットの符号語になっている事はないので、このような問題は生じない。

実際、アルファベットの符号語の集合をWとするとき、接頭符号の場合は以下の方法で一意に複号できる。

• 符号語Xを入力として受け取る
• While(X≠空列)
  • Xの接頭部がwになっているようなw∈Wを見つける。
  • wに対応するアルファベットを出力。
  • Xの先頭からwを取り去ったものを新しくXとする。

以上で分かるように、接頭符号の復号計算は、符号語の長さの線形時間である為、効率的である。また復号計算アルゴリズムはオートマトンで記述できるほど単純である。

例

接頭符号を構築する技法には、ハフマン符号やシャノン符号化がある。他にもユニバーサル符号があり、以下のような具体的な符号が存在する。

• アルファ符号
• ガンマ符号
• デルタ符号
• オメガ符号
• ゴロム符号
• フィボナッチ符号
• レーベンシュタイン符号

接頭符号が実応用上使われている例として、以下のものがある。

• 国際電話の国番号
• ISBNのグループ番号と出版者番号
• W-CDMAで使われている2次同期コード (SSC)
• Gコード
• Unicode文字を符号化するUTF-8エンコード体系

接頭符号は一般には誤り訂正符号ではないので、接頭符号で圧縮した後、誤り訂正符号で符号化した上で送信する事が多い。

参考文献

• P. Elias, Universal codeword sets and representations of integers, IEEE Trans. Inform. Theory 21 (2) (1975) 194-203.
• D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., Sept. 1952, pp. 1098-1102 （ハフマンのオリジナル論文）
• Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54-58 (Background story)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp.385–392.

外部リンク

• Codes, trees and the prefix property by Kona Macphee