はじめに
今回はテキストから文字列を探索するアルゴリズムを紹介します。テキストファイルから特定の情報を取り出す場合、簡単な方法は文字列の探索を利用することです。文字列の探索は grep, sed, awk などのツールや、Python などのスクリプト言語でサポートされているおなじみの機能です。
これらのツールやプログラミング言語では「正規表現 (regular expression)」がサポートされています。正規表現は「文字列のパターンを示した式」のことで、複雑なパターンでも簡単に探索することができます。興味のある方は拙作のページ 新・お気楽 Python プログラミング入門第 4 回 をお読みください。今回はそのような高機能なものではなく、単純なパターンを探索するアルゴリズムを取り上げます。
最初に、力任せに探索する方法と高速な文字列探索アルゴリズムとして有名な「BM 法」を説明します。次に、BM 法のバリエーションである「Horspool のアルゴリズム」と「Sunday のアルゴリズム」を説明します。Sunday のアルゴリズムは BM 法のバリエーションの中でも高速といわれていて、別名 quick search と呼ばれています。
●力まかせの探索
文字列の探索でいちばん簡単な方法は、テキストの先頭から探索する文字列 (以降パターンと表記) を重ね合わせていくことです。テキストとパターンの文字を順番に比較し、パターンの末尾文字まで一致すれば探索は成功です。途中で文字が違っていれば探索は失敗です。パターンを重ね合わせる位置を一つずらして再度比較を行います。これを「力まかせの探索 (brute-force searching)」といいます。
探索の様子を下図に示します。テキストはルイス・キャロル 『不思議の国のアリス』からの一節です。
探索するパターンは "behind" です。最初はテキストの先頭から比較を始めます。b と t なので探索は失敗です (1)。パターンを 1 文字右へずらして再度比較します。つまり、テキストの中から文字 b を探すことと同じ動作です (2)。そして、文字 b が見つかったならば、次の文字を比較します。
(3) の場合、believe と behind を比較するので、be までは一致します。ところが、次の文字 (l と h) で探索失敗となります。この場合も (4) のように、パターンを 1 文字右へずらして、パターンの先頭から比較していきます。(5) の場合で、パターン behind とテキストが最後まで一致して探索は成功します。
文字列探索アルゴリズムの判断基準として、文字の比較回数を尺度に考えるのが妥当でしょう。力まかせの探索で最悪の場合は、同一文字しかないテキストの中から、それと同じ文字がいくつか続いて最後が違う文字、というパターンを探すことです。たとえば、"aaaaa ..... a" の中から"aaaa ... ab" というパターンを探す場合がそうなります。
テキストを 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 法と一緒に行います。
●BM (Boyer-Moore) 法
テキストを 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 法のバリエーションの中でも高速だといわれています。どのくらい速くなるのか、実際にプログラムを作って確かめてみましょう。
[*1] これとは独立に Gosper も考案したので Boyer-Moore-Gosper 法と呼ばれることもあります。
●BM 法の仕組み
BM 法の特徴は、パターンを末尾から先頭に向かって比較していくことです。それでは、BM 法を使った探索の様子を見ながら説明していきましょう。
まず、テキストの先頭とパターンの先頭を重ね合わせることは、今までと同じです。最初に、パターンの末尾文字 d とテキストの 6 文字目 t を比較します。当然不一致なのでパターンを動かしますが、このとき不一致になったテキストの文字 t に着目します。t はパターン behind には含まれていません。パターンが t と重なっている間は一致するはずがないので、t と重ならないようにパターンを一気に 6 文字分移動します (図 3 (2))。
このように、BM 法では 1 回の文字比較でいっきに m 文字分パターンを動かすことができるので、うまくいけば n / m 程度の比較回数で探索を終了することができます。実際のテキストは文字種類が十分に多いので、これに近い状態を期待することができます。これが BM 法の速さの仕組みです。
パターン長 m が長いとより高速に探索できるように思われますが、不一致になった文字がパターンに含まれていると、パターンをいっきに m 文字移動することはできなくなります。したがって、実際には n / m ほど高速化できるわけではありません。それでも力まかせの探索よりも高速に動作することが期待できます。
次に、不一致になった文字がパターンに含まれている場合を考えてみましょう。
(3) の状態で、d と i を比較して不一致になりました。i はパターンに含まれる文字です。この場合、両者が重なる位置までパターンを移動することができます。この場合、2 文字分移動すれば i が重なります。すると、(4) の状態になり、再びパターン末尾から比較を行います。
今の例はパターンの末尾文字で不一致が起きた場合です。次は、末尾文字以外の場所で不一致になる場合を考えてみましょう。
(5) の状態では、末尾文字 d は一致していますが、一つ前の文字 n と e で不一致になります。この場合も不一致となった文字に注目します。e はパターンの中にあるので、その文字と重ね合わせるようにパターンを 3 文字分移動します。すると、(6) の状態になります。パターン末尾から照合すると、今度は e と d で不一致になります。不一致文字 e に注目して、パターンを4 文字移動して e に合わせると (7) の状態になります。ここで、パターン behind がすべて一致するので探索成功となります。
●パターンの移動
このように、BM 法は不一致になったテキスト側の文字に注目してパターンを移動していきます。移動量は、あらかじめ計算しておいてテーブルに格納しておきます。次の図を見てください。
パターンの長さを m とすると、パターンに含まれない文字は m を登録します。移動量は先頭文字が m - 1 となり、あとは順番に 1 ずつ引いた値を書き込んでいきます。同一文字が複数ある場合は、上書きして最も右側の文字の値になります。末尾文字の移動量は 0 ではなく m になります。ご注意ください。
簡単な例を示しましょう。次の図を見てください。
テキスト側の探索位置を * で示しています。(1) は 5 番目で不一致になりました。テキスト側の文字はパターンに含まれていないので、5 + 6 = 11 番目に探索位置を移動します。(2) は 11 番目から照合を開始して、10 番目で不一致になりました。テキスト側の文字 e はパターンに含まれているので、テーブルから移動量 4 を求めて探索位置に加算します。
すると、探索位置は 10 + 4 = 14 になります。これで、パターンを 3 文字分移動させて e の位置に合わせることができます。(3) も同様に、14 + 4 = 18 になります。そして、18 番目から照合を開始して探索成功となります。
このように、パターンの移動は不一致になったテキストの位置に移動量を加えるだけです。とても簡単なのですが、一つだけ注意点があります。次の図を見てください。
(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 法のプログラム
それではプログラムを作りましょう。次のリストを見てください。
リスト : 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() で一致した行を表示します。output_line() は次の行の先頭位置を返すので、その返り値に m - 1 を加えます。そうでなければ、不一致だった文字 buff[i] の移動量を bm_table から求め、パターンと照合した文字数 m - j と比較します。そして、大きいほうの値を i に加算します。これでパターンを移動させることができます。
●実行結果
それでは、力任せの探索と BM 法の実行速度を比較してみましょう。テストプログラムを示します。
リスト : テスト
buff = sys.stdin.read()
for func in [bf_search, bm_search]:
s = time.time()
func(buff, sys.argv[1])
e = time.time()
print e - s
標準入力 (stdin) から read でデータを一気に読み込みます。read の返り値は文字列になります。パターンはコマンドラインで指定します。テストデータは Canterbury Corpus で配布されている The Large Corpus の world192.txt (2,473,400 byte) を使用させていただきました。この中から "behind" を探した結果を示します。
表 : 実行結果 (時間 秒)
: 時間 : 比較回数
------+-------+-----------
力任せ: 0.778 : 2,499,956
ＢＭ法: 0.320 : 487,109
実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
力任せの探索よりも BM 法の方が高速ですね。BM 法の効果は十分に出ていると思います。比較回数は文字を比較した回数です。力任せの探索の場合、比較回数はテキストの大きさとほぼ同じになりました。BM 法の場合、うまくいけば 2,473,400 / 6 = 412,234 回くらいの比較ですむはずですが、実際には 487,109 回になりました。それでも、力任せの探索に比べれば比較回数は激減しています。これが BM 法の速さの秘密なのです。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●Horspool のアルゴリズム
Horspool のアルゴリズムは、1980 年に R. N. Horspool が発表した BM 法の改良版です。ここでは BMH 法と呼ぶことにしましょう。BMH 法のポイントは、パターンとの比較で不一致になったときに移動量を求めるところです。BM 法は不一致になったテキストの文字から移動量を求めました。ところが BMH 法はそうではなく、パターンの末尾と同じ位置にあるテキストの文字から移動量を求めます。つまり、パターンのどこで不一致になったとしても、移動量はパターン末尾と同じ位置にあるテキスト文字から求めるのです。次の図を見てください。
(1) と (3) のように、パターンの末尾文字が不一致の場合は、今までの BM 法と同じです。(1) の場合、テキストの文字 t はパターンに含まれていないので、パターンを 6 文字移動させることができます。これが (2) の状態です。(3) の場合、テキストの文字 i はパターンに含まれているので、パターンを 2 文字移動して (4) の状態になります。
次は、パターンの末尾以外で不一致だった場合です。
(5) の状態では、末尾文字 d は一致しますが、一つ前の文字 n と e が不一致です。BMH 法では、この場合も末尾文字の位置に注目します。d はパターンのほかの場所には無いので、この場合も 6 文字移動して (6) の状態になります。もし、ほかの場所にも現れる場合、その文字と重ね合わせるようにパターンを移動します。次の例を見てください。
上図のようにパターンが believe の場合、末尾文字の e が複数含まれています。移動量の計算は BM 法と同じです。この場合、文字 e の移動量は 2 になります。したがって、パターンを 2 文字移動すると、テキストとパターンの e を重ね合わせることができます。
また、BMH 法はパターンが後戻りすることはありません。次の図を見てください。
(1) の場合、7 番目から照合を開始して、4 番目で不一致になりました。不一致になった文字は d なので、BM 法の場合は (2) のように後戻りしてしまいます。BMH 法の場合、パターンの位置に移動量を加算するだけでパターンを移動することができます。文字 e の移動量は 5 なので、パターンの先頭位置は 3 + 5 = 8 番目まで移動することができます。移動量は 0 にはならないので、パターンが後戻りすることはありません。
●BMH 法のプログラム
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : 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 にセットします。そして、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 のアルゴリズム
Sunday のアルゴリズムは、1990 年に D. M. Sunday が発表した BM 法の改良版です。ここでは quick search と呼ぶことにしましょう。quick search は BMH 法とよく似ている方法です。違いは移動量を求めるところです。パターンが不一致になったとき、BMH 法はパターンの末尾と同じ位置にあるテキストの文字から移動量を求めます。ところが 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 のプログラム
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : 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 にセットします。quick search の場合、移動量を求めるときテキストの範囲外にアクセスすることがあります。
たとえば、テキストの最後の m 文字とパターン m 文字を比較した場合、次の移動量を求めるためテキスト末尾の次の文字が必要になります。ここで、テキストの範囲外をアクセスしてしまうのです。今回のプログラムは、最後の改行文字が番兵の役割をはたしているので正常に動作します。ご注意くださいませ。
変数 i がテキスト上のパターンの先頭位置を表します。i は 0 に初期化します。そして while ループで、i がテキストの範囲内であれば pattern と照合します。変数 j がパターンの位置を表します。quick search は BM 法とは違ってパターンの末尾から照合する必要はありません。
パターンのどの位置から照合してもかまわないのですが、このプログラムでは先頭から照合することにします。変数 j は 0 に初期化します。あとは、1 文字ずつ比較していきます。比較するテキストの位置は i + j になります。不一致であれば break で while ループを脱出します。
while ループが終了したあと、j が m と等しい場合は pattern と全て一致しました。output_line() で一致した行を表示します。そうでなければ、パターンの次に位置するテキストの文字 buff[i + m] の移動量を qs_table から求めて i に加算します。このように、quick search のプログラムは簡単に実装することができます。
●実行結果
それでは、プログラムの実行速度を比較してみましょう。world192.txt (2.473,400 byte) の中から "behind" を探した結果を示します。
表 : 実行結果 (時間 秒)
: 時間 : 比較回数
------+-------+-----------
力任せ: 0.778 : 2,499,956
ＢＭ法: 0.320 : 487,109
BMH 法: 0.282 : 481,787
quick : 0.210 : 405,431
実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
quick search が最も速くなりました。BM 法に比べ、比較回数は約 17 % 減少しています。quick search の効果はとても高いですね。BMH 法は quick search より遅くなりましたが、BM 法よりは高速で比較回数も減少しています。BMH 法の効果も十分に出ていると思います。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●参考文献 (URL)
●プログラムリスト
#
# search.py : 文字列の探索
#
# Copyright (C) 2007-2022 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
c = 0
while i <= n - m:
j = 0
while j < m:
c += 1
if buff[i + j] != pattern[j]: break
j += 1
if j == m:
# 発見した
i = output_line(buff, i) + m - 1
else:
i += 1
return c
# Boyer - Moore 法
CSIZE = 256
def make_bm_table(pattern, size):
bm_table = [size] * CSIZE
size -= 1
for i in range(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
c = 0
while i < n:
j = m - 1
while j >= 0:
c += 1
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)
return c
# Horspool のアルゴリズム
def bmh_search(buff, pattern):
n = len(buff) - 1
m = len(pattern)
bm_table = make_bm_table(pattern, m)
i = 0
c = 0
while i <= n - m:
j = m - 1
while j >= 0:
c += 1
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])]
return c
# Quick Search (Sunday のアルゴリズム)
def make_qs_table(pattern, size):
qs_table = [size + 1] * CSIZE
for i in range(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
c = 0
while i <= n - m:
j = 0
while j < m:
c += 1
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])]
return c
# テスト
buff = sys.stdin.read()
for func in [bf_search, bm_search, bmh_search, qs_search]:
s = time.time()
print(func(buff, sys.argv[1]))
e = time.time()
print(e - s)
改訂 2022 年 9 月 3 日