ゲームプログラムをしているとあんまり『圧縮』というものに触れる
機会がありません。

　そして、触れた事があるとしたら恐らくその切っ掛けの殆どは『たまたま』
ではないかと推察します。(たまたまプログラムの雑誌に書かれてた、授業で
たまたま圧縮が取り上げられた、等)
　ここもその『たまたま』の１つとして、圧縮について書いてみたいと思います。



　ではまず、

RRRRRRABDDDDDGG

　という文字列があったとします。
　これに『ランレングス圧縮』という圧縮をかけると次のようなデータになります。

RR6ABDD5GG2

　ここでは


　同じ文字が２回以上続いたらその部分を

[２回以上続いた文字][２回以上続いた文字][続いた数]

　という情報に置き換える


　というルールで圧縮をかけています。お陰で元の文字列より４文字短くなりました。
(ただ、２文字ピッタリの場合は逆に１文字分増えるという欠点もあります(汗))

　復元する時は２回同じ文字が続いたらそれは「２文字以上続いていた
から変換された」箇所なので、３文字目にある回数だけその文字を並べてやれば

RRRRRRABDDDDDGG

　という文字列に戻せます。
　これだけで圧縮出来てしまうのです。割りと簡単ではないでしょうか？

　此処では分かり易く文字で例えましたが、実際は数値で処理します。
　例えば RRRRRRABDDDDDGG は数値で書くと

'82' '82' '82' '82' '82' '82' '65' '66' '68' '68' '68' '68' '68' '71' '71'

　(一つの ' ' が１バイト、82=R　65=A　66=B　68=D　71=G )
　なので、ランレングス圧縮後は

'82' '82' '6' '65' '66' '68' '68' '5' '71' '71' '2'

　となります。数値も処理出来ると言う事はこの方法は画像データ等の
バイナリデータでも使えるということです。

　というわけで、一番基本的な圧縮について説明してみました。これがいわゆる圧縮
というヤツです。色々な法則を使って、元のデータを壊さずに、元のデータよりも
記憶に必要なデータ領域を少なくしてしまおうというわけです。
(ＪＰＥＧ等は元のデータを壊しますが・・・)

　尚、ここで説明したランレングス圧縮では何回も同じ数値が続いていなければ
圧縮出来ないので、写真画像等の隣り合ったドットの色が同じ、なんてことは
殆ど無いデータは全然圧縮できません。しかも、先程ちょっと触れましたが
２回しか連続していない場合は圧縮するどころか逆に１バイト増えてしまいます。

　ランレングス圧縮以外の基本的な圧縮方式にハフマン圧縮というのがあるの
ですが、ランレングス圧縮よりも実現が大変な割には単体ではあんまり圧縮率が
高くありません。

　・・・・。

　となるとやはり、実用可能なレベルの圧縮率を出すにはもっと複雑で実装が
大変なアルゴリズムを使わなくちゃいけないのか？ などと思ってしまいそうですが
(というか私は思っていましたが)、そうではありませんでした。

　ＬＺＳＳ圧縮という圧縮方法があり、これが中々良い感じなのです。

　ＬＺＳＳ圧縮とは Lempel という方と Ziv という方が１９７７年に
発案した圧縮方式ＬＺ７７(名前の頭と発案した年を取っているようです)
を、１９８２年に Storer という方と Szymanski という方が改良を加えた
圧縮方式です。(『です』と言い切れるほど熟知している訳ではありませんが(汗))
　この圧縮方式は理屈はランレングス圧縮と同じくらい単純なのに、
ランレングス圧縮に比べたら数段実用的な圧縮率が望めます。

　例えば

ABCDEFGABCDEFCDEFGH

　という文字列があったとします。これにＬＺＳＳ圧縮をかけると
次のようになります。

ABCDEFG[7,6][11,5]H

　一つの [ ] は３文字分だと思ってください。
　とすると

ABCDEFGABCDEFCDEFGH = 19 文字
ABCDEFG[7,6][11,5]H = 14 文字

　というわけで５文字分減りました。
　この圧縮方式の理屈は

　同じ文字(数値)の羅列が以前も出てきた場合は、何文字(何バイト)前から
何文字(何バイト)同じ文字(数値)が続いているか、という情報に置き換える。

　というものです。
　その情報に必要な文字数(バイト数)は３文字(３バイト)ですので、『何文字
(何バイト)同じ文字(数値)が続いているか』が、もし３文字以上だった場合は
その分元のデータよりも小さくなるわけです。

