簡単な圧縮アルゴリズム

Question

お世話になっております。

C言語ライクの言語で、インストーラーのようなものを作ってみようと思っているのですが、
圧縮アルゴリズムが理解できません。
簡単なアルゴリズムの名称と、簡単な処理の流れをご教授いただけないでしょうか。
また、実用的なアルゴリズムの名称も教えていただけたら幸いです。
これは、今後に向けて勉強するためです。

よろしくお願いいたします。

Answer 1

先の書込み以外では、
統合アーカイバプロジェクト
http://www.madobe.net/archiver/index.html
が、資料もまとまっている、古くからのサイトです。
各種圧縮形式の、コマンドプロンプト版～DLL版まで、存在します。
圧縮アルゴリズムの解説などもあります。
’
＞インストーラーのようなものを作ってみようと思っているのですが、
＞圧縮アルゴリズムが理解できません。
を、一緒くたに考えずに、
１．インストーラを、作成する。方法、方式を考える。
⇒インストーラの形式には、標準とされる物が、OS毎に存在します。
が、独自形式にしますか？
見栄えを除けば、BAT/CMD/PowerShell でも困らないのに、インストーラを作る理由は？
２．インストールファイルのパッケージングの過程で、圧縮も可能なので、
圧縮するだけですが、何か別な意図がありますか？
３．有償、無償のパッケージングソフトは使用した事がありますか？

Comments

[nnahito]

ご回答有難うございます。

まず、先に断っておきますが、私が今回インストーラーをつくろうと思ったのは、
自身の勉強のためです。
何故かすべてを否定されるような書き方をされて、少し残念に思います。

最終目標としては、インストーラーとして、データをexeの一つにファイルに纏め、
配布可能な形式にしたいと考えています。
ちなみに、その部分は完成しており、残りは圧縮のみとなっています。
既存のソフトウェアに頼る、その選択肢もありますが、やはりプログラマーとして、
実際に自分でアルゴリズムを知り、自身の手で書くことに意味があるのではないでしょうか。

Answer 2

C言語ライクの言語で、インストーラーのようなものを作ってみようと思っているのですが、

データ圧縮アルゴリズムを大別すると、1ビットもデータ欠損してはいけない「可逆圧縮(lossless)」と、映像・音声データのように多少の歪みを許容する「非可逆圧縮(lossy)」の2つに分類されます。目的が“インストーラー（につかえるアルゴリズム）”とのことですから、まずは「可逆圧縮」のアルゴリズムを当たるべきですね。

簡単なアルゴリズムの名称と、簡単な処理の流れをご教授いただけないでしょうか。
また、実用的なアルゴリズムの名称も教えていただけたら幸いです。

古典かつ簡単なところでは「ランレングス圧縮(Run-Length encoding)」や、「ハフマン符号(Huffman coding)」「算術符号(Arithmetic coding)」から調べるのがよいと思います。また、本質的な方法論が異なる「LZ77, LZ78アルゴリズム」あたりが入門向けでしょうか。前者はエントロピー符号(Entropy coding)に、後者は辞書式符号(Dictionary coding)に区分されます。

たとえば データ圧縮法概説 では、かなり丁寧にアルゴリズムを解説しています。

残念ながらいずれのアルゴリズムも”簡単”とは言えませんが、超概念的な説明だけしておきます。
-　エントロピー符号系：データの統計的な偏りを調べて、何度も登場する値には短い符号長（＝出力するビットの長さ）を、あまり出てこない値には長い符号長を割り当てる。
-　辞書式符号系：データ自身を”辞書”つまり値並びのカタログとみなして、既出の値並びと一致したらそれを指す短いインデクス値を、新出の値並びならばそのまま出力する。

いずれも数学的な考え方（情報理論）に基づいたアルゴリズムなので、既に実装されているコードだけ追いかけても、アルゴリズムの本質を理解するのは困難かと思います。結果的には、基礎的な理論から学習したほうが近道かもしれません。単に利用したいだけならば、既存ライブラリの活用を強くお勧めします。

Answer 3

参考情報をいくつか紹介します。
(web 上で "データ 圧縮" で検索すれば、たくさんの情報がヒットします。)

• ウィキペディア データ圧縮 http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%BC%E3%82%BF%E5%9C%A7%E7%B8%AE

• 『世界でもっとも強力な9のアルゴリズム』 データ圧縮（第7章） http://gekkan.bunshun.jp/articles/-/504

• コーディングに役立つ！ アルゴリズムの基本 データ量を操る圧縮／展開を究めよう http://www.atmarkit.co.jp/ait/articles/0903/04/news116.html

• zlib の使い方 http://s-yata.jp/docs/zlib/

...
zlib は圧縮アルゴリズムの一種である Deflate のライブラリであり，C#, Haskell, Java, Perl, Python, Ruby など，主要なプログラミング言語では，軒並み使えるように整備されています．圧縮・伸長が高速なこともあり，ディスク領域の有効利用や通信量の削減を目的として，zlib は気軽に利用できます．本記事は，C 言語から zlib を利用する方法の解説になっています．
...

Comments

[nnahito]

ご回答有難うございます。
もちろん検索しなかったわけではなく、検索し、様々なものを見た上で、
学習し易いものはどれかを知りたくて質問させて頂いております。

[katoy]

どんなページの内容の以上のものを欲しているのかが、質問文にあれば、そのようページを紹介することができたかもしれません。
そのような情報がないので、基礎・導入的なページを紹介しました。
データ圧縮は幅も深さもあるトピックです。

[nnahito]

返信有難うございます．
私も，少し質問の内容を端折り過ぎたと反省しております．
申し訳ありません．

Answer 4

• ＬＨＡとＺＩＰ　圧縮アルゴリズム×プログラミング入門

発刊当時に読みましたが、これの「アルゴリズム編」は圧縮アルゴリズムに関して初歩から分かりやすく書いていてくれたはずです。一読されてはいかがでしょうか。

Comments

[nnahito]

ご回答有難うございます．
検討させていただきます