本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、文字列の探索としてKMP法(Knuth–Morris–Pratt Algorithm)について学んでいきます。
KMP法とは
KMP法とは、1970年にS.A.Cookの文字列探索アルゴリズムの証明を基に、D.E.KnuthとV.R.Prattが発見したアルゴリズムで、さらに同時期にテキストエディタ を作成する中でJ.H.Morrisが同じようなアルゴリズムを発見し、彼らの名前をとってKMP法(Knuth–Morris–Pratt Algorithm)と呼ばれています。
力まかせのアルゴリズムでは、パターンが途中までは一致していても、パターンとの不一致が起きたら、問答無用で文字列側のポインタを戻してしまっていました。
KMP法では上記の無駄を無くし、文字列側のポインタを戻すことはしません。
またパターン側では、不一致が起きた時にどれだけパターンをずらせばよいかを参照するための表も作成します。
なお、KMP法では計算量が最悪でもになりますが、条件分岐などの定数項が多くなるため、場合によっては力まかせのアルゴリズムより遅くなることもあります。
PythonでKMP法を実装してみる
それでは、PythonでKMP法を実装してみます。
# kmp.py import time def create_table(pattern): table = [0 for _ in range(len(pattern))] j = 0 for i in range(1, len(pattern)): if pattern[i] == pattern[j]: j += 1 table[i] = j else: table[i] = j j = 0 return table def kmp_search(string, pattern): table = create_table(pattern) i = j = 0 while i < len(string) and j < len(pattern): if string[i] == pattern[j]: i += 1 j += 1 elif j == 0: i += 1 else: j = table[j] if j == len(pattern): return i - j else: return None with open("sample_string.txt", "r") as f: string = f.read() pattern = "hoge" start = time.time() index = kmp_search(string, pattern) if index: print("The pattern starts with at index {}.".format(index)) else: print("No pattern matched.") print("elapsed {} sec.".format(time.time() - start))
動作確認
それでは上記で作成したスクリプトを実行してみます。
事前にa~zまでランダムに100,000文字を生成し、文字列の最後に"hoge"を追記したものから、"hoge"のパターンを探索します。
自環境で実行した結果を以下にまとめます。
アルゴリズム名 | 所要時間(秒) |
---|---|
Python 組込みメソッド(find()) | 0.0004 |
Brute-forcing | 0.0414 |
KMP | 0.0379 |