クヌース–モリス–プラット法

クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）codice_1から単語codice_2を探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。
このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J. H. Morris が発明し、3人共同で発表した。
本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って（後述の）単語 codice_2 内の文字 codice_4 は codice_5 と表される。
KMP法.
この検索アルゴリズムの実施例.
実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 codice_6 と codice_7 で表される。codice_6 はテキスト codice_1 内の文字の位置であり、単語 codice_2 にマッチする可能性のある位置でもある。codice_7 は、その時点で照合中の codice_2 内の文字の位置を示す。検索開始時点の状態は以下のように表される。
 m: 01234567890123456789012
 S: ABC ABCDAB ABCDABCDABDE
 W: ABCDABD
 i: 0123456
まず、上記の状態で codice_2 の先頭と codice_1 の先頭から照合していく。この例では4文字目の照合で codice_15 が空白、codice_16 となるため、不一致となる。codice_2 内でそこまでに照合された範囲で codice_18 が 0 番目にしかないことから、そこまで照合した codice_1 の範囲内に codice_18 が出現しないことは明らかである。つまり、codice_21 から codice_15 までは codice_23 とマッチすることはない。そのため、次の照合を単純に codice_21 から開始するのではなく、codice_25 および codice_26 として次の照合を開始する。
 m: 01234567890123456789012
 S: ABC ABCDAB ABCDABCDABDE
 W: ABCDABD
 i: 0123456
ここで、codice_27 までマッチすることがわかるが、codice_28 (codice_29) で不一致となる。しかし、前回の不一致とは異なり、codice_30 が2回出現していることに注意が必要である。この範囲での2回目の "AB" は codice_2 の先頭ともマッチするので、ここでは codice_32 および codice_33 として照合を再開する。これにより codice_1 の事前にマッチした文字列の照合を省くだけでなく、codice_2 内の照合済み文字列の照合も省略している。
 m: 01234567890123456789012
 S: ABC ABCDAB ABCDABCDABDE
 W: ABCDABD
 i: 0123456
今回の照合は即座に失敗し、次の照合は codice_36 および codice_26 として再開する。
 m: 01234567890123456789012
 S: ABC ABCDAB ABCDABCDABDE
 W: ABCDABD
 i: 0123456
ここでも codice_27 までマッチしていることが明らかとなるが、次の一文字は codice_4 であり、codice_2 内の次の文字 codice_41 と不一致となる。前述の場合と同様 codice_30 が2回マッチしているので、codice_43 および codice_33 として検索を行う。
 m: 01234567890123456789012
 S: ABC ABCDAB ABCDABCDABDE
 W: ABCDABD
 i: 0123456
ここで完全に照合でき、その際の最初の文字の位置は codice_45 となる。
この検索アルゴリズムの擬似コードと解説.
前述の実施例はこのアルゴリズムのあらゆる要素を含んでいる。ここで、現在の照合が不一致に終わった際に次の照合の開始時点で参照する「部分マッチ」テーブル codice_46 を使用するものとする（後述）。codice_46 のエントリは、codice_48 から照合して codice_49 と codice_50 が不一致となった際に次に照合を開始すべき位置を codice_1 の codice_52 番目とするよう設定される（つまり、codice_53 は不一致の際のバックトラッキングを示す）。これには2つの意味がある。第一に codice_54 は codice_23 が不一致の場合にバックトラックできず単に次の文字を照合すべきであることを示す。第二に codice_52 が次の照合のインデックスとなるが、その先頭 codice_53 個の文字を照合する必要はなく、照合は codice_58 からでよい。以下の擬似コードは KMP法の実装例である。
 algorithm "kmp_search":
 input:
 an array of characters, S (検索対象のテキスト)
 an array of characters, W (単語)
 output:
 an integer (W が見つかった際の S 内の位置。ただし先頭文字は 0番目とする)
 define variables:
 an integer, m ← 0 (S 内の現在照合中の開始位置)
 an integer, i ← 0 (W 内の現在位置)
 an array of integers, T (テーブル。他で事前に構築される)
 while m + i is less than the length of S, do:
 if W[i] = S[m + i], let i ← i + 1
 if i equals the length of W, return m
 otherwise, let m ← m + i - T[i], and if i > 0, let i ← T[i]
 (W が S 内に見つからなかった場合)
 return the length of S
