可逆データ圧縮としてはgzipやlha, pngなどダントツで使われているLZ法(Lemple Ziv法)ですが、他のデータ圧縮法(BWT法、PPM法、CM法)に比べ圧縮率が低いということで研究の対象としてはあまり注目をあびていませんでした。ところが次の論文で真面目にやれば圧縮率は非常に高くなる可能性があり、BWT法とかそれを超える可能性があることが示されています。。 "On the bit-complexity of Lempel-Ziv compression", SODA 2009, P. Ferragina, et. al. [pdf] まず、LZ法についておさらいですが、基本的にはデータを前から順番に見ていったときに、既に出現した文字列がもう一度出現(マッチング)したら、その文字列を前回出現した(相対)位置と長さのペア(pos, len)で置き換えることで圧縮する方法です。データ
![LZ法再び - DO++](https://cdn-ak-scissors.b.st-hatena.com/image/square/a0aa051048cb3afda5716214159b2dba29aaa425/height=288;version=1;width=512/http%3A%2F%2Fhillbig.cocolog-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)