第108回 プログラミングについて『ファイルを圧縮してみよう！ その7』

　　　　　　　　　　 プログラミングについて　第１０8回目

　　　　　　　　　　 『ファイルを圧縮してみよう！ その７』

　　　　　　　　　　　　　～ＬＺ法で圧縮する その２～

　前回はＬＺ法の基本アルゴリズムで圧縮するプログラムの初版を作成しました。しかしながら実行速度が遅いので、これをなんとかしてみましょう。

　まず実行速度を遅くしていると思われる原因を考えてみましょう。

　（１）文字の検索方法
　（２）２５５文字前の文字配列が一杯になったときの処理

この２つが考えられます。最初に（１）について考えてみましょう。文字の検索には２分木などの構造を使って行なうと無駄が省けるので速度が向上しますが、どのような情報を元にして２分木をつくるかが問題です。実際にいろいろと試してみましたが、なかなかいい方法（検索する先頭の文字で２分木を作ってみました）が見つかりませんでした。２分木に挿入したり、削除する方に手間がかかって速度の向上がみられず、結局のところ諦めてしまいました。

前回の検索部分は、

　search(match,lmatch)
　char *match;
　int　lmatch;
　{
　　int i,l;

　　l=ltext-lmatch;

　　for(i=0;i<=l;i++){
　　　if(memcmp(text+i,match,lmatch)==0)return ltext-i;
　　}

　　return 0;
　}

と単純な方法でしたので、構造はそのままにしておいて文字の検索方法に工夫をしてみましょう。

　以前、文字列の検索のお話をしたことを覚えているでしょうか、２５回目だったと思います。その中で、Ｂｏｙｅｒ－Ｍｏｏｒｅ法というアルゴリズムがあることだけを紹介して詳細の説明をしませんでしたが、この方法を使って検索速度の向上を行なってみましょう。
　Ｂｏｙｅｒ－Ｍｏｏｒｅ法というのは文字列検索を高速に行なうアルゴリズムの１つです。次の例を見て下さい。

　被検索文字列　takoyakitaiyakitarakoyakiimo
　　検索文字列　tarako

最初に検索文字列 tarako の最後の文字 o とその位置にある a は違っています。そこで一致しなかった被検索文字列 a が tarako の中に２個含まれていますが、２番目のa の位置を被検索文字列の a の位置に合わせます。

　被検索文字列　takoyakitaiyakitarakoyakiimo
　　検索文字列　　tarako

再び検索文字列の最後の文字とその位置にある被検索文字列の i を比べると違っています。この i は検索文字列には含まれていないので、検索文字列の文字数分ずらします。

　被検索文字列　takoyakitaiyakitarakoyakiimo
　　検索文字列　　　　　tarako

同じことを繰り返し、検索文字列の最後の文字 o とその位置の被検索文字列 k は一致していません。k は検索文字列の最後から２番目に含まれていますので、この k の位置を一致しなかった被検索文字列の k の位置を合わせます。

　被検索文字列　takoyakitaiyakitarakoyakiimo
　　検索文字列　　　　　 tarako

検索文字列の最後の文字 o とその位置の被検索文字列 i は一致せず、i は検索文字列に含まれていないので検索文字列の文字数分ずらします。

　被検索文字列　takoyakitaiyakitarakoyakiimo
　　検索文字列　　　　　　　　 tarako

ここで一致しました。このように文字の検索を１文字ずつずらして比較を行なうのではなく、検索文字列の最後の文字とその位置の被検索文字列の文字を比較し、一致しないときにはできる限り多くずらすことで無駄な検索を行なわないようにしようというのがＢｏｙｅｒ－Ｍｏｏｒｅ法なのです。

　このアルゴリズムを実現するには検索文字列にどの文字が含まれていて、どの文字のときにどれだけずらすのかというテーブルを作成する必要があります。次のその方法を説明しましょう。今、検索文字列が入っている変数を search とし、テーブルを skipとします。

　char search[MAX_SEARCH];
　int　skip[256];
　int　i,len;

　　　 :
　　　 :

　len=strlen(search);

　for(i=0;i<256　;i++)skip[i]=len;
　for(i=0;i<len-1;i++)skip[(unsigned char)search[i]]=len-i-1;

実はこれだけの簡単な方法でテーブルが完成します。

　for(i=0;i<256;i++)skip[i]=len;

は、すべての文字について検索文字列の長さを代入し、検索文字に含まれない文字のときには検索文字列の文字数分ずらすという値を代入します。

