データ圧縮プログラムについてざっくり学ぶ

 ゲームプログラムをしているとあんまり『圧縮』というものに触れる 機会がありません。  そして、触れた事があるとしたら恐らくその切っ掛けの殆どは『たまたま』 ではないかと推察します。(たまたまプログラムの雑誌に書かれてた、授業で たまたま圧縮が取り上げられた、等)  ここもその『たまたま』の1つとして、圧縮について書いてみたいと思います。
 ではまず、 RRRRRRABDDDDDGG  という文字列があったとします。  これに『ランレングス圧縮』という圧縮をかけると次のようなデータになります。 RR6ABDD5GG2  ここでは  同じ文字が2回以上続いたらその部分を [2回以上続いた文字][2回以上続いた文字][続いた数]  という情報に置き換える  というルールで圧縮をかけています。お陰で元の文字列より4文字短くなりました。 (ただ、2文字ピッタリの場合は逆に1文字分増えるという欠点もあります(汗))  復元する時は2回同じ文字が続いたらそれは「2文字以上続いていた から変換された」箇所なので、3文字目にある回数だけその文字を並べてやれば RRRRRRABDDDDDGG  という文字列に戻せます。  これだけで圧縮出来てしまうのです。割りと簡単ではないでしょうか?  此処では分かり易く文字で例えましたが、実際は数値で処理します。  例えば RRRRRRABDDDDDGG は数値で書くと '82' '82' '82' '82' '82' '82' '65' '66' '68' '68' '68' '68' '68' '71' '71'  (一つの ' ' が1バイト、82=R 65=A 66=B 68=D 71=G )  なので、ランレングス圧縮後は '82' '82' '6' '65' '66' '68' '68' '5' '71' '71' '2'  となります。数値も処理出来ると言う事はこの方法は画像データ等の バイナリデータでも使えるということです。  というわけで、一番基本的な圧縮について説明してみました。これがいわゆる圧縮 というヤツです。色々な法則を使って、元のデータを壊さずに、元のデータよりも 記憶に必要なデータ領域を少なくしてしまおうというわけです。 (JPEG等は元のデータを壊しますが・・・)  尚、ここで説明したランレングス圧縮では何回も同じ数値が続いていなければ 圧縮出来ないので、写真画像等の隣り合ったドットの色が同じ、なんてことは 殆ど無いデータは全然圧縮できません。しかも、先程ちょっと触れましたが 2回しか連続していない場合は圧縮するどころか逆に1バイト増えてしまいます。  ランレングス圧縮以外の基本的な圧縮方式にハフマン圧縮というのがあるの ですが、ランレングス圧縮よりも実現が大変な割には単体ではあんまり圧縮率が 高くありません。  ・・・・。  となるとやはり、実用可能なレベルの圧縮率を出すにはもっと複雑で実装が 大変なアルゴリズムを使わなくちゃいけないのか? などと思ってしまいそうですが (というか私は思っていましたが)、そうではありませんでした。  LZSS圧縮という圧縮方法があり、これが中々良い感じなのです。  LZSS圧縮とは Lempel という方と Ziv という方が1977年に 発案した圧縮方式LZ77(名前の頭と発案した年を取っているようです) を、1982年に Storer という方と Szymanski という方が改良を加えた 圧縮方式です。(『です』と言い切れるほど熟知している訳ではありませんが(汗))  この圧縮方式は理屈はランレングス圧縮と同じくらい単純なのに、 ランレングス圧縮に比べたら数段実用的な圧縮率が望めます。  例えば ABCDEFGABCDEFCDEFGH  という文字列があったとします。これにLZSS圧縮をかけると 次のようになります。 ABCDEFG[7,6][11,5]H  一つの [ ] は3文字分だと思ってください。  とすると ABCDEFGABCDEFCDEFGH = 19 文字 ABCDEFG[7,6][11,5]H = 14 文字  というわけで5文字分減りました。  この圧縮方式の理屈は  同じ文字(数値)の羅列が以前も出てきた場合は、何文字(何バイト)前から 何文字(何バイト)同じ文字(数値)が続いているか、という情報に置き換える。  というものです。  その情報に必要な文字数(バイト数)は3文字(3バイト)ですので、『何文字 (何バイト)同じ文字(数値)が続いているか』が、もし3文字以上だった場合は その分元のデータよりも小さくなるわけです。  つまり ABCDEFG[7,6][11,5]H  の [7,6] というのは元の文字列の7文字前から6文字同じ羅列がありますよ、 という事を指しているわけです。(同じく [11,5] は元の文字列の 11文字前 から5文字同じ羅列がありますよ、という意味です)  確認してみましょう ABCDEFGABCDEFCDEFGH  の中の[7,6]に置き換えられたところは ABCDEFG  の次の'A'の部分です。  [7,6]に従うと、丁度この'A'から7文字前から6文字分同じ文字列が続くと 言っています。 ABCDEF'G' 一文字前 ABCDE'F'G 二文字前 ABCD'E'FG 三文字前 ABC'D'EFG 四文字前 AB'C'DEFG 五文字前 A'B'CDEFG 六文字前 'A'BCDEFG 七文字前  確かに7文字前に同じ'A'がありました。ここから6文字同じだそうです。 ABCDEFGABCDEFCDEFGH の中の 'ABCDEF'G'ABCDEF'CDEFGH  ''で囲われたところ同士、確かに六文字同じです。  次に[11,5]を確認してみましょう。  これは[7,6]の直後に来ていますが、[7,6]の直後といえば ABCDEFGABCDEF  この直後の'C'の部分です。  [11,5]の通りならばここから11文字前から5文字分同じ文字列がある ということです。どうでしょう、11文字前といえば AB'C'DEFGABCDEF  確かに同じ'C'があります。ここから後の5文字分の CDEFG も確かに ABCDEFGABCDEF  の後の CDEFGH  と5文字分だけ合っています。  ところで、ランレングス圧縮の時は『同じ文字が2回続く』ことで圧縮 された情報かどうかを判別していましたが、LZSS圧縮ではどうやって 圧縮された情報かどうかを判別するのでしょうか?  これについては、一番登場回数が少ない文字を圧縮情報の識別子にして しまうという方法があります。(LZSS正規のものはちょっと面倒なので・・・)  先程の ABCDEFGABCDEFCDEFGH  でいうなら、H です。一回しか出てきません。  なので、  H が出てきたら、そのあとの1文字目を『何文字前からか?』の数値、 2文字目を『何文字同じか?』の数値と判断します。  で、H 自体だった場合は HH と2回続けます。ランレングス圧縮の 場合と逆です。(^^;  なので、 ABCDEFG[7,6][11,5]H   を [ ] で誤魔化さずに表現すると 'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' '7' '6' 'H' '11' '5' 'H' 'H'  となります。  (一つの '' が一バイト(0〜255まで表現可能))  数値で表現すると '65' '66' '67' '68' '69' '70' '71' '72' '7' '6' '72' '11' '5' '72' '72'  という数値列になります。(圧縮情報の前に 72=H があります ) (65=A 66=B 67=C 68=D 69=E 70=F 71=G 72=H )  これですと圧縮情報の印に選出された数値の登場回数分だけ無駄に データが増えてしまうことになりますが、私が試した限りではその せいで圧縮前のデータよりもサイズが大きくなってしまう、ということは ありませんでした。恐らく相当圧縮し難いデータで無い限りは逆にサイズが 増えてしまう、なんてことは無いと思います。(LZHやZIPなどの既に 圧縮されたデータをこの方法でさらに圧縮しようとすると増えるかもしれませんが)  因みに、どの文字を圧縮情報の印に使っているかは別に保存しておく 必要があります、でないと復元できないので。(^^;  というわけで、LZSS、お勧めです。 (とはいえ正規の方法を使わない時点で既に『LZSS風』ですが(汗))  ここで説明は終わりですが、やはり実際に動くプログラムを見てみないと しっくり来ない、という方もいると思います。なので、簡単なサンプル プログラムを用意しました。今の説明で抜けている部分は全てこちらに ありますので宜しければご覧になってみて下さい。 <<圧縮>> http://dxlib.o.oo7.jp/lecture/Press/LzssEncode.cpp // ソース http://dxlib.o.oo7.jp/lecture/Press/LzssEncode.exe // 実行可能ファイル(コンソールアプリケーション) <<解凍(展開)>> http://dxlib.o.oo7.jp/lecture/Press/LzssDecode.cpp // ソース http://dxlib.o.oo7.jp/lecture/Press/LzssDecode.exe // 実行可能ファイル(コンソールアプリケーション) (細部まで完全に説明し切っているわけではないので、不明な点があり ましたら掲示板の方にお書き込みください)  ソースは BCC でも VC でも『コンソールアプリケーション』として コンパイルできます。(Windows アプリケーションとしてはコンパイル出来ません)  圧縮ソフトにに圧縮したいファイルをドラッグ&ドロップすれば 拡張子が『lzs』になった圧縮ファイルが作成されます。  圧縮されたファイルを解凍ソフトにドラッグ&ドロップすれば 拡張子が『dec』になった元のファイルと同じ内容のファイルが 作成されます。  その他・・・ ・ 自然画やWAVファイルは殆ど圧縮できません。orz ・ 『もっと圧縮率を高くしたい』という方は、このソフトで圧縮した  ファイルに『ハフマン圧縮』または『レンジコーダー圧縮』というものを  掛けてみてください。さらに少しだけ圧縮することが出来ます。  (または『ブロックソーティング(Block Sorting)』や  『PPM (Prediction by Partial Matching) 』などを調べて見て下さい) ・ 複数のファイルを一つのファイルにする機能は『圧縮』ではなく  『アーカイブ』という機能ですので、このソフトでは一つのファイル  しか圧縮出来ません。(つまり LZH や ZIP 等は圧縮データ形式であると  同時にアーカイブデータ形式でもあるわけです)  あと、上記のソフトを使用して圧縮した画像データ、音声データを DXライブラリで読み込むサンプルもこちらに置いておきます。 http://dxlib.o.oo7.jp/lecture/Press/LzssDxSample.cpp // ソース http://dxlib.o.oo7.jp/lecture/Press/LzssDxSample.exe // 実行可能ファイルとデータファイル一式(普通の Win32 アプリケーション)  ソースのコンパイルには普通にDXライブラリのコンパイル環境が必要に なります。  今回お世話になったサイト [[やまざき@BinaryTechnology]] リンクについて何処にも書かれていなかったので google( http://www.google.co.jp/ )で検索してください。(^^; こちらのサイトの『データ圧縮の基礎』というページで圧縮の基礎が学べます。 [[M.Hiroi's Home Page]] http://www.geocities.jp/m_hiroi/index.html こちらのサイトには様々な圧縮方法について基礎から実用方法まで分かり易く説明されています。 ここの説明が要らない位です。(^^;  折角なのでハフマン圧縮についても間単に説明します。  ハフマン圧縮は 1952年に David A. Huffman という方が発案しました。 今から50年以上も前に作られた圧縮方法というのは驚きですね。(・・;;  では早速例を。  例えば次のような文字列があったとします ABEBCCBBDBCCACCCDECDE  これに、ハフマン圧縮をかけると上記の文字列が次のようになります 11110010110000100100110100001110001101010110101  これは2進数の数値列です。  驚いた方に謝ります、すいません。 // 2進数とデータサイズの説明(知らない方向け) ===============================  まず2進数は0、1と数えていき、2で桁が繰り上がり10になります。 『じゅう』ではなくて『いちぜろ』です。  3 は 11、4 はまた桁が繰り上がって 100 になります。 対応表 2進  10進 00000 0 00001 1 00010 2 00011 3 00100 4 00101 5 00110 6 00111 7 01000 8 01001 9 01010 10 01011 11 01100 12 01101 13 01110 14 01111 15 10000 16  で、よくC言語の解説書等には unsigned char (符号なし1バイト型) は 0から255まで表現できる、と書いてありますが、それは『1バイト』は 2進数8桁の情報のことを指していて、2進数8桁では最大で255までしか 表現できないからなのです。 2進   10進 11111111 255  というわけです。(これ以上1でも増えたら9桁になってしまう)  あと、よく512メガバイトとか120ギガバイトとか聞きますが、 その関係は 1バイトが1024個 = 1キロバイト (1KByte) 1キロバイトが1024個 = 1メガバイト (1MByte) 1メガバイトが1024個 = 1ギガバイト (1GByte)  ということになります。  1バイトで1文字表現できるので(日本語文字などは1文字2バイト必要) 1メガバイトあれば 1024 x 1024 = 1,048,576 = 104万8576文字も 記憶出来るということになります。(日本語文字なら52万4288文字)  ちなみに『ビット(bit)』という言葉も聞いたことがあるかもしれませんが、 1ビットというのは2進数1桁のことを指しています。なので2進数8桁 で1バイトである『バイト(byte)』という単位は、1バイトあたり8ビット ということになります。 01001010 = 2進数8桁 = 8ビット = 1バイト 01110000 11101011 = 2進数16桁 = 16ビット = 2バイト  というわけです。 // ================================================================  さて、先程の 11110010110000100100110100001110001101010110101  は、意味は分かりませんが、とりあえず2進数47桁です。 バイトに直すと 47÷8=5.875、つまり6バイト弱、 元の文字列が21文字(バイト)なのでかなり圧縮されて いることになります。  ではこの数値列の謎を解きましょう。  実は上記の0と1の数値列は元の ABEBCCBBDBCCACCCDECDE  の各文字を、次の2進数の数値列と文字との対応表を元に 変換したものなのです A = 111 B = 100 C = 0 D = 110 E = 101  試してみましょう。左端から見ていきます  11110010110000100100110100001110001101010110101 の最初の 111100 は最初の3ビット 111 の時点で対応表の A のに対応しています  元に戻した文字列:A  残り:10010110000100100110100001110001101010110101 次の 1001011 は最初の 100 の時点で対応表の B に  元に戻した文字列:AB  残り:10110000100100110100001110001101010110101 次の 1011000 は最初の 101 の時点で対応表の E に  元に戻した文字列:ABE  残り:10000100100110100001110001101010110101 次の 10000 は 100 の時点で B に  元に戻した文字列:ABEB  残り:00100100110100001110001101010110101 次の 00100 は 0 の時点で C に  元に戻した文字列:ABEBC  残り:0100100110100001110001101010110101 次の 0100100 も 0 が初めに来ている時点で C に  元に戻した文字列:ABEBCC  残り:100100110100001110001101010110101  まだ途中ですが、今のところこの手法で元の文字列に戻っていって います。これを最後までやるとちゃんと元の文字列に戻ります。  『成る程』と思われたかもしれません。  因みに各文字の出現数は以下の様になっています。 A = 2 B = 5 C = 8 D = 3 E = 3  C が一番出現数が多いです。  ハフマン圧縮の圧縮のカラクリは出現数が多いものほど短いビット数で 表現して、その合計ビット数を元のデータよりも小さくしてしまおう、 というものです。なので、圧縮対象のデータが全て均等に出現する 場合は全く圧縮できません。出現数に隔たりがあればあるほどより圧縮 出来るというわけです。  なお、今回は C だけが対応するビット列の長さが違いましたが、実際には 出現回数が多いものほどビット列が短くなり、出現回数が少ないもの ほどビット列が長くなります。ついでに出現するものの種類が多くなれば 全体的なビット列も長くなります。今回は5種類しかなかったので最高 3ビットになっているわけです。  では、この A = 111 B = 100 C = 0 D = 110 E = 101  表はどうやって作ればいいのでしょう?  例えば『0』一個で終わってしまう C がある時点で他に0から始まる 文字を表に加えることは出来ませんし、『101』で終わる E がある 時点で『10101』という対応コードを持つ文字を表に加えることも 出来ませんから、普通に考えると大変そうです。  ですがこれには簡単な方法で導きだすことが出来ます。  まず先程の  を、とりあえず分かり易くするために  出現数の小さい順に並べ直します。  次に、一番小さい数値二つを繋げて、繋いだ上に二つの出現数を足した 値を書き込みます。D と E は同じ数値ですが、同じ数値のデータが複数 あるばあいはどれを選んでも構いません。  同じ手順を繰り返します。ただし、繋いだ A と D はもう比較対象には 入れずに、代わりに A と D を繋いだ部分を比較対象に加えます。  この中で一番値が低いのは E の3です。次に低いのは A と D を足した 値5と B の5ですが、これも先程と同じようにどちらをつなげても構いません。(今回はBと繋げました)  そして同じように繋いだ上に E と B の出現数を足した値8を書き込み、 次は E と B の代わりに比較対照とします。  残ったのは A と D を繋いだ値5と E と B を繋いだ値8、あと C の 8です。また同じになってしまいましたが、今回もどちらでも良いので 今度は A と D を繋いだものと E と B を繋いだものを繋ぎました。  同じように上に足した値を書き込みます。  後は残ったものどうしを繋げるだけです。  次に繋いだ部分の左右に右に0、左に1を書き込みます。 0と1は左右逆でも構いません。  最後に天辺から各文字のところまで辿ります。  辿る途中で通過した分岐の数値を各文字の下に書き込みます。  すると、なんと、例の表 A = 111 B = 100 C = 0 D = 110 E = 101  の通りになりました。  というわけです。(^^;  なお、この表は  11110010110000100100110100001110001101010110101  からは連想することは出来ませんので、出来上がった表を別に保存 しておくか、1バイトで表現できる0から255までの数値の出現数を 別に保存しておくか、どちらかをする必要があります。  大体それらには1キロバイトほどの保存領域が必要になります ので(ちょっと面倒くさいことをすればもっと小さく出来ますが) 1キロバイト以下のデータをハフマン圧縮しようとしても、 どう足掻いても圧縮できないということになります。  ですが、1キロバイト以下のファイルというのはあんまり無いので、 大抵は小さくなるというわけです。  これで、圧縮と復元の理屈はわかったと思います。  後はどうやってC言語のプログラムにするかですが、その辺りは サンプルプログラムをご覧下さい。(^^; <<圧縮>> http://dxlib.o.oo7.jp/lecture/Press/HuffmanEncode.cpp // ソース http://dxlib.o.oo7.jp/lecture/Press/HuffmanEncode.exe // 実行可能ファイル(コンソールアプリケーション) <<解凍(展開)>> http://dxlib.o.oo7.jp/lecture/Press/HuffmanDecode.cpp // ソース http://dxlib.o.oo7.jp/lecture/Press/HuffmanDecode.exe // 実行可能ファイル(コンソールアプリケーション)  LZSS圧縮の時と同じようにこのソースは BCC でも VC でも『コンソール アプリケーション』としてコンパイルできます。(Windows アプリケーションとしては コンパイル出来ません)  圧縮ソフトにに圧縮したいファイルをドラッグ&ドロップすれば 拡張子が『huf』になった圧縮ファイルが作成されます。  圧縮されたファイルを解凍ソフトにドラッグ&ドロップすれば 拡張子が『dec』になった元のファイルと同じ内容のファイルが 作成されます。  というわけで、ざっくりとした圧縮の説明でした。(^^; // ビット演算の説明 ======================================================  ハフマン圧縮はバイト単位の処理ではなくビット単位の処理になるので、 ビット単位の処理をする方法を知らないといけません。  ので、ここで簡単なビット演算の方法を記述します。 ・シフト演算 『<<』 又は 『>>』   ビット単位で数値を左右に移動したい時に使います。   使用例:2ビット左にシフトする    // 2進数で 00110100 (10進数では 52 )    unsigned char A = 52 ;    // A <<= 2 ; と書くことも出来る    A = A << 2 ;    // A の値は2進数で 11010000(十進で 208) になる。(左に2ビット移動した)   注意:     11001111 を右に2ビットシフトして 00110011 になった後、左に2ビット    シフトすると 11001100 になる、つまりスクロールアウトしてしまった部分は    元に戻らず、スクロールインしてきたビットは必ず0で埋められます。 ・論理積演算(AND(アンド)演算)『&』   ビット単位である演算を行います。   法則は以下の計算を見て覚えて下さい。   11001111   10110101&   ---------   10000101   01101011   10010101&   ---------   00000001    要は『どちらも1じゃないと0になる』です。    これは特定のビットが0か1かを調べたり、特定のビット域だけを   抽出したりする時に使います。   使用例:変数 A の0ビット目が0か1かを判断する    // 2進数 01010101 ( 10進数では 85 )    unsigned char A = 85 ;    if( ( A & 1 ) == 0 )    {      // 0ビット目は 0    }    else    {      // 0ビット目は 1    }       // この例では判断式では A の0ビット目は 1 なので結果は『偽』になります ・論理和演算(OR(オア)演算) 『|』   論理積演算に似ていますが効果は逆といった感じです。   11001111   10110101|   ---------   11111111   01000011   10010101|   ---------   11010111   要は『どちらか1なら1になる』です。   特定のビットを1にしたいとき等に使用します。   使用例:変数 A の7ビット目(0から数える)を1にする    // 2進数 01110100 ( 10進数では 116 )    unsigned char A = 116 ;    // A |= 128 ; と書くことも出来る。因みに 128 は 2進数で 10000000    A = A | 128 ;    // 結果 A は 2進数で 11110100、10進数で 244 になる    ・排他的論理和演算(XOR(エックスオア?)演算) 『^』    今回のハフマン圧縮では使わない演算子です。   11001111   10110101^   ---------   01111010   01010011   10010101^   ---------   11000110    要は『片方だけ1なら1、どちらも0かどちらも1なら0』です。    偶に使います。 ・否定演算(NOT(ノット)演算) 『~』    ビットを全て反転します。2つの数値を演算するのではなく、単体で   使用します。これも今回のハフマン圧縮では使いません。   01011100~   --------   10100011   11111110~   --------   00000001   使用例:2ビット目(0から数える)を0にする    // 2進数 01010111 ( 10進数では 87 )    unsigned char A = 87 ;    // 2ビット目が1の数値(十進数で4)を抜いて他のビットを1にする為に NOT演算を利用する    A = A & ~4 ;    // 結果 A は 2進数で 01010011、10進数で 83 になる  以上6つ(シフト演算子は2つカウント)のビット演算子を利用して ビット演算を行います。 // ================================================================================= 戻る