この検索アルゴリズムの効率.
テーブル codice_46 が事前に用意されているとした場合、クヌース-モリス-プラット法の検索部分の計算量は Ocodice_60（ここで codice_61 は codice_1 の長さ）となる。関数呼び出しに関わる固定オーバヘッド部分を除くと、全ての計算は codice_63 ループ内で行われるため、このループの繰り返し回数の上限が計算量となる。ここで codice_46 の性質が重要となる。codice_48 から開始された照合が codice_49 と codice_50 の不一致で失敗したとき、次の照合は codice_68 から開始される。次の照合は codice_6 以降のインデックスから開始される必要があるため、codice_70 が成り立つ。
このことから、ループが最大 codice_71 回繰り返されることがわかる。繰り返しのたびにループ内の2つの分岐のいずれかが実行される。最初の分岐では、常に codice_7 をインクリメントして codice_6 をそのままとし、インデックス codice_74 を変化させることで codice_1 内の文字を調べていく。次の分岐では codice_76 を codice_6 に加算する。前述の通り、この加算する値は常に正の値である。従って、照合開始位置 codice_6 は増加していく。ループの終了は codice_79 となったときである。従ってループ内の各分岐は codice_61 回実行され、各分岐は codice_74 か codice_6 のいずれかを増加させる。ここで、codice_83 である。codice_84 となったとき、codice_85 なので、それ以前のいずれかの時点で codice_79 となっているはずである。従っていずれにしても処理は終了する。
以上からループの繰り返し回数は最大でも codice_71 回であり、この検索アルゴリズムの計算量は codice_88 となる。
「部分マッチ」テーブル.
このテーブルの目的は codice_1 内の各文字を複数回照合することを防ぐことである。線形検索の性質として、パターンの先頭とマッチする文字列に遭遇したとき、次の照合を開始すべき位置を与えることで複数回照合を防ぐことができる。換言すれば、パターン内を事前に検索して照合する必要のない文字数を各文字位置に対応して算出しておくのである。
ここで codice_2 の各文字位置で不一致が発生したとき、その直前の位置の文字列と codice_2 の先頭からの文字列が一致している場合、そのサブ文字列の長さのぶんだけバックトラックする。従って、codice_53 の値は codice_2 の先頭からの文字列と codice_94で完了する文字列が一致している長さに対応する。ここで空の文字列の長さを 0 とする。単語の先頭で不一致となる場合は特殊ケースであり（バックトラックできないため）、codice_54 とする。
テーブル生成法の実施例.
codice_96 の例を考えてみよう。まず codice_54 とする。codice_98 は単語の2文字目で不一致となった場合のバックトラックする文字数であるが、1文字しか一致していない状態ではバックトラックできないので、codice_99 となる。
codice_100 は、そこまでの文字列 "AB" にその文字列の先頭部分と等しいサブ文字列がないため codice_101 となる。
codice_102 についても同様の判定を行う。つまり、codice_53 を検討する場合、codice_23 から codice_105 までの文字列について、codice_105 で終わる文字列と codice_23 から始まる文字列が一致するかどうかを調べる。しかし、長さ 2 の文字列（考えられる最長のサブ文字列）が一致するなら、それは codice_100 の段階で見つかっていたはずである。従って長さ 2 のサブ文字列はありえない。また、長さ 1 では "C" は "A" とは一致しない。以上のことから codice_109 とする。
次に codice_110 つまり codice_18 を渡す。同様の考え方で考慮すべき最長のサブ文字列の長さは 1 であり、この場合 codice_18 は単語の先頭と一致している。しかし、テーブルには現在位置の「直前」のサブ文字列長を格納するので、codice_113 となる。
次に codice_114 を調べると codice_115 である。ここで codice_110 から codice_114 のサブ文字列は単語の先頭サブ文字列に等しい。従って codice_114 で不一致となった場合に codice_110 以前に対応する部分を再度照合する必要はない。そこで codice_120 となる。
現在注目している codice_121 から始まる文字列の次の文字は codice_115 であることが期待されるが、これは codice_114 と等しい。さらに前述の通り codice_28 のためのサブ文字列を探索するのに codice_110 より前を考慮する必要はない。従って、codice_126 となる。
以上から、この場合のテーブルは以下のように生成される:
テーブル生成法の擬似コードと解説.
上述の実施例はテーブル生成の一般的な技術を説明している。基本的にそれが全てである。ある位置に到達したとき、すべきことは既に完了している。複雑化させる小さな問題は先頭で間違ってサブ文字列を与えてしまうことである。これに対処するにはちょっとした初期化コードが必要となる。
 algorithm "kmp_table":
 input:
 an array of characters, W (解析すべき単語)
 an array of integers, T (生成すべきテーブル)
 output:
 nothing (ただし、処理を行うことでテーブルの中身が書き込まれる)
 define variables:
 an integer, i ← 2 (T の中で現在計算している位置)
 an integer, j ← 0 (現在見ているサブ文字列の次の文字のインデックス。0から始まる)
 (先頭ふたつの値は固定。ただしアルゴリズムの実装によっては具体的値は異なる)
 let T[0] ← -1, T[1] ← 0
 while i is less than the length of W, do:
 (第一の場合: サブ文字列は継続中)
 if W[i - 1] = W[j], let T[i] ← j + 1, i ← i + 1, j ← j + 1
 (第二の場合: サブ文字列は継続しないが、フォールバック可能)
 otherwise, if j > 0, let j ← T[j]
 (第三の場合: 対象をはみ出した。このとき j = 0)
 otherwise, let T[i] ← 0, i ← i + 1