　for(i=0;i<len-1;i++)skip[(unsigned char)search[i]]=len-i-1;

は、検索文字列の最後の文字位置にある被検索文字列の文字が検索文字列にあったときにそれだけずらすのかを代入しています。(unsigned char) としているのは検索文字列の文字の最上位ビットがオンのときに search は char 型ですので負の値になってしまいますので (unsigned char) とすることで －１２８～１２７までの値を ０～２５５にするためです。

　search に代入されている文字列が abcad だったとします。

　for(i=0;i<256;i++)skip[i]=len;

では skip のすべての要素にこの文字列の長さ ５ が代入されます。

　for(i=0;i<len-1;i++)skip[(unsigned char)search[i]]=len-i-1;

では、

　a → skip の a の位置に ５－０－１＝４
　b → skip の b の位置に ５－１－１＝３
　c → skip の c の位置に ５－２－１＝２
　a → skip の a の位置に ５－３－１＝１

と代入されます。最後の文字（この場合は d ）は含めません。検索文字列に a が２つありますが、２番目の a の値が最初の a の値を上書きしますので、結果として検索文字列に含まれているそれぞれの文字の最後のものがシフト量になることになります。

　そこで前回の文字列を検索する関数にこのアルゴリズムを適用してみましょう。

　search(match,lmatch)
　char *match;
　int　lmatch;
　{
　　int i,l;
　　unsigned char skip[MAX_TEXT];

　　for(i=0;i<MAX_TEXT;i++)skip[i]=lmatch;
　　for(i=0;i<lmatch-1;i++)skip[((unsigned char *)match)[i]]=lmatch-1-i;

　　l=ltext-lmatch;

　　for(i=0;i<=l;i+=skip[((unsigned char *)text)[i+lmatch-1]]){
　　　if(text[i+lmatch-1]!=match[lmatch-1])continue;

　　　if(memcmp(text+i,match,lmatch)==0)return ltext-i;
　　}

　　return 0;
　}

むずかしそうに見えますが、やっていることは上で説明した内容と同じです。

　この改修を加えて実行してみたところ、前回は５５秒かかっていた１．３メガのファイルの圧縮時間が１６秒になりかなり改善されました。これは効果が大きかった。

　調子に乗ってもう少し検索について考えてみましょう。Ｂｏｙｅｒ－Ｍｏｏｒｅ法では上の説明から推測できると思いますが、検索文字列が２文字以上では効果が大きいのですが、１文字のときには総当たりの検索と何も変りません。そこで、検索文字列が１文字のときをなんとかしてみましょう。

　２５５文字前までの文字列にどんな文字があるのか、またはないのかが分かっていれば最初の１文字だけで簡単に有無が分かるはずです。そこでその２５５文字前までの文字列に文字を追加する関数 add_char に細工をしましょう。

　まず次の配列をグローバルに定義します。

　int exist[MAX_TEXT];

そしてメイン関数にその初期化を行なわせます。

　main()
　{
　　ifp=fopen( IN_FNAME,"rb");
　　ofp=fopen(OUT_FNAME,"wb");

　　ltext=0;

　　ochar_remain=8;

　　init_exist();　　　　　　　/* 追加 */

　　compress();

　　fclose(ifp);
　　fclose(ofp);
　}
　　　　　　　　　　　　　　　 /* 追加 */
　init_exist()
　{
　　int i;

　　for(i=0;i<MAX_TEXT;i++)exist[i]=0;
　}

ここまでは問題ありませんね。次は add_char 関数です。

　add_char(c)
　char c;
　{
　　if(ltext>=MAX_TEXT){
　　　exist[(unsigned char)text[0]]--;

　　　memcpy(text,text+1,MAX_TEXT-1);
　　　text[ltext-1]=c;
　　}
　　else{
　　　text[ltext++]=c;
　　}

　　exist[(unsigned char)c]++;
　}

文字 c が追加されれば exist の c の位置の要素を１つ増やし、２５５文字以上になったときに最初の１文字を捨てるときに、その捨てる文字の要素の値を１つへらすようにします。こうすることで現在２５５文字前までの文字列にどの文字がどれだけあるのかが分かります。

　そして再び search 関数を変更しましょう。

