圧縮プログラミング

Question

ファイルを圧縮するプログラムと、その逆、圧縮されたファイルを元に戻すプログラムを作ってみたいと思い、いろいろ調べています。

中学の授業で、圧縮のプログラムは文字を縮めている！みたいな事を習いました。
・すもももももももものうち→すも[8]のうち
有名な例だと思います。

ですが、よくよく考えるとファイルはほとんどがバイナリ形式（？）と呼ばれるものですよね。
テキストファイルならこのような感じでいいと思いますが、exeや他の形式のデータは
どのようにしているのでしょうか。

ご存知の方がいらっしゃいましたら、ご教示ください。
よろしくお願いします。

ちなみに、言語はBASIC（Active Basic）を使用しています。
使えそうな関数などありましたら、それも教えていただけると幸いです。

siremono2496 · Accepted Answer

No3です。なかなか納得できないみたいですね。

> バイナリファイルではどのようにまとめるのか、ということです。

ですから、テキストだろうとバイナリだろうと同じですよ。テキストデータでは、

すも[8]

のように記述しますが、これは[8]というテキストがデータ中に存在しないときにしか使えない方法です。もし圧縮しようとしている文章内に初めからこのフレーズがあったら、後で圧縮したデータを見たときに、それは圧縮した結果なのか元々そういうテキストなのかが区別できません。なのでランレングス圧縮を行う場合は、確実にデータと繰り返し数を区別できるような工夫・約束が必要になります。それを考えるのが、この課題の肝となるでしょう。

バイナリデータでも、00～FF全ての値を使い切っていないデータ、例えば7Eがデータ中に出てこないと解っていれば、7Eをマークにしてその次を繰り返し数にできるわけです。これは、テキストの[8]と全く同じ考え方です。ただ、世の中にはなかなかそんなに都合の良いデータはないため、00～FF全ての値が含まれると考えておかねばならず、そうなったらデータ中に出てこない値の繰り返しを置いて、その次が繰り返し数になるといった工夫をすることになります。つまり、確実にデータかどうか区別でき、かつ圧縮されると期待できる長さのマークを考えなければなりません。このためランレングス圧縮は、どうしても効率が悪くなります。

マークが1バイトで繰り返し数に1バイトの最小構成の場合でも、データ＋マーク＋繰り返し数＝3バイト必要になるので、4つ以上繰り返すデータでなければ小さくなりません。これでは、よっぽど繰り返しが多い単純冗長なデータでなければ、圧縮できないことはすぐに解るでしょう。

ここで発想を転換して、データを1バイト＝8ビット単位ではなく、9ビット単位で扱うという作戦はわかりやすい手ではないでしょうか。

x bbbb bbbb

x：繰り返し数・データ判断フラグ
b：繰り返し数またはデータ

x=0：bは繰り返し数である
x=1：bはデータである

と考えるわけです。これならどんなバイナリ値でも関係なく、xが1か0かだけ見ていればいい。ただしデータを読み出す関数はたいてい1バイト単位になるので、この追加した1ビットだけデータがずれていくため、取り出し方には工夫が必要になります。

とまあ、こういう方法を考えるのが、圧縮の何たるかを考えると言うことになります。方法はいろいろあり得ると思うので、試行錯誤してみてください。

wormhole · Answer

簡単な例をあげるなら

・すもももももももものうち
→0す18も0の0う0ち

0: 次はデータ
1: 次は、その次々(データ)の繰り返し数

こんな感じです。

okwave0 · Answer

日本語でしたら以下の頁が参考になると思います
http://www.geocities.jp/m_hiroi/light/index.html
http://homepage3.nifty.com/wpage/

英語の資料
http://mattmahoney.net/dc/dce.html

圧縮に特化した掲示板で利用するならこちら
http://encode.ru/forum.php

nazotarou · Answer