　つまり

ABCDEFG[7,6][11,5]H

　の [7,6] というのは元の文字列の７文字前から６文字同じ羅列がありますよ、
という事を指しているわけです。(同じく [11,5] は元の文字列の １１文字前
から５文字同じ羅列がありますよ、という意味です)

　確認してみましょう

ABCDEFGABCDEFCDEFGH

　の中の[7,6]に置き換えられたところは

ABCDEFG

　の次の'A'の部分です。
　[7,6]に従うと、丁度この'A'から７文字前から６文字分同じ文字列が続くと
言っています。

ABCDEF'G'　一文字前
ABCDE'F'G　二文字前
ABCD'E'FG　三文字前
ABC'D'EFG　四文字前
AB'C'DEFG　五文字前
A'B'CDEFG　六文字前
'A'BCDEFG　七文字前

　確かに７文字前に同じ'A'がありました。ここから６文字同じだそうです。

ABCDEFGABCDEFCDEFGH の中の

'ABCDEF'G'ABCDEF'CDEFGH

　''で囲われたところ同士、確かに六文字同じです。
　次に[11,5]を確認してみましょう。
　これは[7,6]の直後に来ていますが、[7,6]の直後といえば

ABCDEFGABCDEF

　この直後の'C'の部分です。
　[11,5]の通りならばここから１１文字前から５文字分同じ文字列がある
ということです。どうでしょう、１１文字前といえば

AB'C'DEFGABCDEF

　確かに同じ'C'があります。ここから後の５文字分の CDEFG も確かに

ABCDEFGABCDEF

　の後の

CDEFGH

　と５文字分だけ合っています。

　ところで、ランレングス圧縮の時は『同じ文字が２回続く』ことで圧縮
された情報かどうかを判別していましたが、ＬＺＳＳ圧縮ではどうやって
圧縮された情報かどうかを判別するのでしょうか？

　これについては、一番登場回数が少ない文字を圧縮情報の識別子にして
しまうという方法があります。(ＬＺＳＳ正規のものはちょっと面倒なので・・・)

　先程の

ABCDEFGABCDEFCDEFGH

　でいうなら、H です。一回しか出てきません。
　なので、

　H が出てきたら、そのあとの１文字目を『何文字前からか？』の数値、
２文字目を『何文字同じか？』の数値と判断します。