　search(match,lmatch)
　char *match;
　int　lmatch;
　{
　　int i,l,tot;
　　unsigned char skip[MAX_TEXT];
　　　　　　　　　　　　　　　　　　　　　　　　　　 /* 追加 */
　　tot=exist[(unsigned char)match[lmatch-1]];
　　if(tot==0)return 0;

　　for(i=0;i<MAX_TEXT;i++)skip[i]=lmatch;
　　for(i=0;i<lmatch-1;i++)skip[((unsigned char *)match)[i]]=lmatch-1-i;

　　l=ltext-lmatch;

　　for(i=0;i<=l;i+=skip[((unsigned char *)text)[i+lmatch-1]]){
　　　if(text[i　　　　 ]!=match[0　　　 ])continue; /* 追加 */
　　　if(text[i+lmatch-1]!=match[lmatch-1])continue;

　　　if(memcmp(text+i,match,lmatch)==0)return ltext-i;

　　　if(--tot==0)break;　　　　　　　　　　　　　　 /* 追加 */
　　}

　　return 0;
　}

追加した内容はむずかしくはありません。

　if(--tot==0)break;

のＩＦ文は検索文字の長さが１のときには効果はありますが、それ以上の場合には
Ｂｏｙｅｒ－Ｍｏｏｒｅ法では途中を飛ばしていきますので運が良いとき以外は tot が
０になることはないはずです。この関数でもう少し無駄な部分を直しましょう。

　if(text[i　　　　 ]!=match[0　　　 ])continue;
　if(text[i+lmatch-1]!=match[lmatch-1])continue;

で match[0] と match[lmatch-1] は常に同じ文字なので次のようにします。

　search(match,lmatch)
　char *match;
　int　lmatch;
　{
　　char cs,ce;
　　int i,l,tot;
　　unsigned char skip[MAX_TEXT];

　　tot=exist[(unsigned char)match[lmatch-1]];
　　if(tot==0)return 0;

　　for(i=0;i<MAX_TEXT;i++)skip[i]=lmatch;
　　for(i=0;i<lmatch-1;i++)skip[((unsigned char *)match)[i]]=lmatch-1-i;

　　cs=match[0　　　 ];
　　ce=match[lmatch-1];

　　l=ltext-lmatch;

　　for(i=0;i<=l;i+=skip[((unsigned char *)text)[i+lmatch-1]]){
　　　if(text[i　　　　 ]!=cs)continue;
　　　if(text[i+lmatch-1]!=ce)continue;

　　　if(memcmp(text+i,match,lmatch)==0)return ltext-i;

　　　if(--tot==0)break;
　　}

　　return 0;
　}

　この改修を加えた後実行してみた結果、１６秒だったものが１１秒に短縮されました。

これで検索についての改善は終了です。次にもう１つの懸念だった２５５文字前の文字配列が一杯になったときの処理です。当然のことですが、入力ファイルを２５５文字読み込んだらそれ以降は常にこの配列は一杯です。そこへ１文字を追加すると１文字先頭方向にずらすのですから２５４文字のコピーが行われることになります。ということは入力ファイルのサイズが４５５バイトだったら、２５４＊２００＝５０８００バイトのコピーを行なうことになります。これは無駄に違いありません。

　この回数を減らせば無駄な時間が減る可能性があります。そこで、グローバルに定義してある text を次のように変えて変更を加えてみましょう。

　　　　　　 :
　　　　　　 :

　#define MAX_BASE_TEXT (MAX_TEXT*10)

　char base_text[MAX_BASE_TEXT];
　char *text;
　int　ltext;

　　　　　　 :
　　　　　　 :

text を文字配列へのポインタとし、別に base_text という大きい配列を用意します。
この base_text を text が示せばなんとかなるはずです。

最初にメイン関数を次のように変更します。

　main()
　{
　　ifp=fopen( IN_FNAME,"rb");
　　ofp=fopen(OUT_FNAME,"wb");

　　 text=base_text;
　　ltext=0;

　　ochar_remain=8;

　　init_exist();

　　compress();

　　fclose(ifp);
　　fclose(ofp);
　}

そして add_char 関数を次のように変更します。

　add_char(c)
　char c;
　{
　　if(ltext>=MAX_TEXT){
　　　exist[(unsigned char)text[0]]--;

　　　 text++;
　　　ltext--;
　　}

　　text[ltext++]=c;

　　if(text+ltext>=base_text+MAX_BASE_TEXT){
　　　memcpy(base_text,text,MAX_TEXT);
　　　text=base_text;
　　}

　　exist[(unsigned char)c]++;
　}

この改修は、２５５文字以上になったら text のポインタを１つずらし、見かけ上は全体が１文字ずれたようにします。そして base_text が一杯になった時点で２５４文字だけをコピーし、text が再び base_text の先頭を指すようにしています。

