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

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

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

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

KMP法

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

実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 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] (S[10]) で不一致となる。しかし、前回の不一致とは異なり、"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] となる。

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

前述の実施例はこのアルゴリズムのあらゆる要素を含んでいる。ここで、現在の照合が不一致に終わった際に次の照合の開始時点で参照する「部分マッチ」テーブル T を使用するものとする（後述）。T のエントリは、S[m] から照合して S[m + i] と W[i] が不一致となった際に次に照合を開始すべき位置を S の m + i - T[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 (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

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

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

「部分マッチ」テーブル

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

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

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

`i`	0	1	2	3	4	5	6
`W[i]`	A	B	C	D	A	B	D
`T[i]`	-1	0	0	0	0	1	2

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

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

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

テーブル生成法の効率

テーブル生成アルゴリズムの計算量は O(n)（ここで n は W の長さ）である。初期化コードを除くと処理は全て while ループ内で行われるので、このループを O(n) 回実行することを示せばよい。これは 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(n) となる。

KMP法の効率

このアルゴリズムの各部分は（上述の通り）それぞれ O(k) と O(n) の計算量があるので、全体としての計算量は O(n + k) となる。

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

`i`	0	1	2	3	4	5	6
`W[i]`	A	A	A	A	A	A	A
`T[i]`	-1	0	1	2	3	4	5

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

外部リンク

参考文献

Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977年). “Fast pattern matching in strings”. SIAM Journal on Computing 6 (2): pp323-350.

Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001年). “Section 32.4: The Knuth-Morris-Pratt algorithm”. Introduction to Algorithms (Second edition ed.). MIT Press and McGraw-Hill. pp. pp923-931. ISBN 0262032937