今回はテキストから文字列を探索するアルゴリズムを紹介します。テキストファイルから特定の情報を取り出す場合、簡単な方法は文字列の探索を利用することです。文字列の探索は grep, sed, awk などのツールや、Python などのスクリプト言語でサポートされているおなじみの機能です。
これらのツールやプログラミング言語では、「正規表現 (regular expression) 」がサポートされています。正規表現は「文字列のパターンを示した式」のことで、複雑なパターンでも簡単に探索することができます。興味のある方は拙作のページ お気楽 Python プログラミング入門第 4 回 をお読みください。今回はそのような高機能なものではなく、単純なパターンを探索するアルゴリズムを取り上げます。
最初に、力任せに探索する方法と高速な文字列探索アルゴリズムとして有名な「BM 法」を説明します。次に、BM 法のバリエーションである「Horspool のアルゴリズム」と「Sunday のアルゴリズム」を説明します。Sunday のアルゴリズムは BM 法のバリエーションの中でも高速といわれていて、別名 quick search と呼ばれています。
文字列の探索でいちばん簡単な方法は、テキストの先頭から探索する文字列（以降パターンと表記）を重ね合わせていくことです。テキストとパターンの文字を順番に比較し、パターンの末尾文字まで一致すれば探索は成功です。途中で文字が違っていれば探索は失敗です。パターンを重ね合わせる位置を一つずらして再度比較を行います。これを「力まかせの探索 (brute-force searching) 」といいます。
探索の様子を下図に示します。テキストはルイス・キャロル 『不思議の国のアリス』からの一節です。
(1) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(2) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(3) the stick, and made believe to worry it: then Alice dodged behind a
behind
~~^
(4) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(5) the stick, and made believe to worry it: then Alice dodged behind a
behind
~~~~~~
^ : 不一致だった文字 ~ : 一致した文字
図 : 力まかせの探索
探索するパターンは "behind" です。最初はテキストの先頭から比較を始めます。b と t なので探索は失敗です (1)。パターンを 1 文字右へずらして再度比較します。つまり、テキストの中から文字 b を探すことと同じ動作です (2)。そして、文字 b が見つかったならば、次の文字を比較します。
(3) の場合、believe と behind を比較するので、be までは一致します。ところが、次の文字 (l と h) で探索失敗となります。この場合も (4) のように、パターンを 1 文字右へずらして、パターンの先頭から比較していきます。(5) の場合で、パターン behind とテキストが最後まで一致して探索は成功します。
文字列探索アルゴリズムの判断基準として、文字の比較回数を尺度に考えるのが妥当でしょう。力まかせの探索で最悪の場合は、同一文字しかないテキストの中から、それと同じ文字がいくつか続いて最後が違う文字、というパターンを探すことです。たとえば、"aaaaa ..... a" の中から"aaaa ... ab" というパターンを探す場合がそうなります。
aaaaaaaa 2 文字まで一致し 3 文字目で不一致
aab
~~^
aaaaaaaa これが 6 回繰り返される
aab
~~^
........
aaaaaaaa 探索終了、発見できず
aab
~~^
図 : 力まかせの探索で最悪の場合
テキストを n 文字、パターンを m 文字とすると、最悪の場合は m - 1 文字まで比較が成功し、m 文字目で比較が失敗することになります。これを n 回近く繰り返すことになるので、最悪の場合では m * n 回程度の比較が必要になります。上図の例では 8 文字のテキストの中から 3 文字のパターンを見つける場合ですが、探索失敗がわかるまで 18 回の比較が必要になります。
ところで、通常のテキストは文字の種類が十分に多いので、このような最悪の場合が発生することは滅多にありません。最初の例でもわかるように、ほとんどの場合がパターン先頭の文字比較で失敗しているので、66 文字のテキスト中から 6 文字のパターンを見つけるのに、66 回の比較で済んでいます。つまり、テキストの文字数 n よりさほど多くない比較回数で探索できるというわけです。
したがって、力まかせに探索した場合の平均実行時間は、最悪の場合の m * n ではなく、n に比例する程度に収まることが期待できます。ちなみに、実行時間がデータ数に比例するアルゴリズムは「高速」といわれています。一般のテキストにおいて、力まかせの探索は十分に高速なアルゴリズムなのです。このため、高速な文字列探索アルゴリズムはソートなどのアルゴリズムに比べると、その登場はずいぶんと遅くなったようです。
それでは、実際にプログラミングしてみましょう。本ページでは、英文のテキストから文字列を探索することを考えてみます。Python はスクリプト言語なので、文字列の探索はとても簡単にできるのですが、アルゴリズムの勉強ということで、プログラムを作ってみましょう。
リスト : 力任せの探索
# 出力
def output_line(buff, n):
s = n
while s >= 0 and buff[s] != '\n': s -= 1
e = buff.find('\n', n)
print buff[s+1:e]
return e + 1
# 探索
def bf_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
i = 0
while i <= n - m:
j = 0
while j < m:
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見
i = output_line(buff, i)
else:
i += 1
関数 bf_search はテキスト buff からパターン pattern を探索します。テキストの最後には改行文字 ('\n') が付加されているものとします。したがって、テキストの長さ n は len(buff) - 1 で、パターンの長さは m となります。あとは、テキストの先頭からパターンと照合していきます。変数 i がテキストの位置、変数 j がパターンの位置を表します。最初の while ループで、i がテキストの範囲内にある間は探索を続行します。
次の while ループでテキストとパターンを前方から照合します。一致しない場合は break で while ループを脱出します。while ループが終了したあと、j と m が等しければ照合は成功です。関数 output_line でパターンと一致した行を出力します。不一致の場合は i の値を一つ増やして探索を繰り返します。
関数 output_line は前後の改行文字を探して、1 行を切り出して出力します。変数 s が先頭の改行文字の位置、変数 e が後ろの改行文字の位置を表します。あとは、buff[s+1:e] で 1 行を切り出して print で出力します。最後に、次の行頭の位置 e + 1 を返します。
プログラムの評価は BM 法と一緒に行います。
テキストを n 文字、パターンを m 文字とすると、力まかせの探索では平均実行時間は最悪の場合 m * n に比例しますが、実際には n に比例する程度に収まります。参考文献 [3] によると、 『しかし 1970 年に、S.A.Cook が「最悪の場合でも文字を m + n に比例した回数の比較をするだけで実行できる文字列探索アルゴリズムが存在する」ということを理論的に証明しました。』 とのことです。
m * n が m + n になるのだから画期的な進歩ですね。これに基づいて KMP (Kunth - Morris - Pratt：クヌース - モリス - プラット) 法が開発されました。ところが、KMP 法のアルゴリズムは大変優れているのですが、実をいうと実行速度はそれほど速くないのです。これに対して、1977 年に発表された BM (Boyer - Moore :ボイヤー - ムーア) 法 [*1] は、アルゴリズムが優れていて実行速度も速いという大変実用的な方法です。
BM 法は現時点で最も高速な文字列探索アルゴリズムといわれていますが、一般的なテキストの場合は、BM 法の改良版である Horspool のアルゴリズム (R. N. Horspool, 1980 年) や Sunday のアルゴリズム (D. M. Sunday, 1990 年) の方が速くなるようです。とくに、Sunday のアルゴリズムは別名 quick search と呼ばれていて、BM 法のバリエーションの中でも高速だといわれています。どのくらい速くなるのか、実際にプログラムを作って確かめてみましょう。
BM 法の特徴は、パターンを末尾から先頭に向かって比較していくことです。それでは、BM 法を使った探索の様子を見ながら説明していきましょう。
(1) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(2) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
図 : BM 法による文字列の探索（その１）
まず、テキストの先頭とパターンの先頭を重ね合わせることは、今までと同じです。最初に、パターンの末尾文字 d とテキストの 6 文字目 t を比較します。当然不一致なのでパターンを動かしますが、このとき不一致になったテキストの文字 t に着目します。t はパターン behind には含まれていません。パターンが t と重なっている間は一致するはずがないので、t と重ならないようにパターンを一気に 6 文字分移動します (2)。
このように、BM 法では 1 回の文字比較でいっきに m 文字分パターンを動かすことができるので、うまくいけば n / m 程度の比較回数で探索を終了することができます。実際のテキストは文字種類が十分に多いので、これに近い状態を期待することができます。これが BM 法の速さの仕組みです。
パターン長 m が長いとより高速に探索できるように思われますが、不一致になった文字がパターンに含まれていると、パターンをいっきに m 文字移動することはできなくなります。したがって、実際には n / m ほど高速化できるわけではありません。それでも力まかせの探索よりも高速に動作することが期待できます。
次に、不一致になった文字がパターンに含まれている場合を考えてみましょう。
(3) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(4) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
図 : BM 法による文字列の探索（その２）
(3) の状態で、d と i を比較して不一致になりました。i はパターンに含まれる文字です。この場合、両者が重なる位置までパターンを移動することができます。この場合、2 文字分移動すれば i が重なります。すると、(4) の状態になり、再びパターン末尾から比較を行います。
今の例はパターンの末尾文字で不一致が起きた場合です。次は、末尾文字以外の場所で不一致になる場合を考えてみましょう。
(5) the stick, and made believe to worry it: then Alice dodged behind a
behind
^~
(6) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(7) the stick, and made believe to worry it: then Alice dodged behind a
behind
~~~~~~
図 : BM 法による文字列の探索（その３）
(5) の状態では、末尾文字 d は一致していますが、一つ前の文字 n と e で不一致になります。この場合も不一致となった文字に注目します。e はパターンの中にあるので、その文字と重ね合わせるようにパターンを 3 文字分移動します。すると、(6) の状態になります。パターン末尾から照合すると、今度は e と d で不一致になります。不一致文字 e に注目して、パターンを4 文字移動して e に合わせると、(7) の状態になります。ここで、パターン behind がすべて一致するので探索成功となります。
このように、BM 法は不一致になったテキスト側の文字に注目してパターンを移動していきます。移動量は、あらかじめ計算しておいてテーブルに格納しておきます。次の図を見てください。
b e h i n d a : 6 e : 4 i : 2
b : 5 f : 6 j : 6
移動量 5 4 3 2 1 c : 6 g : 6 k : 6
d : 6 h : 3 l : 6 ....
[移動量テーブル]
図 : 移動量テーブルの作成
パターンの長さを m とすると、パターンに含まれない文字は m を登録します。移動量は先頭文字が m - 1 となり、あとは順番に 1 ずつ引いた値を書き込んでいきます。同一文字が複数ある場合は、上書きして最も右側の文字の値になります。末尾文字の移動量は 0 ではなく m になります。ご注意ください。
簡単な例を示しましょう。次の図を見てください。
* --------> *
(1) 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
---------------------------------------
A l i c e d o d g e d b e h i n d
b e h i n d
* ----> *
(2) 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
---------------------------------------
A l i c e d o d g e d b e h i n d
b e h i n d
* ----> *
(3) 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
---------------------------------------
A l i c e d o d g e d b e h i n d
b e h i n d
図 : パターンの移動
テキスト側の探索位置を * で示しています。(1) は 5 番目で不一致になりました。テキスト側の文字はパターンに含まれていないので、5 + 6 = 11 番目に探索位置を移動します。(2) は 11 番目から照合を開始して、10 番目で不一致になりました。テキスト側の文字 e はパターンに含まれているので、テーブルから移動量 4 を求めて探索位置に加算します。すると、探索位置は 10 + 4 = 14 になります。これで、パターンを 3 文字分移動させて e の位置に合わせることができます。(3) も同様に、14 + 4 = 18 になります。そして、18 番目から照合を開始して探索成功となります。
このように、パターンの移動は不一致になったテキストの位置に移動量を加えるだけです。とても簡単なのですが、一つだけ注意点があります。次の図を見てください。
*
(1) 0 1 2 3 4 5 6 7 8 9 0
---------------------
x x x c d c d e x x x
a b c d e
*
(2) 0 1 2 3 4 5 6 7 8 9 0
---------------------
x x x c d c d e x x x
a b c d e
*
(3) 0 1 2 3 4 5 6 7 8 9 0
---------------------
x x x c d c d e x x x
a b c d e
図 : 後戻りする場合
(1) の場合、7 番目から照合を開始して、4 番目で不一致になりました。不一致になった文字は d なので、移動量は 1 になります。すると、4 + 1 = 5 となり、探索位置が後戻りしてしまいます。この場合、(3) のように探索位置を強制的に +1 して 8 番目にします。
この処理は、移動量と不一致になるまで照合した文字数を比較して、大きい方の値を選ぶことで実現できます。(2) の場合、移動量は 1 で比較した文字数は 4 です。したがって、探索位置は 4 + 4 = 8 になります。これで探索が後戻りすることはありません。
ところで、今まで説明した方法は BM 法の半分だけを利用した簡略版です。このままでは最悪の場合 m * n に比例した比較回数が必要になります。力まかせとは逆の場合、"aaaa....aaaa"の中から"baaa....aaa"を探すことが最悪になります。残りの半分を使えば、最悪の場合でもテキストの文字数 n に比例する程度の実行時間に収まるのですが、この部分は処理が複雑なため、実行速度にほとんど貢献しないのです。したがって、一般のテキストで使用する場合には、このような簡略版で十分だといわれています。
それではプログラムを作りましょう。次のリストを見てください。
リスト : BM (Boyer - Moore) 法
CSIZE = 256 # byte 単位で比較を行う
# 移動量テーブルの作成
def make_bm_table(pattern, size):
bm_table = [size] * CSIZE
size -= 1
for i in xrange(size):
bm_table[ord(pattern[i])] = size - i
return bm_table
# BM 法による探索
def bm_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
bm_table = make_bm_table(pattern, m)
i = m - 1
while i < n:
j = m - 1
while j >= 0:
if buff[i] != pattern[j]: break
i -= 1
j -= 1
if j < 0:
# 発見
i = output_line(buff, i + 1) + m - 1
else:
i += max(bm_table[ord(buff[i])], m - j)
関数 make_bm_table は移動量テーブルを作成して返します。引数 pattern がパターンを、size がパターンの長さを表します。今回のプログラムはバイト単位で比較を行うので、テーブルの大きさは 256 (CSIZE) となります。
最初に、大きさが 256 個の配列 bm_table を作成します。要素の値は size になります。あとは、for ループでパターンに含まれる文字の移動量を bm_table に書き込みます。最後の文字は含めないので、最初に size を -1 していることに注意してください。したがって、書き込む移動量は size - i となります。最後に bm_table を返します。
関数 bm_search の引数 buff がテキスト、pattern がパターンです。最初に、テキストとパターンの長さを求めて変数 n と m にセットします。テキストの最後には改行文字が付いていることを想定しているので、テキストの長さは len(buff) - 1 としています。そして、make_bm_table で移動量テーブルを作成します。
変数 i がテキストの探索位置を表します。i はパターンの末尾文字の位置 m - 1 に初期化します。そして while ループで、i がテキストの範囲内であれば pattern と照合します。変数 j がパターンの位置を表していて、末尾文字の位置 m - 1 に初期化します。あとは、後方から 1 文字ずつ比較していき、不一致であれば break で while ループを脱出します。
while ループが終了したあと、j が 0 より小さい場合は pattern が全て一致しました。関数 output_line で一致した行を表示します。out_line は次の行の先頭位置を返すので、その返り値に m - 1 を加えます。そうでなければ、不一致だった文字 buff[i] の移動量を bm_table から求め、パターンと照合した文字数 m - j と比較します。そして、大きいほうの値を i に加算します。これでパターンを移動させることができます。
それでは、力任せの探索と BM 法の実行速度を比較してみましょう。テストプログラムを示します。
# テスト
buff = sys.stdin.read()
for func in [bf_search, bm_search]:
s = time.clock()
func(buff, sys.argv[1])
e = time.clock()
print e - s
標準入力 (stdin) から read でデータを一気に読み込みます。read の返り値は文字列になります。パターンはコマンドラインで指定します。テストデータは Canterbury Corpus で配布されている The Canterbury Corpus の中の alice29.txt を使用させていただきました。alice29.txt (152,089 byte) の中から "behind" を探した結果を示します。
表 : 実行結果
: 時間 (秒) : 比較回数
-------------------------------
力任せ : 0.133 : 149,938
BM 法 : 0.046 : 30,168
alice29.txt (152,089 byte) から behind を探索
テキストの長さ 148,480
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
力任せの探索よりも BM 法の方が高速ですね。BM 法の効果は十分に出ていると思います。比較回数は文字を比較した回数です。テキストモードでファイルを読み込んでいるため、テキストの長さは 148,480 になります。力任せの探索の場合、比較回数はテキストの大きさとほぼ同じになりました。BM 法の場合、うまくいけば 148480 / 6 = 24747 回くらいの比較ですむはずですが、実際には 30178 回になりました。それでも、力任せの探索に比べれば比較回数は激減しています。これが BM 法の速さの秘密なのです。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
Horspool のアルゴリズムは、1980 年に R. N. Horspool が発表した BM 法の改良版です。ここでは BMH 法と呼ぶことにしましょう。BMH 法のポイントは、パターンとの比較で不一致になったときに移動量を求めるところです。BM 法は不一致になったテキストの文字から移動量を求めました。ところが BMH 法はそうではなく、パターンの末尾と同じ位置にあるテキストの文字から移動量を求めます。つまり、パターンのどこで不一致になったとしても、移動量はパターン末尾と同じ位置にあるテキスト文字から求めるのです。次の図を見てください。
(1) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(2) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(3) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
(4) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
図 : BMH 法による文字列の探索（その１）
(1) と (3) のように、パターンの末尾文字が不一致の場合は、今までの BM 法と同じです。(1) の場合、テキストの文字 t はパターンに含まれていないので、パターンを 6 文字移動させることができます。これが (2) の状態です。(3) の場合、テキストの文字 i はパターンに含まれているので、パターンを 2 文字移動して (4) の状態になります。
次は、パターンの末尾以外で不一致だった場合です。
(5) the stick, and made believe to worry it: then Alice dodged behind a
behind
^~
(6) the stick, and made believe to worry it: then Alice dodged behind a
behind
図 : BMH 法による文字列の探索（その２）
(5) の状態では、末尾文字 d は一致しますが、一つ前の文字 n と e が不一致です。BMH 法では、この場合も末尾文字の位置に注目します。d はパターンのほかの場所には無いので、この場合も 6 文字移動して (6) の状態になります。もし、ほかの場所にも現れる場合、その文字と重ね合わせるようにパターンを移動します。次の例を見てください。
重ね合わせる
|
and made believe ==> and made believe
believe believe
^~ ^
図 : 末尾文字が複数ある場合の移動
上図のようにパターンが believe の場合、末尾文字の e が複数含まれています。移動量の計算は BM 法と同じです。この場合、文字 e の移動量は 2 になります。したがって、パターンを 2 文字移動すると、テキストとパターンの e を重ね合わせることができます。
また、BMH 法はパターンが後戻りすることはありません。次の図を見てください。
*
(1) 0 1 2 3 4 5 6 7 8 9 0
---------------------
x x x c d c d e x x x
a b c d e
(2) 0 1 2 3 4 5 6 7 8 9 0
---------------------
x x x c d c d e x x x
a b c d e
BM 法は後戻りする
(3) 0 1 2 3 4 5 6 7 8 9 0 1 2
-------------------------
x x x c d c d e x x x x x
a b c d e
BMH 法は後戻りしない
図 : BMH 法のパターン移動
(1) の場合、7 番目から照合を開始して、4 番目で不一致になりました。不一致になった文字は d なので、BM 法の場合は (2) のように後戻りしてしまいます。BMH 法の場合、パターンの位置に移動量を加算するだけでパターンを移動することができます。文字 e の移動量は 5 なので、パターンの先頭位置は 3 + 5 = 8 番目まで移動することができます。移動量は 0 にはならないので、パターンが後戻りすることはありません。
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : BMH 法 (Horspool のアルゴリズム)
def bmh_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
bm_table = make_bm_table(pattern, m)
i = 0
while i <= n - m:
j = m - 1
while j >= 0:
if buff[i + j] != pattern[j]: break
j -= 1
if j < 0:
# 発見
i = output_line(buff, i)
else:
i += bm_table[ord(buff[i + m - 1])]
関数 bmh_search の引数 buff がテキスト、pattern がパターンです。最初に、テキストとパターンの長さを求めて変数 n と m にセットします。テキストの最後には改行文字が付いていることを想定しているので、テキストの長さは len(buff) - 1 としています。そして、make_bm_table で移動量テーブルを作成します。
変数 i がテキスト上のパターンの先頭位置を表します。i は 0 に初期化します。そして while ループで、i がテキストの範囲内であれば pattern と照合します。変数 j がパターンの位置を表していて、末尾文字の位置 m - 1 に初期化します。あとは、後方から 1 文字ずつ比較していきます。比較するテキストの位置は i + j になります。不一致であれば break で while ループを脱出します。
while ループが終了したあと、j が 0 より小さい場合は pattern が全て一致しました。関数 output_line で一致した行を表示します。そうでなければ、パターンの末尾に対応する文字 buff[i + m - 1] の移動量を bm_table から求めて i に加算します。
プログラムの評価は Sunday のアルゴリズムと一緒に行います。
Sunday のアルゴリズムは、1990 年に D. M. Sunday が発表した BM 法の改良版です。ここでは quick search と呼ぶことにしましょう。quick search は BMH 法とよく似ている方法です。違いは移動量を求めるところです。パターンが不一致になったとき、BMH 法はパターンの末尾と同じ位置にあるテキストの文字から移動量を求めます。ところが quick search の場合は、その右隣にあるテキストの文字から移動量を求めるのです。次の図を見てください。
*
(1) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
*
(2) the stick, and made believe to worry it: then Alice dodged behind a
behind
^
*
(3) the stick, and made believe to worry it: then Alice dodged behind a
behind
~~^
図 : quick search よる文字列の探索
quick search はパターンの先頭から 1 文字ずつ照合していきます。(1) の場合、先頭文字で照合は失敗します。この場合、パターン behind の右隣に位置する文字 a に着目します。a はパターン behind には含まれていません。パターンが a と重なっている間は一致するはずがないので、a と重ならないようにパターンを一気に 7 文字分移動させることができます。
(2) の場合、パターンの先頭で照合失敗したので、(1) と同様にパターンの右隣の文字 i に着目します。i はパターンに含まれている文字です。この場合、両者が重なる位置までパターンを移動することができます。3 文字分移動すれば (3) のように i が重なります。
ここで、どちらの場合もパターンの移動量は BM 法に比べて 1 つ多くなることに注意してください。これが quick search の速さの秘密です。移動量は 1 つ多くなるだけですが、これが積み重なって BM 法よりも速くなるのです。
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : quick search (Horspool のアルゴリズム)
# 移動量テーブルの作成
def make_qs_table(pattern, size):
qs_table = [size + 1] * CSIZE
for i in xrange(size):
qs_table[ord(pattern[i])] = size - i
return qs_table
# quick search による探索
def qs_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
qs_table = make_qs_table(pattern, m)
i = 0
while i <= n - m:
j = 0
while j < m:
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見
i = output_line(buff, i)
else:
i += qs_table[ord(buff[i + m])]
関数 make_qs_table は移動量テーブルを作成して返します。引数 pattern がパターンを、size がパターンの長さを表します。最初に、大きさが 256 個の配列 qs_table を作成します。要素の値は size + 1 になります。あとは、for ループでパターンに含まれる文字の移動量を qs_table に書き込みます。BM 法とは違って、最後の文字も含めることに注意してください。書き込む移動量は size - i となります。最後に qs_table を返します。
関数 qs_search の引数 buff がテキスト、pattern がパターンです。最初に、テキストとパターンの長さを求めて変数 n と m にセットします。テキストの最後には改行文字が付いていることを想定しているので、テキストの長さは len(buff) - 1 としています。
quick search の場合、移動量を求めるときテキストの範囲外にアクセスすることがあります。たとえば、テキストの最後の m 文字とパターン m 文字を比較した場合、次の移動量を求めるためテキスト末尾の次の文字が必要になります。ここで、テキストの範囲外をアクセスしてしまうのです。今回のプログラムは、最後の改行文字が番兵の役割をはたしているので正常に動作します。ご注意くださいませ。
変数 i がテキスト上のパターンの先頭位置を表します。i は 0 に初期化します。そして while ループで、i がテキストの範囲内であれば pattern と照合します。変数 j がパターンの位置を表します。quick search は BM 法とは違ってパターンの末尾から照合する必要はありません。quick search の場合、パターンのどの位置から照合してもかまわないのですが、このプログラムでは先頭から照合することにします。変数 j は 0 に初期化します。あとは、1 文字ずつ比較していきます。比較するテキストの位置は i + j になります。不一致であれば break で while ループを脱出します。
while ループが終了したあと、j が m と等しい場合は pattern と全て一致しました。関数 output_line で一致した行を表示します。そうでなければ、パターンの次に位置するテキストの文字 buff[i + m] の移動量を qs_table から求めて i に加算します。このように、quick search のプログラムは簡単に実装することができます。
それでは、プログラムの実行速度を比較してみましょう。
表 : 実行結果
: 時間 (秒) : 比較回数
-------------------------------
力任せ : 0.133 : 149,938
BM 法 : 0.046 : 30,168
BMH 法 : 0.041 : 29,728
quick : 0.033 : 25,094
alice29.txt (152,089 byte) から behind を探索
テキストの長さ 148,480
実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
quick search が最も速くなりました。BM 法に比べ、比較回数は 17 % 減少しています。quick search の効果はとても高いですね。BMH 法は quick search より遅くなりましたが、それでも BM 法よりは高速で、比較回数も減少しています。BMH 法の効果も十分に出ていると思います。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
ところで、BM 法で日本語 (多バイト文字) を含むテキストを探索すると、ミスマッチングを起こすことがあります。たとえば、Shift_JIS の場合を考えてみましょう。Shift_JIS は、Windows などで使われている日本語コードです。Shift_JIS については Shift_JIS - Wikipedia が参考になると思います。
たとえば、アBC と ABC を考えてみましょう。
ABC 41 42 43
アBC 83 41 42 43
^^
2 バイトコードの途中からマッチングする
図 : ミスマッチングの例
アは Shift_JIS で 0x8341、第 2 バイトがアスキーコード A と同じです。アBC から ABC を検索すると、第 2 バイトの A から探索成功となってしまいます。
いちばん簡単な解決方法は、1 バイトずつの比較をやめて 1 文字ずつ比較することです。ただし、この方法では文字列を末尾から比較する BM 法に適用することはできません。また、力まかせの探索で使うにしても、比較のたびに文字種別のチェックを行うと、実行速度が遅くなる恐れがあります。
実行速度を低下させないためには、探索が成功したあとで正常にマッチングしているか確認したほうがよいでしょう。このとき、先頭から 1 文字ずつチェックしていってもよいのですが、ここでは他の方法を紹介します。次の図を見てください。
a b c ａ ｂ ｃ ア B C
61 62 63 82 81 82 82 82 83 83 41 42 43
^^ ~~ ~~ ~~ ~~ ~~ ~~ ~~ 41 42 43
A B C
~~ : iskanji で True となる文字
^^ : iskanji で False となる文字
図 : 文字種別を判断する方法
Shift_JIS の第 1 バイト (0x81 - 0x9f, 0xe0 - 0xfc) を判定する関数 iskanji を定義します。iskanji が False になる文字は、アスキーコードか Shift_JIS の第 2 バイトのいずれかです。どちらにしても、そこで文字が確実に完結しています。探索成功した位置から iskanji が False になる文字を前に遡って探すと、その間には Shift_JIS コードしか存在しません。したがって、その間のバイト数は偶数になるはずです。もしも奇数であれば、それは第 2 バイトから探索成功した場合です。
上図を見てください。ABC はアの第 2 バイトからマッチングしています。そこから前方向に iskanji が FALSE になる文字を探すと c が見つかります。探索成功した位置から c までの間には 7 バイトあるので、この場合は Shift_JIS の途中からマッチングしたことがわかります。
この方法は、探索するテキストには Shift_JIS に違反する文字は含まれていない、ということを前提にしているので、絶対的な方法ではありません。しかし、通常のテキストではこの前提が崩れることはほとんどないと思います。
プログラムは次のようになります。
リスト : Shift_JIS への対応 (1)
# Shift_JIS の第 1 バイトか
def iskanji(c):
return 0x81 <= c <= 0x9f or 0xe0 <= c <= 0xfc
# Shift_JIS のミスマッチをチェック
def check(buff, n):
i = n - 1
while i >= 0 and iskanji(ord(buff[i])): i -= 1
return (n - i) & 1
探索成功した位置からテキストを前方向に遡って、iskanji が True となる文字をスキップしていきます。探索成功した位置の文字はチェックする必要がないので、変数 i は n - 1 に初期化しています。行の先頭には改行コードがあるので、ここで iskanji が必ず False になります。マッチングした行が 1 行目の場合は i >= 0 でチェックします。n - i はその間にある文字数に 1 加えた値になるので、その値が奇数であれば正常にマッチングしたことになります。
関数 check を使うと、探索本体のプログラムは次のようになります。
リスト : Shift_JIS への対応 (2)
def qs_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
qs_table = make_qs_table(pattern, m)
i = 0
while i <= n - m:
j = 0
while j < m:
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見
if check(buff, i):
i = output_line(buff, i)
else:
i += 1
else:
i += qs_table[ord(buff[i + m])]
パターンを発見したら、関数 check を呼び出してミスマッチングしていないかチェックします。正しくマッチングしていたら output_line で行を表示します。そうでなければミスマッチングなので、次の文字から探索を開始するように変数 i に 1 を加えます。
他のコード (JIS, EUC-JP) については Fussy さんの Fussy's HOMEPAGE にある文字列の検索 -2- がとても参考になります。Fussy さんに感謝いたします。
# coding: shift_jis
#
# search.py : 文字列の探索
#
# Copyright (C) 2007 Makoto Hiroi
#
import sys, time
# 出力
def output_line(buff, n):
s = n
while s >= 0 and buff[s] != '\n': s -= 1
e = buff.find('\n', n)
print buff[s+1:e]
return e + 1
# 力任せの探索
def bf_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
i = 0
while i <= n - m:
j = 0
while j < m:
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見した
i = output_line(buff, i) + m - 1
else:
i += 1
# Boyer - Moore 法
CSIZE = 256
def make_bm_table(pattern, size):
bm_table = [size] * CSIZE
size -= 1
for i in xrange(size):
bm_table[ord(pattern[i])] = size - i
return bm_table
#
def bm_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
bm_table = make_bm_table(pattern, m)
i = m - 1
while i < n:
j = m - 1
while j >= 0:
if buff[i] != pattern[j]: break
i -= 1
j -= 1
if j < 0:
# 発見
i = output_line(buff, i + 1)
else:
i += max(bm_table[ord(buff[i])], m - j)
# Horspool のアルゴリズム
def bmh_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
bm_table = make_bm_table(pattern, m)
i = 0
while i <= n - m:
j = m - 1
while j >= 0:
if buff[i + j] != pattern[j]: break
j -= 1
if j < 0:
# 発見
i = output_line(buff, i)
else:
i += bm_table[ord(buff[i + m - 1])]
# Quick Search (Sunday のアルゴリズム)
def make_qs_table(pattern, size):
qs_table = [size + 1] * CSIZE
for i in xrange(size):
qs_table[ord(pattern[i])] = size - i
return qs_table
def qs_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
qs_table = make_qs_table(pattern, m)
i = 0
while i <= n - m:
j = 0
while j < m:
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見
i = output_line(buff, i)
else:
i += qs_table[ord(buff[i + m])]
# テスト
buff = sys.stdin.read()
for func in [bf_search, bm_search, bmh_search, qs_search]:
s = time.clock()
print func(buff, sys.argv[1])
e = time.clock()
print e - s
# coding: shift_jis
#
# search1.py : 文字列の探索 (Shift_JIS への対応)
#
# Copyright (C) 2007 Makoto Hiroi
#
import sys
# Shift_JIS の第 1 バイトか
def iskanji(c):
return 0x81 <= c <= 0x9f or 0xe0 <= c <= 0xfc
# Shift_JIS のミスマッチをチェック
def check(buff, n):
i = n - 1
while i >= 0 and iskanji(ord(buff[i])): i -= 1
return (n - i) & 1
# 出力
def output_line(buff, n):
s = n
while s >= 0 and buff[s] != '\n': s -= 1
e = buff.find('\n', n)
print buff[s+1:e]
return e + 1
# Quick Search
CSIZE = 256 # byte 単位で探索
def make_qs_table(pattern, size):
qs_table = [size + 1] * CSIZE
for i in xrange(size):
qs_table[ord(pattern[i])] = size - i
return qs_table
def qs_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
qs_table = make_qs_table(pattern, m)
i = 0
while i <= n - m:
j = 0
while j < m:
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見
if check(buff, i):
i = output_line(buff, i)
else:
i += 1
else:
i += qs_table[ord(buff[i + m])]
# テスト
pattern = sys.argv[1]
buff = sys.stdin.read()
qs_search(buff, pattern)