　この改修で実行時間が９秒になりました。多分このあたりが限界だと思います。最初の５５秒と比べれば６倍の改善です。それでも圧縮率は別にしてもＬＨＡが６秒ですので殆ど遜色がなくなりました。

　最後に全文です。

　#include <stdio.h>

　#define　IN_FNAME "z.z"
　#define OUT_FNAME "x.x"

　#define MAX_TEXT 256
　#define MAX_BASE_TEXT (MAX_TEXT*10)

　char base_text[MAX_BASE_TEXT];
　char *text;
　int　ltext;

　int exist[MAX_TEXT];

　char ochar;
　int　ochar_remain;

　FILE *ifp,*ofp;

　main()
　{
　　ifp=fopen( IN_FNAME,"rb");
　　ofp=fopen(OUT_FNAME,"wb");

　　 text=base_text;
　　ltext=0;

　　ochar_remain=8;

　　init_exist();

　　compress();

　　fclose(ifp);
　　fclose(ofp);
　}

　init_exist()
　{
　　int i;

　　for(i=0;i<MAX_TEXT;i++)exist[i]=0;
　}

　compress()
　{
　　char match[MAX_TEXT];
　　int lmatch;
　　int　 prev;
　　int　p;
　　char c;

　　　prev=0;
　　lmatch=0;

　　while(1){
　　　c=fgetc(ifp);
　　　if(feof(ifp))break;

　　　while(1){
　　　　match[lmatch]=c;

　　　　p=search(match,lmatch+1);
　　　　if(p){
　　　　　prev=p-lmatch;

　　　　　lmatch++;

　　　　　if(lmatch>=MAX_TEXT-1){
　　　　　　output_same(prev,lmatch);
　　　　　　　prev=0;
　　　　　　lmatch=0;
　　　　　}
　　　　}
　　　　else if(prev){
　　　　　if(lmatch>=2)output_same(prev,lmatch);
　　　　　else　　　　 output_char(match[0]);

　　　　　　prev=0;
　　　　　lmatch=0;

　　　　　continue;
　　　　}
　　　　else{
　　　　　output_char(c);
　　　　}

　　　　break;
　　　}

　　　add_char(c);
　　}

　　if(prev){
　　　if(lmatch>=2)output_same(prev,lmatch);
　　　else　　　　 output_char(match[0]);
　　}

　　output_same(0,0);

　　add_bits(0,7);
　}

　add_bits(v,l)
　int v,l;
　{
　　while(l-- >0){
　　　ochar<<=1;
　　　ochar_remain--;

　　　if(v & (1<<l))ochar|=1;
　　　else　　　　　ochar|=0;

　　　if(ochar_remain<=0){
　　　　fputc(ochar,ofp);
　　　　ochar_remain=8;
　　　}
　　}
　}

　output_char(c)
　char c;
　{
　　add_bits(　　 0,1);
　　add_bits((int)c,8);
　}

　add_char(c)
　char c;
　{
　　if(ltext>=MAX_TEXT){
　　　exist[(unsigned char)text[0]]--;

　　　 text++;
　　　ltext--;
　　}

　　text[ltext++]=c;

　　if(text+ltext>=base_text+MAX_BASE_TEXT){
　　　memcpy(base_text,text,MAX_TEXT);
　　　text=base_text;
　　}

　　exist[(unsigned char)c]++;
　}

　output_same(prev,len)
　int prev,len;
　{
　　add_bits(　 1,1);
　　add_bits(prev,8);
　　add_bits( len,8);
　}

　search(match,lmatch)
　char *match;
　int　lmatch;
　{
　　char cs,ce;
　　int i,l,tot;
　　unsigned char skip[MAX_TEXT];

　　tot=exist[(unsigned char)match[lmatch-1]];
　　if(tot==0)return 0;

　　cs=match[0];
　　ce=match[lmatch-1];

　　for(i=0;i<MAX_TEXT;i++)skip[i]=lmatch;
　　for(i=0;i<lmatch-1;i++)skip[((unsigned char *)match)[i]]=lmatch-1-i;

　　l=ltext-lmatch;

　　for(i=0;i<=l;i+=skip[((unsigned char *)text)[i+lmatch-1]]){
　　　if(text[i　　　　 ]!=cs)continue;
　　　if(text[i+lmatch-1]!=ce)continue;

　　　if(memcmp(text+i,match,lmatch)==0)return ltext-i;

　　　if(--tot==0)break;
　　}

　　return 0;
　}

次回は伸長するプログラムを作成しましょう。