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

　では、今回の要点です。

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

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

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

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

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

　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" を含みません。というわけで、一気に４つ飛ばすことができます。

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

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

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 に含まれていないので、一気に６つ進みます。

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

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

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

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

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

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

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

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

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

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

// 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 を埋めていけば、
    // 同じものが２度以上出てきても上書きされ、
    // 最終的には一番右の位置が保存されます
    // スキップする数は、i = 0 （最初）で nPatSize - 1 になるので
    // 一般的には nPatSize - 1 - j だと分かります
    for(i = 0; i < nPatSize - 1; i++)
        skip[pat[i]] = nPatSize - 1 - i;

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

    // 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;
}

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

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

　では、今回の要点です。

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

第３８章　速読法２ | 第４０章　二世帯住宅

Last update was done on 2001.4.17

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