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

圧縮アルゴリズムに対してより詳しく説明して下さい

  • 2010/12/21(火) 13:52:55

Q圧縮アルゴリズムに対してより詳しく説明して下さい。

A圧縮アルゴリズムは大きく分けてEntropy(エントロピー)コーディングとインデックスコーディングに分かれます。

まず二つの方式を比較してみます。
Entropy(エントロピー)コーディングとは
Aという文字が10回Bという文字が5回存在する場合
A文字にB文字より短いコードを割り当てて全体の長さを減らします。
例えばA:0 B:10のような形で割り当て出来ます。

インデックスコーディングは特定文字を辞書のインデックスのように表示する方式です。
例えばABCABCABCDEFDEFという文字列があるとします。
ABC:1,DEF:2に定義すると11122で表示されます。

Entropy(エントロピー)コーディングの体表的な例は
Huffman コーディングとArithmetic(Range)コーディングがあります。
インデックスコーディングはLZ77,LZW等があります。

その他にはBWTという文字ソートで圧縮する方式やMarkov Chainという予測方法で圧縮する方法もあります。






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

ファイルが圧縮される仕組みを教えて下さい

  • 2010/12/21(火) 13:49:24

Qファイルが圧縮される仕組みを教えて下さい。

Aデータ圧縮は圧縮アルゴリズムをによって行われます。

圧縮形式はデータの圧縮とは直接的な関係はありませんが、圧縮データを復元するとき原本と
同一な結果を出すための一連の情報を保存しているコンテナ(保存所)です。

ファイル名などの情報は圧縮形式に、ファイルの内容はアルゴリズムにより圧縮されてから
一つのかたまり情報になって圧縮形式に保存されます。
参考としてALZipのegg形式は圧縮データを複数のブロックに分けて保存しています。

圧縮形式は圧縮された情報を効率よく読み書きできるように構成されています。




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