接頭符号の定義とその意義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/04 04:12 UTC 版)
「接頭符号」の記事における「接頭符号の定義とその意義」の解説
符号が語頭属性を満たすとは、任意の符号語が他のいかなる符号語の接頭部になっていないという属性である。ここで符号語 s 1 … s n {\displaystyle s_{1}\ldots s_{n}} の接頭部とは、ある l ≤ n {\displaystyle l\leq n} を用いて s 1 … s ℓ {\displaystyle s_{1}\ldots s_{\ell }} の形にかける語の事である。語頭属性を満たす符号を接頭符号という。 例えば、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」の接頭部であるからである。 一方、接頭符号の場合は、ある文字の符号語が別の符号語の接頭部になっている事はないので、このような不都合は生じない。実際、符号語の集合を W {\displaystyle W} とするとき、接頭符号の場合は以下の方法で復号できる。 符号化された文字列 X {\displaystyle X} を入力として受け取る While( X ≠ {\displaystyle X\neq } 空列) X {\displaystyle X} の接頭部が w {\displaystyle w} になっているような w ∈ W {\displaystyle w\in W} を見つける。 符号語 w {\displaystyle w} に対応する文字を出力。 X {\displaystyle X} の先頭から w {\displaystyle w} を取り去ったものを新しく X {\displaystyle X} とする。 このように、符号語ごとに順次復号ができることから、接頭符号は「瞬時符号」とも呼ばれる。接頭符号の復号計算は、入力の長さの線形時間であるため、効率的である。また復号計算アルゴリズムはオートマトンで記述できるほど単純である。 なお、語頭符号でなくても、符号語の切れ目にカンマをいれて「100,00」などとする事で瞬時符号に変換することもできるが、カンマを何らかの方法で符号化する必要があるため、符号化後の長さが長くなってしまうという欠点がある。
※この「接頭符号の定義とその意義」の解説は、「接頭符号」の解説の一部です。
「接頭符号の定義とその意義」を含む「接頭符号」の記事については、「接頭符号」の概要を参照ください。
- 接頭符号の定義とその意義のページへのリンク
