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

この章では、現在のデータ圧縮・画像圧縮などで広く用いられている「LZ 法」について説明します。 前章・前々章に説明したハフマン符号化では、個々のデータを出現頻度に応じてハフマン符号に変換して圧縮を試みるというものでした。それに対して「LZ 法」では、あるデータ列に着目して、それが以前に出現したことがあるかをチェックし、すでに出現したことがあるのならば、そのデータ列を示す何らかの符号 ( 当然、データ列より短くなければなりません ) に置き換える処理を行うことにより圧縮を行っています。「LZ 法」にはいくつかの種類があり、その種類によってさらに名称が変わります。しかし、どの場合も先に述べた考え方が基本原理となります。 「LZ 法」は、「Abraham Lempel」と「Jacob Ziv」の共同開発によって 1977 年に誕生しました。Lempel と Ziv は、その翌年にも同じ原理を使っ