LZ法再び - DO++

可逆データ圧縮としては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)で置き換えることで圧縮する方法です。データ

[inak0shi]

LZ圧縮の改善研究の紹介。わかりやすい解説。有用なリンクあり。

[otonasi_kaoru]

he-

[mitsuki_engawa]

LZ77改善の近況。

[hengsu]

真面目にやると、計算量は増えるが、飛躍的に圧縮出来るらしい。

[K-Ono]

奥村先生吉崎先生の時代が再び来る!?

[ockeghem]

面白い

[oooooooo]

奥村先生のフォロー待ち

[TAKESAKO]

おおお

[kkobayashi]

枯れた技術と思っていたが・・・。

[tsupo]

真面目に最長&最右一致を全過去の文脈から探すと圧縮率は非常に高くなる / 数文字スキップしたらもっと長いマッチングがあって全体を小さくできる可能性 / 最長&最右一致よりも更に数%圧縮率を向上可能

[hiromark]

追いかける価値はあるなあ。