【第6章　LZ78符号化(Ziv-Lempel coding,1978)】

6.1 LZ77符号の問題点とLZ78符号の開発

LZ77符号は元データに含まれる記号の出現率などの事前情報を必要とせず、しかも圧縮効果の高い画期的な手法ですが、それでもまだ少しだけ問題点があります。 それはスライド窓中の記号列を辞書として利用するため、符号化する記号の直前の記号列しか参照できないという点です。 符号化が進むにつれて最初の方の語句はスライド窓から出て行ってしまうので、最初に出現した語句と同じ語句が後ろの方にある場合は効率的に符号化できません。 もちろん、スライド窓を長くすれば多くの語句を参照することができますが、スライド窓を長くしますと、最長一致系列のオフセット値を表すために多くのビット数が必要となり、圧縮効率が悪くなってしまう上に、最長一致系列を探すのに多くの時間が必要となり、圧縮時間も長くなってしまいます。

そこでこの問題点を解決するために、LZ77符号を発表した翌年にZivとLempelが開発した手法が「LZ78符号」です。 LZ78符号はLZ77符号を改良した手法と言うよりも、LZ77符号とは似て非なる別の手法と言った方が適切で、LZ77符号の問題点を解決しただけでなく、圧縮／展開が速くてプログラム化が容易という優れた特徴を持っているため、現在のところ最も一般的な圧縮手法となっています。

6.2 LZ78符号の原理

LZ78符号はスライド辞書を使わず、語句とその参照番号を登録する辞書を用意し、新しい語句が出てきた場合はそれを辞書に登録し、すでに辞書にある語句の場合はその参照番号を用いて符号化します。 例として「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」を符号化すると次のようになります。

まず最初に空の辞書を用意します。

次に最初の記号「カ」から始る記号列と最長一致する語句を辞書から探しますが、辞書はまだ空ですから一致する語句はありません。 一致する語句が辞書にない場合は、符号として参照番号０とその語句自体を出力し、同時にそれを辞書に登録します。 したがってこの場合は「0カ」と符号化し、同時に「カ」を参照番号１として辞書に登録します。 ただし最初の記号は必ず辞書にないので、最初だけは参照番号０を省略して「カ」だけを出力します。

同様に「エルピョコ」までは辞書に一致する記号がありませんから、「0エ」、「0ル」、「0ピ」、「0ョ」、「0コ」を出力し、同時にこれらの記号を辞書に登録します。

次の記号「ピ」は辞書の４番目にありますから、その参照番号４と次の記号「ョ」を「4ョ」と符号化して出力し、同時に「ピョ」を新しい語句として辞書に登録します。

同様の操作を最後まで繰り返しますと、最終的な辞書と符号は次のようになります。

こうして作成した辞書には、最初の方に出てきた語句も最後の方に出てきた語句も全て登録されていますので、スライド辞書のように一部の語句しか参照できないということはなく、元データが長くても効率的に符号化することができます。 しかも最長一致系列を探す場合、LZ77符号では毎回スライド窓全体を探すため符号化に時間がかかりますが、LZ78符号の場合は辞書に登録された語句だけを探せばよいので符号化時間が短くなります。

参照番号を符号化する場合、辞書に登録された語句の数が１個なら１ビットで符号化することができ、３個以内なら２ビット、７個以内なら３ビットで符号化することができます。 つまり辞書に登録された語句の数がｎ＝(2^p−1)個以内ならば、参照番号をｐビットで符号化することができるわけです。

また辞書に登録される語句は符号を１つ出力するたびに１つずつ増えますから、参照番号を符号化する場合はビット数を規則的に増やすことが可能です。 ただし辞書に際限無く語句を登録しますと非常に多くのメモリが必要ですし、番号を符号化するのに必要なビット数が多くなって圧縮効率が落ちますので、登録語句がある程度の数になったら、新しい語句を登録するのを止めて辞書を固定するか、あるいは辞書をクリアして新たに作り直します。 したがってVF符号であるLZ77符号とは異なり、LZ78符号は可変長符号を可変長符号に変換するVV符号となります。

符号化されたデータを復号するには、次のようにします。 符号化と同様、まず最初に空の辞書を用意します。

次に、符号化されたデータ「カ0エ0ル0ピ0ョ0コ4ョ6ミ7コ9ア0ワ0セ0テ9ピ5コ0ム14ョ6」から最初の符号「カ」を読み込みます。 最初の記号は必ず新しい記号ですから、記号「カ」をそのまま出力し、同時にそれを辞書に登録します。

同様に、「0エ0ル0ピ0ョ0コ」までは新しい記号ですから、「エルピョコ」をそのまま出力し、同時にこれらの記号を辞書に登録します。

次の「4ョ」は、辞書の４番目の語句に「ョ」が続いているということですから、５番目の記号「ピ」と「ョ」を出力し、同時に「ピョ」を新しい語句として辞書に登録します。

同様の操作を最後まで繰り返しますと、最終的な復号データと辞書は次のようになり、符号化時と全く同じ辞書が復元されます。

以上のように、LZ78符号では辞書に登録できる最大語句数と、辞書が満杯になった時の更新方法さえ決めておけば、LZ77符号と同様に符号化後のデータにオーバーヘッドを追加する必要はありません。

またこの手法では符号化も復号化も原理的に同じような手順で行いますので、どちらもあまり変わらない速さで行うことができます。 それに対してLZ77符号では符号化には時間がかかりますが、復号化はスライド窓中の記号列をコピーするだけですので、LZ78符号よりも高速に行うことができます。 したがって、これらの特徴を生かして２種類の手法を使い分けると効率的です。

最終更新日：2001年7月2日 　第5章へ 第3節へ

　webmaster@snap-tck.com 　Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)