今回も前回に続いて文字列照合について話していきたいと思います。２つの有名なアルゴリズムのうち、今回はその一方について話します。
では、今回の要点です。
では、いってみましょう。
前回の Match.txt を思いだしてみましょう。
| Match.txt |
|---|
tomatu tomati tomata tomate tomato |
では、この中から "tomato" を探すことにします。先ず、先頭をあわせて比較してみましょう。
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato pat : tomato
"tomat" までは同じですが、最後が異なるので先に進むことにします。
しかし、ちょっとここで考えてみましょう。"tomat" までが同じだったことを利用することはできないでしょうか？
"tomat" は "t" で終わっています。これは "tomato" の最初の文字 "t" と同じですね。ということは、その次が "omato" であればよいことになります。
src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato pat : to ma to
このように、比較した終わりの部分が検索文字列の先頭と同じであれば、その部分から検索文字列の残りの部分との比較を行ったのでよいわけです。そして、同じでなければ、その部分までに "tomato" がないことになるので、その次から pat との比較を始めればよいのです。
説明文だけではピンとこないかもしれないので、いくつか例を挙げていきたいと思います。
１．src : "tomatomata tomatomato" 、pat : "tomatomato"
先ず、先頭をあわせて比較します。
src : tomatomata tomatomato pat : tomatomato"tomatomat" まで同じですが、最後が異なるので先に進むことにします。
ここで、今まで比較したところが検索文字列と重なっていないかを確かめます。すると、"tomat" までが重なっていることが分かります。
tomatomat tomatomatoなので、次が "omato" かどうかを確かめればいいわけです。
src : tomatomata tomatomato pat : tomatomatoやはり違います。ここで、やはり今まで比較したところが検索文字列と重なっていないかを確かめます。"tomat" までは比較された扱いになり、
tomat tomatomatoとなります。次が "omatomato" であるかを確かめればいいわけですね。
src : tomatomata tomatomato pat : tomatomato今度は全く異なっているので、普通に比較を続けます。
src : tomatomata tomatomato pat : tomatomatosrc : tomatomata tomatomato pat : tomatomatoこれで終了です。
２．src : "I could drink cocoa." 、pat : "cocoa"
初めの "I" と " " は普通に進み、次に一部が等しくなる部分が出てきます。
src : I could drink cocoa. pat : cocoaここで、やはり今まで比較したところが検索文字列と重なっていないかを確かめます。
co cocoa先頭から重なるのは当たり前なので除外します。となると、全く重ならないことがわかります。つまり、"I co" の部分までには "cocoa" はないということが分かります。ということで、その次の "uld dri..." から比較を続ければよいことになります。
src : I could drink cocoa. pat : cocoaこれを続けていけば、最終的に
src : I could drink cocoa. pat : cocoaとなります。
これで大体感じはつかめましたか？ まだしっくり来ない人も、何度か試してみると何となく分かってくると思います。
では次に、これをどのようにプログラムすればいいかについて話します。
「今まで比較したところが検索文字列と重なっていないかを確かめる」とはいっても、毎回毎回確かめるのは無駄になります。なので、検索する前に全部確かめて、何らかの表を作っておけばいいでしょう。
では、どのような表を作ればよいのでしょうか？ 最初の例では "omato" から比較し始めればよいと、次の例では "omatomato" から比較し始めればよいといいました。このようなどこから比較し始めればよいかを表にしておくのがいいでしょう。これを ini と呼ぶことにします。
次に、そのような表をどうやって作ればいいかについて考えましょう。例えば "tomato" で考えてみましょう。
今まで比較したところが検索文字列と重なっていればいいわけなので、自分自身と比較していって重なっているか確かめればいいわけですね。先ず、最初の "t" は無視するとして、次の "o" から実際にやってみましょう。
tomato tomato
全く重なりませんね。このような場合は最初から比較しなおすことになるので、これを０とします。
pat : tomato ini : 00
さぁ、どんどんいきましょう。次は "m" です。
tomato tomato
やはり全く重なりません。これは次の "a" も同じです。なので、これまでのところ ini は次のようになります。
pat : tomato ini : 0000
そして、次です。
tomato
tomato
やっと重なりました。"t" までが等しい場合は "omato" と、"to" までが等しい場合は "mato" と等しければいいので、ini は次のようになります。
pat : tomato ini : 000012
これで ini が完成しました。あとは、これを使えば上でやった文字列照合ができるわけです。また、ini の作り方を注意してみれば、上の文字列照合と同じような方法を使っていることも分かります。
この文字列照合法は D.E.Knuth, J.H.Morris, V.R.Pratt によって開発され、その頭文字を取ってＫＭＰ法と呼ばれます。
この文字列照合法の特徴は、src をさかのぼって参照することがないことです。ある程度の速度も重要なのですが、一番重要なのはその src をさかのぼらないことそのものです。このことは、大きなファイルの中から検索するという場合に力を発揮します。
大きなファイルを一気にメモリにロードして比較するのは辛い場合があります。そこで、例えば１０２４バイトずつ読み出してから比較していくとします。このような場合、src をさかのぼることがあれば、１０２４バイト目からさかのぼるときなどは、また前の所をロードしなおさなくてはいけません。こういったことが起こりにくいようにする工夫もあるにはあるのですが（ダブルバッファリング。第４０章参照）、多少面倒です。そこをいくと、ＫＭＰ法は src をさかのぼることがないので、そのようなことに煩わされることはないのです。
では、プログラムを見てみましょう。
| プログラム |
|---|
// Match4.cpp
#include "Match2.h"
static int KMPMatch(const char* src, int nBufSize,
int nFirst, const char* pat);
int main()
{
Match("Match.txt", KMPMatch);
return 0;
}
static int KMPMatch(const char* src, int nBufSize,
int nFirst, const char* pat)
{
// エラーチェック
if(pat[0] == 0 ||
src[nBufSize] != 0 ||
nFirst > nBufSize)
return MATCH_NOTFOUND;
// 開始位置をずらします
src += nFirst;
const int nKMPIniSize = 1024;
int ini[nKMPIniSize];
int i;
int j;
// 表の作成
i = 1;
j = 0;
ini[0] = 0; // 最初は必ず０
while(pat[i] != 0)
{
if(i > nKMPIniSize) // pat が大きすぎる場合
return MATCH_NOTFOUND;
// 同じ場合は比較を続けます
// v i = 4
// pat : tomato
// pat : tomato
// ^ j = 0
// ini : 000012
if(pat[i] == pat[j])
{
// ここは ini[i++] = ++j; でもＯＫ
j++;
ini[i] = j;
i++;
}
// 初めから違う場合、ini を０にして先に進みます
// v i = 1
// pat : tomato
// pat : tomato
// ^ j = 0
// ini : 000012
else if(j == 0)
{
ini[i] = 0;
i++;
}
// 途中まで同じだった場合、
// まさにＫＭＰ法の比較の如く、
// 途中から比較できるか確かめます
// v i = 7
// pat : totetototo
// pat : totetototo
// ^ j = 3
// ini : 0010123232
// ^ j - 1 = 2
else
j = ini[j - 1];
}
// 照合
// やっていることは、表を作るときとほとんど同じです
// 具体的には、ini への代入をなくし、
// ループ条件を変えただけです
i = j = 0;
while(pat[i] != 0 && src[i] != 0)
{
if(src[i] == pat[j])
{
i++; j++;
}
else if(j == 0)
i++;
else
j = ini[j - 1];
}
// pat[j] が０のとき検索成功です
// i が j の分だけ進みすぎているので j を引きます
if(pat[j] == 0)
return i - j + nFirst;
return MATCH_NOTFOUND;
} |
コメントで分厚くなっているので分かりにくいかもしれませんが、それ程長いプログラムではありません。大きなファイルの検索に適用するプログラムなどは、各自自分で作ってみましょう。
では、今回の要点です。
次回は高速文字列照合アルゴリズムについて話したいと思います。それでは。
Last update was done on 2001.4.15
この講座の著作権はロベールが保有しています