ZIP,RAR等はどのようなアルゴリズムを使用しているのですか

  • 2010/12/21(火) 13:54:13

Q では、ZIP,RAR等はどのようなアルゴリズムを使用しているのですか?

A ZIPがHuffmanアルゴリズムを使用していると認識している方々もありますが、
ZIPはDEFLATEというアルゴリズムを使用します。

Q DEFLATEアルゴリズムは説明がなかったのですが、どこに属するアルゴリズムですか?

A 誤解の余地がある部分ですが、圧縮は特定の単一アルゴリズムだけを使うのではないです。
基本的には上記の「Entropy(エントロピー)コーディング+インデックスコーディング+α」の形で
二つ以上のアルゴリズムを組み合わせて一つの圧縮アルゴリズムが生まれます。

DEFLATEの場合はLZ77+ Huffmanになります。
インデックスコーディングとEntropy(エントロピー)コーディングの組合せです。

例えばインデックスコーディングを利用してABCABCABCDEFDEFという文字列を11122にエンコードしてから
1が2より多く存在するので、Entropy(エントロピー)コーディングを利用して1に2より小さいコードを割り当てして圧縮します。

BZIP2ではRLE(Run Length Encoding) + BWT + Huffmanを使用します。
RLE + BWがインデックスコーディングと類似な効果を持っていると理解して下さい。

7Zipで使用するLZMAの場合は
LZ77 + Markov Chain + Rangeコーディングを使用します。

すなわち世の中で使われている圧縮アルゴリズムは、上記のような基本アルゴリズムの組合せで作られます。




ALZip(アルジップ)は、初心者から専門家まで簡単に使用でき、素早い圧縮速度と便利な分割圧縮をサポートしている統合圧縮管理プログラムとしてPCユーザーの必需品ですhttp://www.altools.jp/product/alzip/intro.aspx

この記事に対するトラックバック

この記事のトラックバックURL

-

管理人の承認後に表示されます

  • From: |
  • 2011/02/25(金) 22:01:39

-

管理人の承認後に表示されます

  • From: |
  • 2012/07/12(木) 22:16:44

この記事に対するコメント

承認待ちコメント

このコメントは管理者の承認待ちです

  • 投稿者: -
  • 2011/02/23(水) 10:36:16
  • [編集]

この記事にコメントする

管理者にだけ表示を許可する