接頭符号

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

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

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

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

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

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

語頭属性のない符号を使って複数文字からなる文章を符号化すると、符号化された文字列から元の文書を得ることが面倒な場合がある。 たとえば文字a,b,cをそれぞれ00, 100, 10に符号化した場合を考えてみよう。「baa...」で始まる文章は「1000000...」と符号化され、「caa...」で始まる文章は「100000...」と符号化される。「baa...」の場合は 1の後に0が偶数個連なり、「caa...」の場合は0が奇数個連なることに注意すれば、この符号も、かならず一意に復号することは可能である。しかし、初めの「1000...」を見ただけでは最初の文字がbであったのかcであったのかを決めることができないため、あまり好ましくない。

以上のような不都合が生じるのは、文字「c」の符号語「10」が、文字「b」の符号語「100」の接頭部であるからである。

一方、接頭符号の場合は、ある文字の符号語が別の符号語の接頭部になっている事はないので、このような不都合は生じない。 実際、符号語の集合を[math]W[/math]とするとき、接頭符号の場合は以下の方法で復号できる。

• 符号化された文字列[math]X[/math]を入力として受け取る
• While([math]X \ne [/math]空列)
  • [math]X[/math]の接頭部が[math]w[/math]になっているような[math]w\in W[/math]を見つける。
  • 符号語[math]w[/math]に対応する文字を出力。
  • [math]X[/math]の先頭から[math]w[/math]を取り去ったものを新しく[math]X[/math]とする。

このように、符号語ごとに順次復号ができることから、接頭符号は「瞬時符号」とも呼ばれる。 接頭符号の復号計算は、入力の長さの線形時間であるため、効率的である。また復号計算アルゴリズムはオートマトンで記述できるほど単純である。

なお、語頭符号でなくても、符号語の切れ目にカンマをいれて「100,00」などとする事で瞬時符号に変換することもできるが、 カンマを何らかの方法で符号化する必要があるため、符号化後の長さが長くなってしまうという欠点がある。

例

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

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

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

• 国際電話の国番号
• 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