第39章 速読法3

 今回も文字列照合について話していきたいと思います。2つの有名なアルゴリズムのうちのもう1つです。


 では、今回の要点です。


 では、いってみましょう。


 さて、前回のKMP法とは違った角度から、もう一度文字列照合について考えてみましょう。では、Match.txt から "mato" を検索しましょう。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat : mato

"toma" と "mato" は1文字目から違うので、1つ先に進みます...と今まではやってきました。

 ここでちょっと考えてみましょう。どうにかして一度に2つ以上進むことはできないでしょうか? これができれば、かなり速くなりそうです。

 pat の先頭から比べる限りそれは無理な話です。しかし、ここは逆転の発想で pat の後から比べていけば何とかなるかもしれません。つまり、上の例では

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat : mato

の赤くなっている部分から逆に比べていくようになります。後から比べれば、その情報を活かして読み飛ばせる可能性が出てきます。

 では、どう情報を活かせばよいのでしょうか? 今回の比較では、やはり一番最後も異なっています。このとき、src で比較に使われた文字は "a" です。もし、この "a" が pat の中に出てこなければ、ここまでの中には pat は出てこないということが分かるはずです。

 しかし、今回は pat は "a" を含みます。この場合はどうすればよいでしょうか?

 この "a" を含む部分に pat が見つかるとします。その場合は、必ずこの "a" と pat 内の "a" は重なっています。つまり、お互いの "a" が重なるようにずらせばいいわけです。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :   mato

 今度も一番最後が異なります。そして、pat は "u" を含みません。というわけで、一気に4つ飛ばすことができます

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :        ma to

 次は "to" の2つが同じです。しかし、それ以上は違います。ここでまた最後の "o" が pat に出てこないかどうかを調べます。pat の最後に "o" がありますが、先に進めないと行けないのでこれは無視します。すると、やはり "o" は出てこないことになります。ということで、やはり一気に4つ飛ばすことができます。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :             mato

 これを続けていけば最終的に最後にある "mato" が見つかることになります。


 では、今度は "tamaty" を探してみましょう。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat : tamaty

 そもそも src に "y" は含まれないので、毎回必ず異なることが分かります。なので、ここでは先に進むことに専念しましょう。

 "u" は pat に含まれていないので、一気に6つ進みます。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :        ta maty

 "a" は pat にも含まれます。しかし、2つ含まれています。このような場合はどれだけ進めればいいのでしょうか?

 読み飛ばしすぎると等しいのに飛ばしてしまう可能性が出てきます。ということは、一番右を除いて最も右側に出てくるところを重ねるのが筋ですね。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :           tamaty

 さぁ、これを続けていきましょう。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                  ta maty
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                     tamaty
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                            ta maty
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                               tamaty
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                                      ta maty
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                                         tamaty
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                                               tamaty

...と、いきすぎてしまいました。このように、BM法はいきすぎてしまいます。つまり、終了条件がヌルターミネータという訳にはいかないのです。あらかじめ src の長さを確認しておいていきすぎないように確認する必要があるわけです。

 もしくは、src のお尻に 0 を pat の長さ分つけておいて src に 0 が現れれば終わり、とか、src の最後に pat をコピーしておき、それが検索されたら検索失敗、とかとすることもできます。長さを確認する方法の方が汎用性の高いでしょうが、後者のような方法も頭の隅にでも置いておけば、いつか役に立つこともあるかもしれません。


 では、今度は src に出てきた文字が pat のどこに現れるかを確かめるにはどうすればよいでしょうか? これはKMP法をやっていれば分かるように、やっぱり表にしておくとよいでしょう。文字コードは0〜255のどれかなので、KMP法と違い表のサイズは一定です。

 この一連の文字列照合法をBM法と呼びます。本来のBM法は表を2つ使いますが、ここでは1つだけしか使わない簡略版のBM法を紹介しました。

 BM法は基本的に後ろ向きに比較していくので、KMP法のような「読み戻しがない」という特徴はありません。この点ではKMP法の方が優れていますが、検索速度は一般的にBM法の方が上です。バシバシと読み飛ばせるので気分爽快です。


 では、プログラムを見てみましょう。

プログラム
// Match5.cpp
#include <string.h>
#include <limits.h>
#include "Match2.h"

#define numof(array)  (sizeof (array) / sizeof *(array))

static int BMMatch(const char* src, int nBufSize,
                   int nFirst, const char* pat);

int main()
{
    Match("Match.txt", BMMatch);
    return 0;
}

static int BMMatch(const char* src, int nBufSize,
                   int nFirst, const char* pat)
{
    // エラーチェック
    if(pat[0] == 0        ||
       src[nBufSize] != 0 ||
       nFirst > nBufSize)
        return MATCH_NOTFOUND;

    // UCHAR_MAX は limits.h 内で定義され、
    // unsigned char の最大値 255 を表します
    int skip[UCHAR_MAX + 1];
    int nPatSize;
    int i;

    // pat のサイズを測ります
    nPatSize = strlen(pat);

    // 表を pat のサイズで初期化します
    // 完全にスキップすることを表します
    for(i = 0; i < numof(skip); i++)
        skip[i] = nPatSize;

    // 表の作成を行います
    // 左端から単純に skip を埋めていけば、
    // 同じものが2度以上出てきても上書きされ、
    // 最終的には一番右の位置が保存されます
    // スキップする数は、i = 0 (最初)で nPatSize - 1 になるので
    // 一般的には nPatSize - 1 - j だと分かります
    for(i = 0; i < nPatSize - 1; i++)
        skip[pat[i]] = nPatSize - 1 - i;

    // 照合
    nPatSize--;  // 便利がいいので1つ減らしておきます

    // src の比較開始文字
    char letSkip;
    // pat の最後の文字
    char letLast = pat[nPatSize];

    for(i = nFirst + nPatSize; i < nBufSize; i += skip[letSkip])
    {
        letSkip = src[i];

        // pat の最後の文字と比較
        if(letSkip == letLast)
        {
            int j = i - 1;
            int k = nPatSize - 1;
            for(; src[j] == pat[k]; j--, k--)
            {
                // pat の最初まで等しければ検索終了です
                if(k == 0)
                    return j;  // 
            }
        }
    }
    return MATCH_NOTFOUND;
}

 KMP法と同じく、コメントを除けば意外とすっきりしていることが分かります。ちょっとした労力でずいぶんと検索速度が上がるということが分かりますね。

 ただ、検索対象の文字列があまりに短いとBM法やKMP法よりも strstr の方が速かったりします。表を作る時間のせいです。これら特殊なアルゴリズムは、少し大きめの検索対象に対して使うといいでしょう。


 では、今回の要点です。


 次回でアルゴリズム編は終了です。次回はKMP法の途中で話したアレについて話そうと思います。では。


第38章 速読法2 | 第40章 二世帯住宅

Last update was done on 2001.4.17

この講座の著作権はロベールが保有しています