使えそうな関数じゃないけど、ライブラリを使うと、手っ取り早く圧縮アプリは完成するねー。
圧縮方式とかはしらんけど、アプリはできる。
便利だねー。
http://www.csdinc.co.jp/archiver/lib/main.html

BASICで、使えるかはしらんけど。

bajutsu · Answer

例だから、分かりやすいようにひらがなでやっているけど
実際には、バイナリコードでやっているんですよ。

テキストだって、中身はバイナリ。
実際には、82B7というデータを、テキストエディタでは「す」と表示し、
82EBというデータを「も」と表示しているにすぎません。
（文字コード体系がSJISの場合）

質問者さんの場合、頭の中から、一旦「文字列」から離れて考える必要がありますね。

nora1962 · Answer

> ・すもももももももものうち→すも[8]のうち
これはランレングス法というものですね。
圧縮方式にはいろいろありますが、

http://www.bk1.jp/product/03325068
http://www.amazon.co.jp/LHA%E3%81%A8ZIP%E2%80%95%E5%9C%A7%E7%B8%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%C3%97%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E5%85%A5%E9%96%80-%E5%B1%B1%E5%B4%8E-%E6%95%8F/dp/4797324287

あたりを参考に。

wormhole · Answer

メジャーどころだとランレングス, スライド辞書, LZW, Huffman, 算術圧縮
ぐぐってみるなどして調べてみてください。

siremono2496 · Answer

それには圧縮ということがどういうものかを知らないと、とりかかれないですね。とっかかりとして、wikiの説明はまず読んでみてください。「・すもももももももものうち→すも[8]のうち」は、ランレングス圧縮として説明されています。これはバイナリにも通用する場合がありますよ。ファクスなんかで実際に使われているはず。

http://ja.wikipedia.org/wiki/%E5%9C%A7%E7%B8%AE%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB

> 使えそうな関数などありましたら、それも教えていただけると幸いです。

もし「この関数一発でできます」なんてのがあった場合、それを使ったら話がそこで終了しちゃいますから、これでは全く勉強になりません。なので繰り返しになりますけど、圧縮のアルゴリズムを勉強することが必要ですね。

DESTROY11 · Answer

一番単純なのは、データ＋個数という組にしてしまうことです。
すもももももももものうち→す[1]も[8]の[1]う[1]ち[1]。
となります。
この場合、繰り返しが多いデータなら圧縮が効きますが、バラバラの数値が多い場合は、かえって大きくなる弱点があります。

「辞書」を使う方式もあります。
すもももももももものうち
を解析し、よく出る繰り返しパターンを探し出します。
これのパターンにナンバーを振って、辞書とします。
[0]す
[1]も
[2]のうち
これで[0]1[1]8[2]1
この辞書ナンバーと繰り返し数をうまいこと組み合わせて1個の数字にしてしまうことも可能で、そうすると
[0*1][1*8][2*1]と3文字のデータにすることもできます。

ほかにもいろいろ方法はありますが、圧縮はそれだけで論文がかけるくらい奥の深い技術です。

LHS07 · Answer

吉崎栄泰　北海道社会事業協会帯広病院の医師が有名です。

http://www.ijinden.com/_c_20/Yoshizaki_Haruyasu.html

http://ja.wikipedia.org/wiki/LHA

圧縮プログラミング

No3です。

簡単な例をあげるなら

日本語でしたら以下の頁が参考になると思います

使えそうな関数じゃないけど、ライブラリを使うと、手っ取り早く圧縮アプリは完成するねー。

例だから、分かりやすいようにひらがなでやっているけど

> ・すもももももももものうち→すも[8]のうち

メジャーどころだとランレングス, スライド辞書, LZW, Huffman, 算術圧縮

それには圧縮ということがどういうものかを知らないと、とりかかれないですね。

一番単純なのは、データ＋個数という組にしてしまうことです。

吉崎栄泰 北海道社会事業協会帯広病院の医師が有名です。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

吉崎栄泰　北海道社会事業協会帯広病院の医師が有名です。