テーブル生成法の効率.
テーブル生成アルゴリズムの計算量は codice_127（ここで codice_128 は codice_2 の長さ）である。初期化コードを除くと処理は全て codice_63 ループ内で行われるので、このループを codice_127 回実行することを示せばよい。これは codice_7 と codice_133 の値を考えていくことで明らかとなる。第一の分岐では codice_133 は変化せず、codice_7 と codice_136 が同時にインクリメントされる。第二の分岐では codice_136 が codice_138 で置換される。これは既に述べたように codice_136 より常に小さい。従って codice_133 は増加する。第三の分岐では、codice_7 だけがインクリメントされる。つまり、codice_7 も codice_133 も増加する。codice_144 であるので、これは各段階で codice_7 か codice_7 の下限が増加するのと同じことである。このアルゴリズムは codice_147 となったとき終了し、codice_133 の初期値は codice_149 なので、ループは最大で codice_150 回くりかえされる。以上からテーブル生成アルゴリズムの計算量は codice_127 となる。
KMP法の効率.
このアルゴリズムの各部分は（上述の通り）それぞれ codice_88 と codice_127 の計算量があるので、全体としての計算量は Ocodice_154 となる。
先述の実施例でも明らかなように、文字をスキップできればできただけ単純な文字列検索アルゴリズムよりも有利となる。つまり、バックトラックがない方が好ましい。換言すれば codice_46 が全て 0 になっていればよい。従って codice_156 のような単語ではこのアルゴリズムは最も効率的に動作し、その際のテーブルは先頭が -1 でそれ以外は全て 0 となっている。逆に codice_157 のような場合は最悪である。このときのテーブルは以下のようになる。
これは codice_46 の最悪のパターンであり、codice_159 といった単語にもあてはまる。codice_1 の中に codice_161 が出現する頻度が多いほど繰り返し回数が増える。この単語のテーブル生成は高速となるが、検索は複数回行われる可能性があるのに対して、テーブル生成は1回だけである。従って、このような単語を検索する場合、このアルゴリズムの性能は低下する。ちなみに、このような文字列はボイヤー-ムーア法では最高の性能となる。KMP法は最良でも最悪でも線形時間で検索が完了するのに対して、ボイヤー-ムーア法は最良と最悪で大きく時間が異なる。