接頭符号のソースを表示

'''接頭符号'''（せっとうふごう、{{lang-en-short|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,&nbsp;100,&nbsp;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」などとする事で瞬時符号に変換することもできるが、
カンマを何らかの方法で符号化する必要があるため、符号化後の長さが長くなってしまうという欠点がある。

<!--
内容的には上に書き直したものと重複するが、リンクを保存する為、コメントとして残しておく。

各符号語の後ろに特別なシンボル（カンマ）を付与する符号もある。カンマは通常のデータには決して出現しない<ref>[http://www.imperial.ac.uk/research/hep/group/theses/JJones.pdf "Development of Trigger and Control Systems for CMS"] by J. A. Jones: "Synchronisation" p. 70</ref>。これは、通常の文章に出現する読点に似ている。全ての符号語にカンマが付与され、カンマがそれ以外の位置に出現しないなら、その符号は接頭符号と同等である（可変長符号で、先頭から曖昧さなく復号可能）。
--><!--
以下、意味不明な為、一旦コメントアウト。

各符号語が全て同じ長さの符号を固定長符号と呼ぶ。

例えば、[[ISO/IEC 8859]]-15 の文字コードは常に8ビットである。[[UTF-32|UTF-32/UCS-4]] の文字コードは常に32ビットである。[[Asynchronous Transfer Mode|ATM]]パケットは常に424ビットである。

固定長符号では接頭部という概念は意味を持たない（符号語の区切りは中身に依存しないため）。しかし、一部の符号語が他の符号語よりも出現確率が高い場合、固定長符号では効率が不十分である。
-->

== 例 ==

接頭符号を構築する技法には、[[ハフマン符号]]や[[シャノン符号化]]がある。他にも[[ユニバーサル符号]]があり、以下のような具体的な符号が存在する。
* [[アルファ符号]]
* [[ガンマ符号]]
* [[デルタ符号]]
* [[オメガ符号]]
* [[ゴロム符号]]
* {{仮リンク|フィボナッチ符号|en|Fibonacci_coding}}
* {{仮リンク|レーベンシュタイン符号|en|Levenshtein_coding}}


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

* [[国際電話番号の一覧|国際電話の国番号]]
* [[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, "[http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf A method for the construction of minimum-redundancy codes]" (PDF), Proceedings of the I.R.E., Sept. 1952, pp.&nbsp;1098-1102 （ハフマンのオリジナル論文）
*[https://web.archive.org/web/20070220234037/http://www.huffmancoding.com/david/scientific.html 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&ndash;392.
<!--
== 脚注 ==

<references/>
-->

== 外部リンク ==
*[http://plus.maths.org/issue10/features/infotheory/index.html Codes, trees and the prefix property] by Kona Macphee

{{DEFAULTSORT:せつとうふこう}}

[[Category:符号理論]]
[[Category:データ圧縮]]
[[Category:数学に関する記事]]