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

クヌース–モリス–プラット法とは、文字列検索アルゴリズムの一種。テキストSから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。

このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt およびJ. H. Morris が発明し、3人共同で発表した。

本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って単語 W 内の文字 'C' は W[2] と表される。

1. KMP法
-------

1.1. この検索アルゴリズムの実施例
-------------------

実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 m と i で表される。m はテキスト S 内の文字の位置であり、単語 W にマッチする可能性のある位置でもある。i は、その時点で照合中の W 内の文字の位置を示す。検索開始時点の状態は以下のように表される。

m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456まず、上記の状態で W の先頭と S の先頭から照合していく。この例では4文字目の照合で S[3] が空白、W[3] = 'D' となるため、不一致となる。W 内でそこまでに照合された範囲で 'A' が 0 番目にしかないことから、そこまで照合した S の範囲内に 'A' が出現しないことは明らかである。つまり、S[1] から S[3] までは W[0] とマッチすることはない。そのため、次の照合を単純に S[1] から開始するのではなく、m = 4 および i = 0 として次の照合を開始する。

m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456ここで、"ABCDAB" までマッチすることがわかるが、W[6]  で不一致となる。しかし、前回の不一致とは異なり、"AB" が2回出現していることに注意が必要である。この範囲での2回目の "AB" は W の先頭ともマッチするので、ここでは m = 8 および i = 2 として照合を再開する。これにより S の事前にマッチした文字列の照合を省くだけでなく、W 内の照合済み文字列の照合も省略している。

m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456今回の照合は即座に失敗し、次の照合は m = 11 および i = 0 として再開する。

m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456ここでも "ABCDAB" までマッチしていることが明らかとなるが、次の一文字は 'C' であり、W 内の次の文字 'D' と不一致となる。前述の場合と同様 "AB" が2回マッチしているので、m = 15 および i = 2 として検索を行う。

m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456ここで完全に照合でき、その際の最初の文字の位置は S[15] となる。

1.2. この検索アルゴリズムの擬似コードと解説
------------------------

前述の実施例はこのアルゴリズムのあらゆる要素を含んでいる。ここで、現在の照合が不一致に終わった際に次の照合の開始時点で参照する「部分マッチ」テーブル T を使用するものとする。T のエントリは、S[m] から照合して S[m + i] と W[i] が不一致となった際に次に照合を開始すべき位置を S の m + i - T[i] 番目とするよう設定される。これには2つの意味がある。第一に T[0] = -1 は W[0] が不一致の場合にバックトラックできず単に次の文字を照合すべきであることを示す。第二に m + i - T[i] が次の照合のインデックスとなるが、その先頭 T[i] 個の文字を照合する必要はなく、照合は W[T[i]] からでよい。以下の擬似コードは KMP法の実装例である。

algorithm //kmp_search//:input: an array of characters, S  an array of characters, W output: an integer 

define variables: an integer, m ← 0  an integer, i ← 0  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 + 1if i equals the length of W, return motherwise, let m ← m + i - T[i], and if i > 0, let i ← T[i]

return the length of S

1.3. この検索アルゴリズムの効率
------------------

テーブル T が事前に用意されているとした場合、クヌース-モリス-プラット法の検索部分の計算量は Oとなる。関数呼び出しに関わる固定オーバヘッド部分を除くと、全ての計算は while ループ内で行われるため、このループの繰り返し回数の上限が計算量となる。ここで T の性質が重要となる。S[m] から開始された照合が S[m + i] と W[i] の不一致で失敗したとき、次の照合は S[m + ] から開始される。次の照合は m 以降のインデックスから開始される必要があるため、T[i] < i が成り立つ。

このことから、ループが最大 2k 回繰り返されることがわかる。繰り返しのたびにループ内の2つの分岐のいずれかが実行される。最初の分岐では、常に i をインクリメントして m をそのままとし、インデックス m + i を変化させることで S 内の文字を調べていく。次の分岐では i - T[i] を m に加算する。前述の通り、この加算する値は常に正の値である。従って、照合開始位置 m は増加していく。ループの終了は m + i = k となったときである。従ってループ内の各分岐は k 回実行され、各分岐は m + i か m のいずれかを増加させる。ここで、m ≤ m + i である。m = k となったとき、m + i ≥ k なので、それ以前のいずれかの時点で m + i = k となっているはずである。従っていずれにしても処理は終了する。

以上からループの繰り返し回数は最大でも 2k 回であり、この検索アルゴリズムの計算量は O となる。

2. 「部分マッチ」テーブル
--------------

このテーブルの目的は S 内の各文字を複数回照合することを防ぐことである。線形検索の性質として、パターンの先頭とマッチする文字列に遭遇したとき、次の照合を開始すべき位置を与えることで複数回照合を防ぐことができる。換言すれば、パターン内を事前に検索して照合する必要のない文字数を各文字位置に対応して算出しておくのである。

