接頭符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

日本語では他に語頭符号、英語では prefix-free codeprefix condition codecomma-free codeinstantaneous 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とする。

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


[編集]

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


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

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


参考文献[編集]


外部リンク[編集]