圧縮アルゴリズムの種類

圧縮・伸張のアルゴリズムの種類を紹介します。

アルゴリズム / 戻る / トップページ

圧縮アルゴリズムの種類
圧縮アルゴリズムにはどのようなものがあるのか調べる必要があったため、 その時にまとめたものを公開します。 私はこの分野には門外漢なので、勘違いをしている可能性もあります。 ご了承ください。 詳細は、 データ圧縮の基礎 のページが参考になります。
　
モールス符号
　
コンピューターがなかった時代からある手法です。 いわゆるツー・トンで言葉を伝える方法です。
　
ハフマン法
　
各記号の生起確率が与えられたときに平均的な伝送時間が 最小となるような符号の構成法です。 バイナリの圧縮に向いています。
　
Lampel-Ziv 法 (LZ77, LZ78)
　
これから圧縮しようとする文字列が辞書 (過去に入力した文字列) にあるかどうか調べ、 もしあれば辞書の位置と一致長に置き換えて圧縮する方法です。 圧縮アルゴリズムの基本となるもので、 多くの圧縮アルゴリズムはこの方法を基盤としています。
　
LZ77 をハッシュで高速化する方法は米 Stac 社が特許を持ちます。
　
LZSS 法
　
LZ77 を改良した方法で、文字データの圧縮に向いています。 gzip はこの方法を更に改良したものです (?)。
　
アルゴリズムが簡単で、圧縮が遅く、展開が速い特徴を持ちます。 ゲームでは良く使われる方法です。
　
LZHUF 法
　
LHA で使われている方法です。 LZSS 法を適用したあとに、静的ハフマン法を適用しています。
　
国内での圧縮の第一人者、吉崎栄泰さんと 奥村晴彦さん が発明したことで有名です。
　
Inflate/Deflate 圧縮
　
PKZIP 2.x の deflate アルゴリズムです。 LHA の方法をハッシュで高速化したものです。 zip, jar, zlib, png もこの方法のようです (?)。
　
LZW (Lempel Ziv Welch) 圧縮アルゴリズム
　
GIF の圧縮、arc, pkarc に使用されています。 unix の compress はこの方法の改良版です。
　
UNISYS 社が特許を持っていますが、 2002 年 12 月をもって期限切れとなったかもしれません (?)。
　
Burrows-Wheeler 変換 (ブロック整列法)
　
今までにない独自の圧縮方法を取っています。 bzip2 がこの方法を使用しています。
　
作者は特許を取る気はないようです。

戻る