のぴぴのメモ

自分用のLinuxとかの技術メモ

データ圧縮アルゴリズムを整理してみた

データ圧縮(可逆圧縮)方式についてまとめました。

まとめ

  • 可逆圧縮の実用的アルゴリズムのほとんどは、LZ法を元にしている
  • LZは、ジェイコブ・ジヴ(Jacob Ziv)とエイブラハム・レンペル(Abraham Lempel)が開発した圧縮アルゴリズム
  • LZ法は、LZ77と、LZ78の2種類があり、それぞれ圧縮の符号方式が異なる。LZ77はsliding-window手法、LZ78はdictionaryによる符号化をする。
  • LZ77、LZ78は基礎的なアルゴリズムであり、実際に利用されるのはLZ77/78をベースに改良した実用的なアルゴリズムが利用されている。
  • 実用的なアルゴリズムの例としては、LZ77から派生した、LZSS(ARA、LZH)やDEFLATE(zip、gzip)、LZ78から派生した、LZW(GIFTIFF)などがある。

f:id:nopipi:20151209002040p:plain