前章の算術符号は元データ全体を１つの語句と考え、１つの可変長符号にしてしまおうという手法でしたが、その基本原理となっている「頻繁に出てくる語句を１つの符号で符号化すればデータを効率的に圧縮することができる」という原理に、より忠実に従った手法がLZ符号です。
このLZ符号はイスラエルの情報理論家であるJ.Zivと、計算機科学家のA.Lempelが1977年に共同開発した手法です。 LZ符号の正式名は「Ziv-Lempel符号」ですから本来は「ZL符号」と略すべきですが、ある著名なコンピュータ研究者が間違って「LZ符号」として紹介し、それが広がってしまったため現在でも慣習的にLZ符号と略されています。 またZivとLempelは同じような原理に基づいた別の手法を翌年にも開発したため、現在では1977年に開発された手法は「LZ77符号」と呼ばれ、翌年に開発された手法は「LZ78符号」と呼ばれています。
LZ符号とそれ以後に開発された同種の符号は、ハフマン符号や算術符号のような古典的な符号と異なり、元データに含まれる記号の出現率などの事前情報を必要とせず、しかも元データが長くなればなるほど最良の圧縮効果が期待できる万能な符号のため、「ユニバーサル符号(universal coding)」と呼ばれています。 このためこの符号の開発以後、古典的な符号はあまり利用されなくなります。 特に当時ようやく問題点が克服され、実用可能な各種の方法が開発されつつあった算術符号は、実際には利用されることはほとんどありませんでした。
LZ符号では「語(word)」または「節(phrase)」と呼ばれる可変長の記号列を、固定長または可変長の符号に変換します。 このように可変長の記号列を固定長または可変長の符号に変換するものを「VF符号(Variable-to-Fix code)」または「VV符号(Variable-to-Variable code)」といいます。
語句に符号を対応させる方法としてLZ符号では辞書を用いますので、「辞書に基づいた符号化(dictonary-based coding)」と呼ばれます。 辞書に基づいた符号化の中で一番単純な方法は、普通の辞書と同じように、あらかじめ語句を登録した辞書を用意し、元データに含まれる語句をその番号に変換する方法です。
例えば「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」について、
という辞書を作り、元データを語句の番号で符号化しますと、
| カエル | ピョコピョコ | ミ | ピョコピョコ | アワセテ | ピョコピョコ | ム | ピョコピョコ |
| ０ | １ | ２ | １ | ３ | １ | ４ | １ |
と、８×８ビット＝64ビットになり、ハフマン符号で符号化した場合の122ビットより短くすることができます。
この方法は元データを符号化する間、辞書の内容を更新しないので「静的辞書法(static dictionary method)」と呼ばれます。 しかしこの方法ですと最初に元データをスキャンして中に含まれる語句を調べ、それに基づいて辞書を作成する必要がありますし、作成した辞書を符号化後のデータに追加しておく必要があります。 それでは古典的な符号化法と同じ欠点を持つことになり、あまり効率的とは言えません。
そこでZivとLempelは辞書をあらかじめ作成せず、元データを読み込みながら辞書を作成・更新していくと同時に語句を符号化し、復号する時も、符号化されたデータを復号しながら復号用辞書を作成・更新していく画期的な方法を考え出しました。 それがLZ77符号化法です。 この方法ですと圧縮過程も復号過程も１パスで行える上、符号化されたデータに辞書を追加する必要がありませんから、高速かつ効率的です。 そして符号化・復号化と同時に辞書を作成・更新していきますので、「動的辞書法(adaptive dictionary method)」と呼ばれます。
LZ77符号では現在符号化を行っている記号を中心として、前後何記号かを保存するバッファを用意し、それを辞書として利用します。 例えば「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」の２番目の「ピョコピョコ」を符号化する場合、先頭から８文字分を参照部、その後ろ８文字分を符号化部とした、全体として16文字分のバッファを用意して次のように行います。
まず符号化する部分が符号化部の先頭になるように、元データの16文字分をバッファにコピーします。 そうしますと、符号化部の先頭から６文字分「ピョコピョコ」が参照部の２文字目から６文字分と一致することがわかります。
このように符号化部の先頭から始る文字列と一致する参照部中の文字列の中で、最も長いものを「最長一致系列」といいます。 そして「ピョコピョコア」までの７文字を［最長一致系列の参照部先頭からのオフセット値］［最長一致系列の記号数］［一致しない最初の記号」という形式を用いて、「16ア」と符号化します。
この時、［最長一致系列の参照部先頭からのオフセット値］は最高でも７ですから、３ビットあれば十分であり、［最長一致系列の記号数］も最高７文字ですから、３ビットあれば十分です。 したがって「16ア」という符号は３＋３＋８＝14ビットの固定長で表すことができ、元データの「ピョコピョコ(６×８＝48ビット)」を３分の１以下に圧縮することができます。
次にバッファ中の文字を符号化した文字数分左に移動します。 この場合は７文字分左に移動します。 これは16文字分の窓が元データの上を７文字分右にスライドすることに相当します。 このため、バッファのことを「スライド窓」とも呼びます。
この動きによって参照部の文字列は変化し、辞書の内容が更新されたことになります。 今度は、符号化部の先頭の「ワ」は参照部に一致する文字がありません。 このような場合は「00ワ」と１文字だけ符号化します。
このようにして符号化されたデータを復号する場合は、符号化時と同じスライド窓を用いて符号化の逆作業をします。 まず復号化した文字列の最後の８文字分を参照部にコピーし、符号化部を空にします。
復号化すべきデータは「16ア」で、これは「参照部のオフセット値１から６文字分が符号化部の先頭から６文字分と同じ記号で、その後にアが続く」という意味ですから、参照部の「ピョコピョコ」を符号化部の先頭にコピーし、その後に「ア」をコピーします。
次に、スライド窓を復号化した文字数分右にスライドします。
次に復号化すべきデータは「00ワ」で、これは「参照部には一致する文字がない」という意味ですから、符号化部の先頭に「ワ」をコピーします。 こうして「16ア00ワ」という符号から、元の「ピョコピョコアワ」を復元することができます。
以上のようにLZ77符号はスライド窓を動的辞書として利用し、可変長の記号列を固定長の符号に変換するVF符号の一種であり、元データを１パスで符号化・復号化することができます。 しかもスライド窓の参照部と符号化部の大きささえ決めておけば、符号化後のデータに余分なオーバーヘッドを追加する必要もありません。 このためハフマン符号や算術符号のような古典的な手法と比べますと、高速かつ効率的にデータを圧縮することが可能となります。
第3節へ
webmaster@snap-tck.com
Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)