ここで W の各文字位置で不一致が発生したとき、その直前の位置の文字列と W の先頭からの文字列が一致している場合、そのサブ文字列の長さのぶんだけバックトラックする。従って、T[i] の値は W の先頭からの文字列と W[i - 1]で完了する文字列が一致している長さに対応する。ここで空の文字列の長さを 0 とする。単語の先頭で不一致となる場合は特殊ケースであり、T[0] = -1 とする。

2.1. テーブル生成法の実施例
----------------

W = "ABCDABD" の例を考えてみよう。まず T[0] = -1 とする。T[1] は単語の2文字目で不一致となった場合のバックトラックする文字数であるが、1文字しか一致していない状態ではバックトラックできないので、T[1] = 0 となる。

T[2] は、そこまでの文字列 "AB" にその文字列の先頭部分と等しいサブ文字列がないため T[2] = 0 となる。

T[3] についても同様の判定を行う。つまり、T[i] を検討する場合、W[0] から W[i-1] までの文字列について、W[i-1] で終わる文字列と W[0] から始まる文字列が一致するかどうかを調べる。しかし、長さ 2 の文字列が一致するなら、それは T[2] の段階で見つかっていたはずである。従って長さ 2 のサブ文字列はありえない。また、長さ 1 では "C" は "A" とは一致しない。以上のことから T[3] = 0 とする。

次に W[4] つまり 'A' を渡す。同様の考え方で考慮すべき最長のサブ文字列の長さは 1 であり、この場合 'A' は単語の先頭と一致している。しかし、テーブルには現在位置の「直前」のサブ文字列長を格納するので、T[4] = 0 となる。

次に W[5] を調べると 'B' である。ここで W[4] から W[5] のサブ文字列は単語の先頭サブ文字列に等しい。従って W[5] で不一致となった場合に W[4] 以前に対応する部分を再度照合する必要はない。そこで T[5] = 1 となる。

現在注目している W[4] = 'A' から始まる文字列の次の文字は 'B' であることが期待されるが、これは W[5] と等しい。さらに前述の通り W[6] のためのサブ文字列を探索するのに W[4] より前を考慮する必要はない。従って、T[6] = 2 となる。

以上から、この場合のテーブルは以下のように生成される:



2.2. テーブル生成法の擬似コードと解説
---------------------

上述の実施例はテーブル生成の一般的な技術を説明している。基本的にそれが全てである。ある位置に到達したとき、すべきことは既に完了している。複雑化させる小さな問題は先頭で間違ってサブ文字列を与えてしまうことである。これに対処するにはちょっとした初期化コードが必要となる。

algorithm //kmp_table//:input: an array of characters, W  an array of integers, T output: nothing 

define variables: an integer, i ← 2  an integer, j ← 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]

otherwise, let T[i] ← 0, i ← i + 1

2.3. テーブル生成法の効率
---------------

テーブル生成アルゴリズムの計算量は Oである。初期化コードを除くと処理は全て while ループ内で行われるので、このループを O 回実行することを示せばよい。これは i と i - j の値を考えていくことで明らかとなる。第一の分岐では i - j は変化せず、i と j が同時にインクリメントされる。第二の分岐では j が T[j] で置換される。これは既に述べたように j より常に小さい。従って i - j は増加する。第三の分岐では、i だけがインクリメントされる。つまり、i も i - j も増加する。i ≥ i - j であるので、これは各段階で i か i の下限が増加するのと同じことである。このアルゴリズムは i = n となったとき終了し、i - j の初期値は 1 なので、ループは最大で 2n 回くりかえされる。以上からテーブル生成アルゴリズムの計算量は O となる。

3. KMP法の効率
----------

このアルゴリズムの各部分はそれぞれ O と O の計算量があるので、全体としての計算量は O となる。

先述の実施例でも明らかなように、文字をスキップできればできただけ単純な文字列検索アルゴリズムよりも有利となる。つまり、バックトラックがない方が好ましい。換言すれば T が全て 0 になっていればよい。従って "ABCDEFG" のような単語ではこのアルゴリズムは最も効率的に動作し、その際のテーブルは先頭が -1 でそれ以外は全て 0 となっている。逆に W = "AAAAAAA" のような場合は最悪である。このときのテーブルは以下のようになる。

これは T の最悪のパターンであり、S = "AAAAAABAAAAAABAAAAAAA" といった単語にもあてはまる。S の中に "AAAAAAB" が出現する頻度が多いほど繰り返し回数が増える。この単語のテーブル生成は高速となるが、検索は複数回行われる可能性があるのに対して、テーブル生成は1回だけである。従って、このような単語を検索する場合、このアルゴリズムの性能は低下する。ちなみに、このような文字列はボイヤー-ムーア法では最高の性能となる。KMP法は最良でも最悪でも線形時間で検索が完了するのに対して、ボイヤー-ムーア法は最良と最悪で大きく時間が異なる。

4. 外部リンク
--------

[1]
[2]

5. 参考文献
-------