　で、H 自体だった場合は HH と２回続けます。ランレングス圧縮の
場合と逆です。(^^;

　なので、

ABCDEFG[7,6][11,5]H　

　を [ ] で誤魔化さずに表現すると

'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' '7' '6' 'H' '11' '5' 'H' 'H'

　となります。
　(一つの '' が一バイト(０～２５５まで表現可能))
　数値で表現すると

'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 )

　これですと圧縮情報の印に選出された数値の登場回数分だけ無駄に
データが増えてしまうことになりますが、私が試した限りではその
せいで圧縮前のデータよりもサイズが大きくなってしまう、ということは
ありませんでした。恐らく相当圧縮し難いデータで無い限りは逆にサイズが
増えてしまう、なんてことは無いと思います。(ＬＺＨやＺＩＰなどの既に
圧縮されたデータをこの方法でさらに圧縮しようとすると増えるかもしれませんが)
　因みに、どの文字を圧縮情報の印に使っているかは別に保存しておく
必要があります、でないと復元できないので。(^^;

　というわけで、ＬＺＳＳ、お勧めです。
(とはいえ正規の方法を使わない時点で既に『ＬＺＳＳ風』ですが(汗))

　ここで説明は終わりですが、やはり実際に動くプログラムを見てみないと
しっくり来ない、という方もいると思います。なので、簡単なサンプル
プログラムを用意しました。今の説明で抜けている部分は全てこちらに
ありますので宜しければご覧になってみて下さい。

<<圧縮>>
https://dxlib.xsrv.jp/lecture/Press/LzssEncode.cpp // ソース
https://dxlib.xsrv.jp/lecture/Press/LzssEncode.exe // 実行可能ファイル(コンソールアプリケーション)

<<解凍(展開)>>
https://dxlib.xsrv.jp/lecture/Press/LzssDecode.cpp // ソース
https://dxlib.xsrv.jp/lecture/Press/LzssDecode.exe // 実行可能ファイル(コンソールアプリケーション)

(細部まで完全に説明し切っているわけではないので、不明な点があり
ましたら掲示板の方にお書き込みください)

　ソースは BCC でも VC でも『コンソールアプリケーション』として
コンパイルできます。(Windows アプリケーションとしてはコンパイル出来ません)

　圧縮ソフトにに圧縮したいファイルをドラッグ＆ドロップすれば
拡張子が『lzs』になった圧縮ファイルが作成されます。
　圧縮されたファイルを解凍ソフトにドラッグ＆ドロップすれば
拡張子が『dec』になった元のファイルと同じ内容のファイルが
作成されます。

　その他・・・

・　自然画やＷＡＶファイルは殆ど圧縮できません。orz
・　『もっと圧縮率を高くしたい』という方は、このソフトで圧縮した
　ファイルに『ハフマン圧縮』または『レンジコーダー圧縮』というものを
　掛けてみてください。さらに少しだけ圧縮することが出来ます。
　(または『ブロックソーティング(Block Sorting)』や
　『ＰＰＭ (Prediction by Partial Matching) 』などを調べて見て下さい)
・　複数のファイルを一つのファイルにする機能は『圧縮』ではなく
　『アーカイブ』という機能ですので、このソフトでは一つのファイル
　しか圧縮出来ません。(つまり LZH や ZIP 等は圧縮データ形式であると
　同時にアーカイブデータ形式でもあるわけです)


　あと、上記のソフトを使用して圧縮した画像データ、音声データを
ＤＸライブラリで読み込むサンプルもこちらに置いておきます。

https://dxlib.xsrv.jp/lecture/Press/LzssDxSample.cpp // ソース
https://dxlib.xsrv.jp/lecture/Press/LzssDxSample.exe // 実行可能ファイルとデータファイル一式(普通の Win32 アプリケーション)

　ソースのコンパイルには普通にＤＸライブラリのコンパイル環境が必要に
なります。



　今回お世話になったサイト


[[やまざき＠BinaryTechnology]]

リンクについて何処にも書かれていなかったので google( http://www.google.co.jp/ )で検索してください。(^^;
こちらのサイトの『データ圧縮の基礎』というページで圧縮の基礎が学べます。


[[M.Hiroi's Home Page]]
http://www.geocities.jp/m_hiroi/index.html

こちらのサイトには様々な圧縮方法について基礎から実用方法まで分かり易く説明されています。
ここの説明が要らない位です。(^^;









　折角なのでハフマン圧縮についても間単に説明します。

　ハフマン圧縮は 1952年に David A. Huffman という方が発案しました。
今から５０年以上も前に作られた圧縮方法というのは驚きですね。(・・;;

　では早速例を。
　例えば次のような文字列があったとします

ABEBCCBBDBCCACCCDECDE

　これに、ハフマン圧縮をかけると上記の文字列が次のようになります

11110010110000100100110100001110001101010110101

　これは２進数の数値列です。
　驚いた方に謝ります、すいません。

// ２進数とデータサイズの説明(知らない方向け) ===============================

　まず２進数は０、１と数えていき、２で桁が繰り上がり１０になります。
『じゅう』ではなくて『いちぜろ』です。
　３ は １１、４ はまた桁が繰り上がって １００ になります。

対応表

２進 　１０進
00000　０
00001　１
00010　２
00011　３
00100　４
00101　５
00110　６
00111　７
01000　８
01001　９
01010　１０
01011　１１
01100　１２
01101　１３
01110　１４
01111　１５
10000　１６

　で、よくＣ言語の解説書等には unsigned char (符号なし１バイト型) は
０から２５５まで表現できる、と書いてありますが、それは『１バイト』は
２進数８桁の情報のことを指していて、２進数８桁では最大で２５５までしか
表現できないからなのです。

２進　　　１０進
11111111　２５５

　というわけです。(これ以上１でも増えたら９桁になってしまう)

　あと、よく５１２メガバイトとか１２０ギガバイトとか聞きますが、
その関係は

１バイトが１０２４個　＝　１キロバイト (1KByte)
１キロバイトが１０２４個　＝　１メガバイト (1MByte)
１メガバイトが１０２４個　＝　１ギガバイト (1GByte)

　ということになります。
　１バイトで１文字表現できるので(日本語文字などは１文字２バイト必要)
１メガバイトあれば 1024 x 1024 = 1,048,576 = １０４万８５７６文字も
記憶出来るということになります。(日本語文字なら５２万４２８８文字)

　ちなみに『ビット(bit)』という言葉も聞いたことがあるかもしれませんが、
１ビットというのは２進数１桁のことを指しています。なので２進数８桁
で１バイトである『バイト(byte)』という単位は、１バイトあたり８ビット
ということになります。

01001010 = ２進数８桁 = ８ビット = １バイト
01110000 11101011 = ２進数１６桁 = １６ビット = ２バイト

　というわけです。

// ================================================================

　さて、先程の

11110010110000100100110100001110001101010110101

　は、意味は分かりませんが、とりあえず２進数４７桁です。
バイトに直すと ４７÷８＝５．８７５、つまり６バイト弱、
元の文字列が２１文字(バイト)なのでかなり圧縮されて
いることになります。

　ではこの数値列の謎を解きましょう。
　実は上記の０と１の数値列は元の

ABEBCCBBDBCCACCCDECDE

　の各文字を、次の２進数の数値列と文字との対応表を元に
変換したものなのです

A = 111
B = 100
C = 0
D = 110
E = 101

　試してみましょう。左端から見ていきます

　11110010110000100100110100001110001101010110101

の最初の 111100 は最初の３ビット 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 だけが対応するビット列の長さが違いましたが、実際には
出現回数が多いものほどビット列が短くなり、出現回数が少ないもの
ほどビット列が長くなります。ついでに出現するものの種類が多くなれば
全体的なビット列も長くなります。今回は５種類しかなかったので最高
３ビットになっているわけです。

　では、この

A = 111
B = 100
C = 0
D = 110
E = 101

　表はどうやって作ればいいのでしょう？

　例えば『０』一個で終わってしまう C がある時点で他に０から始まる
文字を表に加えることは出来ませんし、『１０１』で終わる E がある
時点で『１０１０１』という対応コードを持つ文字を表に加えることも
出来ませんから、普通に考えると大変そうです。

　ですがこれには簡単な方法で導きだすことが出来ます。


　まず先程の



　を、とりあえず分かり易くするために



　出現数の小さい順に並べ直します。



　次に、一番小さい数値二つを繋げて、繋いだ上に二つの出現数を足した
値を書き込みます。D と E は同じ数値ですが、同じ数値のデータが複数
あるばあいはどれを選んでも構いません。



　同じ手順を繰り返します。ただし、繋いだ A と D はもう比較対象には
入れずに、代わりに A と D を繋いだ部分を比較対象に加えます。
　この中で一番値が低いのは E の３です。次に低いのは A と D を足した
値５と B の５ですが、これも先程と同じようにどちらをつなげても構いません。(今回はＢと繋げました)
　そして同じように繋いだ上に E と B の出現数を足した値８を書き込み、
次は E と B の代わりに比較対照とします。



　残ったのは A と D を繋いだ値５と E と B を繋いだ値８、あと C の
８です。また同じになってしまいましたが、今回もどちらでも良いので
今度は A と D を繋いだものと E と B を繋いだものを繋ぎました。
　同じように上に足した値を書き込みます。



　後は残ったものどうしを繋げるだけです。



　次に繋いだ部分の左右に右に０、左に１を書き込みます。
０と１は左右逆でも構いません。



　最後に天辺から各文字のところまで辿ります。
　辿る途中で通過した分岐の数値を各文字の下に書き込みます。

　すると、なんと、例の表

A = 111
B = 100
C = 0
D = 110
E = 101

　の通りになりました。
　というわけです。(^^;

　なお、この表は

　11110010110000100100110100001110001101010110101

　からは連想することは出来ませんので、出来上がった表を別に保存
しておくか、１バイトで表現できる０から２５５までの数値の出現数を
別に保存しておくか、どちらかをする必要があります。
　大体それらには１キロバイトほどの保存領域が必要になります
ので(ちょっと面倒くさいことをすればもっと小さく出来ますが)
１キロバイト以下のデータをハフマン圧縮しようとしても、
どう足掻いても圧縮できないということになります。

　ですが、１キロバイト以下のファイルというのはあんまり無いので、
大抵は小さくなるというわけです。


　これで、圧縮と復元の理屈はわかったと思います。
　後はどうやってＣ言語のプログラムにするかですが、その辺りは
サンプルプログラムをご覧下さい。(^^;

<<圧縮>>
https://dxlib.xsrv.jp/lecture/Press/HuffmanEncode.cpp // ソース
https://dxlib.xsrv.jp/lecture/Press/HuffmanEncode.exe // 実行可能ファイル(コンソールアプリケーション)

<<解凍(展開)>>
https://dxlib.xsrv.jp/lecture/Press/HuffmanDecode.cpp // ソース
https://dxlib.xsrv.jp/lecture/Press/HuffmanDecode.exe // 実行可能ファイル(コンソールアプリケーション)


　ＬＺＳＳ圧縮の時と同じようにこのソースは BCC でも VC でも『コンソール
アプリケーション』としてコンパイルできます。(Windows アプリケーションとしては
コンパイル出来ません)

　圧縮ソフトにに圧縮したいファイルをドラッグ＆ドロップすれば
拡張子が『huf』になった圧縮ファイルが作成されます。
　圧縮されたファイルを解凍ソフトにドラッグ＆ドロップすれば
拡張子が『dec』になった元のファイルと同じ内容のファイルが
作成されます。

　というわけで、ざっくりとした圧縮の説明でした。(^^;

// ビット演算の説明 ======================================================

　ハフマン圧縮はバイト単位の処理ではなくビット単位の処理になるので、
ビット単位の処理をする方法を知らないといけません。

　ので、ここで簡単なビット演算の方法を記述します。



・シフト演算 『<<』 又は 『>>』

　　ビット単位で数値を左右に移動したい時に使います。


　　使用例：２ビット左にシフトする

　　　// ２進数で 00110100 (１０進数では 52 )
　　　unsigned char A = 52 ;

　　　// A <<= 2 ; と書くことも出来る
　　　A = A << 2 ;

　　　// A の値は２進数で 11010000(十進で 208) になる。(左に２ビット移動した)


　　注意：
　　　　11001111 を右に２ビットシフトして 00110011 になった後、左に２ビット
　　　シフトすると 11001100 になる、つまりスクロールアウトしてしまった部分は
　　　元に戻らず、スクロールインしてきたビットは必ず０で埋められます。



・論理積演算(AND(アンド)演算)『&』

　　ビット単位である演算を行います。
　　法則は以下の計算を見て覚えて下さい。

　　11001111
　　10110101&
　　---------
　　10000101

　　01101011
　　10010101&
　　---------
　　00000001

　　　要は『どちらも１じゃないと０になる』です。
　　　これは特定のビットが０か１かを調べたり、特定のビット域だけを
　　抽出したりする時に使います。


　　使用例：変数 A の０ビット目が０か１かを判断する

　　　// ２進数 01010101 ( １０進数では 85 )
　　　unsigned char A = 85 ;
　　　if( ( A & 1 ) == 0 )
　　　{
　　　　　// ０ビット目は 0 
　　　}
　　　else
　　　{
　　　　　// ０ビット目は 1 
　　　}
　　
　　　// この例では判断式では A の０ビット目は 1 なので結果は『偽』になります



・論理和演算(OR(オア)演算) 『|』

　　論理積演算に似ていますが効果は逆といった感じです。

　　11001111
　　10110101|
　　---------
　　11111111

　　01000011
　　10010101|
　　---------
　　11010111

　　要は『どちらか１なら１になる』です。

　　特定のビットを１にしたいとき等に使用します。


　　使用例：変数 A の７ビット目(０から数える)を１にする

　　　// ２進数 01110100 ( １０進数では 116 )
　　　unsigned char A = 116 ;

　　　// A |= 128 ; と書くことも出来る。因みに 128 は ２進数で 10000000
　　　A = A | 128 ;

　　　// 結果 A は ２進数で 11110100、１０進数で 244 になる

　　

・排他的論理和演算(XOR(エックスオア?)演算) 『^』

　　　今回のハフマン圧縮では使わない演算子です。

　　11001111
　　10110101^
　　---------
　　01111010

　　01010011
　　10010101^
　　---------
　　11000110

　　　要は『片方だけ１なら１、どちらも０かどちらも１なら０』です。
　　　偶に使います。



・否定演算(NOT(ノット)演算) 『~』

　　　ビットを全て反転します。２つの数値を演算するのではなく、単体で
　　使用します。これも今回のハフマン圧縮では使いません。

　　01011100~
　　--------
　　10100011

　　11111110~
　　--------
　　00000001


　　使用例：２ビット目(０から数える)を０にする

　　　// ２進数 01010111 ( １０進数では 87 )
　　　unsigned char A = 87 ;

　　　// ２ビット目が１の数値(十進数で４)を抜いて他のビットを１にする為に NOT演算を利用する
　　　A = A & ~4 ;

　　　// 結果 A は ２進数で 01010011、１０進数で 83 になる



　以上６つ(シフト演算子は２つカウント)のビット演算子を利用して
ビット演算を行います。

// =================================================================================

戻る