圧縮プログラミング

質問

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

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

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

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

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

回答No.10

noname#194317 · ベストアンサー

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ビットだけデータがずれていくため、取り出し方には工夫が必要になります。

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

お礼

遅くなって本当に申し訳ありません。
とても分かりやすく、参考になるご回答、本当にありがとうございます。

>例えば7Eがデータ中に出てこないと解っていれば、7Eをマークにしてその次を繰り返し数にできるわけです。
なるほど、これでつながりました。
後はどんな方法を使うか、それを模索していけばいいわけですね。
やはりこういうものはネットを探すだけではほしい情報に当たりにくいようです。

参考になりそうな本を探して、購入しようと思います。
ありがとうございました。

回答No.9

wormhole

簡単な例をあげるなら

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

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

こんな感じです。

回答No.8

okwave0

日本語でしたら以下の頁が参考になると思います
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

回答No.7

nazotarou

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

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

回答No.6

bajutsu

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

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

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

お礼

ご回答ありがとうございます。

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

書き方が悪く、申し訳ありません。
私が知りたかったのは、テキストファイルでは「すも[8]～」のようにまとめますが、
バイナリファイルではどのようにまとめるのか、ということです。

回答者様の例で行きますと、
82EB[個数]なのか、
82EB5B395D
のようにするのかということです。

ご存知でしたらご教示ください。
お願いします

回答No.5

nora1962

> ・すもももももももものうち→すも[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

あたりを参考に。

回答No.4

wormhole

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

回答No.3

noname#194317

それには圧縮ということがどういうものかを知らないと、とりかかれないですね。とっかかりとして、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

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

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

回答No.2

DESTROY11

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

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

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

お礼

ご回答ありがとうございます。
独学でプログラミングを勉強しており、いろいろ試作しているところなのでデータ＋個数を参考にさせていただきたいと思います。

ところで、上の例ですが、ファイルの中に本当に
（文字）[繰り返し字数]
と書き込んでいくのでしょうか。

編集はバイナリモードでファイルをオープンしてやっていこうとしているのですが、
たとえば
FF[16]
のように書き込むのでしょうか。
それとも[16]も文字コードで書き込むのでしょうか。

本当に良くわかっていなくて申し訳ないです。
よろしければご教示ください。

回答No.1

LHS07

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

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

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