|
接頭符号（）は、語頭属性（prefix property）を満たす符号の事で、通常可変長符号である。主にデータ圧縮に使われる。接頭符号の例として可変長ハフマン符号がある。 日本語では他に語頭符号、英語では ''prefix-free code''、''prefix condition code''、''comma-free code''、''instantaneous code''（日本語では瞬時復号可能符号）などとも呼ばれる。ハフマン符号は接頭符号を生成する数あるアルゴリズムの1つに過ぎないが、ハフマンのアルゴリズムを使わずに生成した接頭符号も「ハフマン符号」と呼ぶことがある。 接頭符号はエントロピー符号の一種で、従って可逆圧縮である。 またクラフトの不等式は、接頭符号として可能な符号語の長さの特性を示している。 == 接頭符号の定義とその意義 == 符号が語頭属性を満たすとは、任意の符号語が他のいかなる符号語の接頭部にもなっていないという属性である。ここで符号語の接頭部とはあるを用いての形にかける語の事である。語頭属性を満たす符号を接頭符号という。 例えば、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とする。 以上で分かるように、接頭符号の復号計算は、符号語の長さの線形時間である為、効率的である。また復号計算アルゴリズムはオートマトンで記述できるほど単純である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「接頭符号」の詳細全文を読む スポンサード リンク
|