KMP法徹底入門：高速な文字列検索アルゴリズムを理解する

By /

KMP法徹底入門：高速な文字列検索アルゴリズムを理解する

はじめに：文字列検索の重要性とナイーブ法の限界

私たちは日常的に、そしてコンピューターの世界では頻繁に「文字列検索」を行っています。Webブラウザでキーワードを入力して情報を探したり、ワープロソフトで特定の単語を置き換えたり、プログラミングにおいてソースコード中の関数名を探したり。これらの操作の根幹には、与えられた長い文字列（これを「テキスト」と呼びます）の中に、特定の短い文字列（これを「パターン」と呼びます）が存在するかどうか、存在する場合はどこにあるのかを見つけ出すという処理があります。

この文字列検索は、コンピュータサイエンスにおける基本的な問題の一つであり、様々なアルゴリズムが考案されてきました。最も直感的で簡単なアルゴリズムは「ナイーブ法（あるいは単純な線形探索）」と呼ばれるものですが、これは特定のケースで非常に非効率になるという欠点があります。

本稿では、このナイーブ法の欠点を克服し、非常に効率的に文字列検索を実行できるアルゴリズムである「KMP法（Knuth-Morris-Pratt法）」について、その原理から実装までを徹底的に解説します。KMP法は、テキストを左から右へ一度だけスキャンする（テキストの同じ文字を複数回検査しない）という特徴を持ち、その計算量はテキストとパターンの長さに線形に比例するという、理論的に非常に優れたアルゴリズムです。

まずは、なぜナイーブ法が非効率なのかを見ていくことから始めましょう。

ナイーブな文字列検索（ナイーブ法）

ナイーブ法は、テキスト T の先頭からパターン P の長さに等しい部分文字列を順に取り出し、それがパターン P と一致するかどうかを比較していく方法です。

アルゴリズムの概要:

  1. テキスト T のインデックス i を 0 から n-m まで（n はテキスト長、m はパターン長）1つずつ増やしながら、以下の処理を行います。
  2. テキスト T の i 番目の文字から始まる長さ m の部分文字列 T[i...i+m-1] とパターン P[0...m-1] を、先頭から1文字ずつ比較します。
  3. もし、全ての文字が一致すれば、パターンはテキストの i 番目の位置から発見されたことになります。
  4. もし、比較の途中で一致しない文字が見つかったら、そのテキストの位置 i からはパターンが見つからなかったと判断し、テキストの次の位置 i+1 からの比較を開始するために、ステップ1に戻ります。

具体例:

テキスト T = "ABABDABACDABABCABAB" (長さ n = 19)
パターン P = "ABABCABAB" (長さ m = 9)

  1. i = 0: T[0...8] (“ABABDABAC”) と P[0...8] (“ABABCABAB”) を比較。
    • T[0] == P[0] (‘A’ == ‘A’) -> OK
    • T[1] == P[1] (‘B’ == ‘B’) -> OK
    • T[2] == P[2] (‘A’ == ‘A’) -> OK
    • T[3] == P[3] (‘B’ == ‘B’) -> OK
    • T[4] != P[4] (‘D’ != ‘C’) -> 不一致。位置 i=0 からはマッチしない。
  2. i = 1: T[1...9] (“BABACDABA”) と P[0...8] (“ABABCABAB”) を比較。
    • T[1] != P[1] (‘B’ != ‘A’) -> 不一致。位置 i=1 からはマッチしない。
  3. i = 2: T[2...10] (“ABACDABAC”) と P[0...8] (“ABABCABAB”) を比較。
    • T[2] == P[0] (‘A’ == ‘A’) -> OK
    • T[3] == P[1] (‘B’ == ‘B’) -> OK
    • T[4] != P[2] (‘A’ != ‘A’) -> 不一致…と思いきや、例がおかしいですね。修正します。

具体例（修正）:

テキスト T = "ABABDABACDABABCABAB" (長さ n = 19)
パターン P = "ABABCABAB" (長さ m = 9)

  1. i = 0: T[0...8] (“ABABDABAC”) と P[0...8] (“ABABCABAB”) を比較。
    • T[0]==’A’, P[0]==’A’ -> OK
    • T[1]==’B’, P[1]==’B’ -> OK
    • T[2]==’A’, P[2]==’A’ -> OK
    • T[3]==’B’, P[3]==’B’ -> OK
    • T[4]==’D’, P[4]==’C’ -> 不一致。i=0 からはマッチしない。次の位置へ。
  2. i = 1: T[1...9] (“BABACDABA”) と P[0...8] (“ABABCABAB”) を比較。
    • T[1]==’B’, P[0]==’A’ -> 不一致。i=1 からはマッチしない。次の位置へ。
  3. i = 2: T[2...10] (“ABACDABAC”) と P[0...8] (“ABABCABAB”) を比較。
    • T[2]==’A’, P[0]==’A’ -> OK
    • T[3]==’B’, P[1]==’B’ -> OK
    • T[4]==’A’, P[2]==’A’ -> OK
    • T[5]==’C’, P[3]==’B’ -> 不一致。i=2 からはマッチしない。次の位置へ。
      …（同様の比較が続く）
  4. i = 10: T[10...18] (“ABABCABAB”) と P[0...8] (“ABABCABAB”) を比較。
    • T[10]==’A’, P[0]==’A’ -> OK
    • T[11]==’B’, P[1]==’B’ -> OK
    • …
    • T[18]==’B’, P[8]==’B’ -> OK
    • すべて一致！ パターンはテキストのインデックス 10 から見つかりました。

ナイーブ法の問題点（計算量）:

ナイーブ法の計算量は、テキスト長を n、パターン長を m とすると、最悪の場合で O(nm) となります。これは、テキストの各位置 i (n-m+1 箇所) に対して、パターン全体 (m 文字) を比較する必要があるためです。

例えば、テキストが “AAAAA…AAAAA” でパターンが “AAAAAB” のような場合を考えます。
T = "AAAAAAA..." (n個の’A’)
P = "AAAAB" (m個の’A’ + ‘B’)

  • i=0: “AAAAB” と比較。4文字目まで一致するが、5文字目 (‘B’) で不一致。
  • i=1: “AAAAB” と比較。4文字目まで一致するが、5文字目 (‘B’) で不一致。
  • …
  • i=n-m: “AAAAB” と比較。

このように、テキストの多くの位置でパターンのほとんどの部分まで一致し、最後の文字で不一致となる場合、ナイーブ法はテキストの各位置 i でほぼ m 回の比較を行うことになります。結果として、比較回数は約 n * m に比例し、O(nm) の計算量となります。テキストやパターンが長くなると、この非効率性が顕著になります。

ナイーブ法の最大の問題は、不一致が発生したときに、テキストのポインタ i を常に1つしか進めず、かつパターンのポインタを最初に戻すことです。上の例で i=0 で不一致になった際、T[0...3] と P[0...3] が一致しているというせっかくの情報があるにも関わらず、i=1 からの比較を再開する際には、テキストの T[1] とパターンの P[0] をまた比較し直しています。この「一致した部分文字列の中に、実は次に検索を開始する上で有用な情報が隠れている」ことを見落としている点が、ナイーブ法の非効率さの根本原因です。

KMP法は、この「一致した部分文字列の中に含まれる有用な情報」を最大限に活用することで、テキストのポインタを巻き戻すことなく、効率的に検索を進めることを可能にします。

KMP法の基本思想：賢いスキップ

ナイーブ法の非効率性は、不一致が発生した際に、それまで一致していた部分の情報を捨て去ってしまうことにありました。KMP法は、この捨てていた情報を活用します。

具体的には、テキスト T とパターン P を比較していて、T[i] と P[j] で初めて不一致が発生したとします。これは、T[i-j ... i-1] というテキストの部分文字列と P[0 ... j-1] というパターンの接頭辞が、これまでの比較で一致していたことを意味します。

テキスト: T = ... [T[i-j] ... T[i-1]] T[i] ...
                  ^                 ^
                  (i-j)             (i)
パターン: P =   [P[0]   ... P[j-1]] P[j] ...
                  ^                 ^
                  (0)               (j)

ここで T[i] != P[j] です。ナイーブ法では、次に T[i-j+1] と P[0] を比較するために、テキストポインタを i-j+1 に、パターンポインタを 0 に戻します。しかし、KMP法は「T[i-j ... i-1] と P[0 ... j-1] が一致している」という事実を使います。

もし、パターン P の接頭辞 P[0 ... j-1] の中に、その適切な接尾辞（自分自身を含まない接尾辞）と一致する適切な接頭辞が存在するならば、その情報を次に生かせるはずです。

例を考えてみましょう。
パターン P = "ABACAB" を検索しています。
テキスト T = "...ABACAZ..." で、T[i] が ‘Z’、P[j] が ‘B’ で、T[i] と P[j] (j=5) で不一致が発生したとします。
つまり、T[i-5 ... i-1] は P[0...4] (“ABACA”) と一致していました。

テキスト: T = ... A B A C A Z ...
パターン: P =     A B A C A B ...
                  ^       ^
                  (i-5)   (i-1) (i)
                  ^       ^
                  (0)     (4)   (5) -- ここで不一致 (Z != B)

ここで T[i-5 ... i-1] (“ABACA”) と P[0...4] (“ABACA”) が一致しています。
パターン P[0...4] (“ABACA”) という文字列を見てみましょう。
この文字列の適切な接頭辞は “A”, “AB”, “ABA”, “ABAC” です。
この文字列の適切な接尾辞は “A”, “CA”, “ACA”, “BACA” です。
これらの中で、一致する最長のものは何でしょうか？
接頭辞 “A” と接尾辞 “A” が一致します。長さは1です。
接頭辞 “ABA” と接尾辞 “ABA” が一致します。長さは3です。
接頭辞 “ABAC” と接尾辞 “ACA” … 一致しません。

したがって、P[0...4] (“ABACA”) という文字列において、適切な接頭辞と適切な接尾辞が一致する最長の長さは3です。これは P[0...2] (“ABA”) と P[2...4] (“ACA”) … 例がおかしいですね。もう一度接尾辞をチェックします。

P[0...4] (“ABACA”) の適切な接尾辞は “A”, “CA”, “ACA”, “BACA” です。
接頭辞 “A” と接尾辞 “A” (長さ1) – OK
接頭辞 “AB” と接尾辞 “CA” – NG
接頭辞 “ABA” と接尾辞 “ACA” – NG
接頭辞 “ABAC” と接尾辞 “BACA” – NG

あれ？この例では、P[0...4] = “ABACA” の適切な接頭辞と適切な接尾辞で一致する最長のものは “A” (長さ1) だけですね。私の例の選定ミスでした。

別の例です。
パターン P = "ABABAB" を検索しています。
テキスト T = "...ABABAC..." で、T[i] が ‘C’、P[j] が ‘B’ で、T[i] と P[j] (j=5) で不一致が発生したとします。
つまり、T[i-5 ... i-1] は P[0...4] (“ABABA”) と一致していました。

テキスト: T = ... A B A B A C ...
パターン: P =     A B A B A B ...
                  ^       ^
                  (i-5)   (i-1) (i)
                  ^       ^
                  (0)     (4)   (5) -- ここで不一致 (C != B)

ここで T[i-5 ... i-1] (“ABABA”) と P[0...4] (“ABABA”) が一致しています。
パターン P[0...4] (“ABABA”) という文字列を見てみましょう。
適切な接頭辞: “A”, “AB”, “ABA”, “ABAB”
適切な接尾辞: “A”, “BA”, “ABA”, “BABA”

一致する最長の適切な接頭辞/接尾辞は？
“A” (長さ1) – OK
“ABA” (長さ3) – OK
“ABAB” (長さ4) – NG

一致する最長の文字列は “ABA” で、長さは3です。

これは何を意味するのでしょうか？
P[0...4] (“ABABA”) の先頭3文字 P[0...2] (“ABA”) は、末尾3文字 P[2...4] (“ABA”) と一致しているということです。
そして、T[i-5 ... i-1] は P[0...4] と一致しているので、テキストのこの部分 (T[i-5 ... i-1]) の先頭3文字 T[i-5 ... i-3] (“ABA”) も、末尾3文字 T[i-3 ... i-1] (“ABA”) と一致していることになります。

不一致が T[i] と P[j] で発生したとき、T[i-j ... i-1] と P[0 ... j-1] は一致していました。
P[0 ... j-1] において、長さ k の適切な接頭辞 P[0 ... k-1] が、同じ長さ k の適切な接尾辞 P[j-k ... j-1] と一致するような、最長の長さ k を考えます。
このとき、テキストの対応する部分 T[i-j ... i-1] でも、先頭 T[i-j ... i-j+k-1] は末尾 T[i-k ... i-1] と一致しており、かつこれらは P[0 ... k-1] と一致しています。

つまり、T[i-k ... i-1] と P[0 ... k-1] は一致していることが保証されます。
したがって、不一致が発生した T[i] に対して、次に比較すべきパターンの文字は、パターン全体 P の k 番目の文字 P[k] にすれば良いのです。パターンのポインタ j を k に移動させる、ということです。

不一致時:
テキスト: T = ... [P[0...k-1]] ... [P[0...k-1]] T[i] ...  <-- T[i-k ... i-1] が P[0...k-1] と一致している
                  ^              ^
                  (i-j)          (i-k)          (i)
パターン: P =   [P[0...k-1]] ... [P[j-k...j-1]] P[j] ...  <-- P[0...k-1] が P[j-k...j-1] と一致している
                  ^              ^              ^
                  (0)            (k)            (j)

次に比較すべき位置:
テキスト: T = ... [P[0...k-1]] ... [P[0...k-1]] T[i] ...  <-- T[i-k ... i-1] は P[0...k-1] と一致
                  ^                             ^
                  (i-k)                         (i)
パターン: P =   [P[0...k-1]]                   P[k] ...  <-- P[0...k-1] は P[0...k-1] 自身
                  ^                             ^
                  (0)                           (k)

次回の比較は T[i] と P[k] で行う

パターンのポインタ j は、この「一致する最長の適切な接頭辞の長さ」 k に基づいて移動します。テキストポインタ i はそのままです。これにより、テキストを巻き戻すことなく、効率的に検索を進めることができます。

この「パターン P の接頭辞 P[0...j-1] において、適切な接頭辞と適切な接尾辞が一致する最長の長さ」を事前に計算しておき、検索時に利用するための情報が、KMP法の中核をなす「失敗関数（failure function）」あるいは「接頭辞関数（prefix function）」と呼ばれるものです。

失敗関数 (Failure Function / Prefix Function) π

失敗関数 π (パイ) は、パターン P に対して事前に計算される配列です。配列 π の各要素 π[i] は、パターン P の i 番目の文字までからなる接頭辞 P[0...i] において、適切な接頭辞であり、かつ適切な接尾辞でもあるような最長の文字列の長さを示します。

定義:
π[i] = パターン P の接頭辞 P[0...i] において、適切な接頭辞 P[0...k-1] が適切な接尾辞 P[i-k+1...i] と一致するような、最大の長さ k (ただし k > 0 の場合)。そのような k が存在しない場合は π[i] = 0 とします。
インデックス i は 0 から m-1 までです。
特に π[0] は、長さ1の接頭辞 P[0...0] ("P[0]") の適切な接頭辞/接尾辞は存在しないため、常に 0 となります。

例：パターン P = "ABABABC" (m=7) の失敗関数 π を計算してみましょう。

  • i = 0: P[0] = "A"。適切な接頭辞/接尾辞なし。π[0] = 0。
  • i = 1: P[0...1] = "AB"。適切な接頭辞: "A"。適切な接尾辞: "B"。一致なし。π[1] = 0。
  • i = 2: P[0...2] = "ABA"。適切な接頭辞: "A", "AB"。適切な接尾辞: "A", "BA"。最長一致: "A" (長さ1)。π[2] = 1。
  • i = 3: P[0...3] = "ABAB"。適切な接頭辞: "A", "AB", "ABA"。適切な接尾辞: "B", "AB", "BAB"。最長一致: "AB" (長さ2)。π[3] = 2。
  • i = 4: P[0...4] = "ABABA"。適切な接頭辞: "A", "AB", "ABA", "ABAB"。適切な接尾辞: "A", "BA", "ABA", "BABA"。最長一致: "ABA" (長さ3)。π[4] = 3。
  • i = 5: P[0...5] = "ABABAB"。適切な接頭辞: "A", "AB", "ABA", "ABAB", "ABABA"。適切な接尾辞: "B", "AB", "BAB", "ABAB", "BABAB"。最長一致: "ABAB" (長さ4)。π[5] = 4。
  • i = 6: P[0...6] = "ABABABC"。適切な接頭辞: "A", "AB", "ABA", "ABAB", "ABABA", "ABABAB"。適切な接尾辞: "C", "BC", "ABC", "BABC", "ABABC", "BABABC"。一致なし。π[6] = 0。

結果として、パターン "ABABABC" の失敗関数 π は [0, 0, 1, 2, 3, 4, 0] となります。

失敗関数 π の計算アルゴリズム:

失敗関数 π は、パターンの長さ m に対して線形時間 O(m) で計算できます。動的計画法に似た考え方を利用します。π[i] を計算する際に、既に計算済みの π[0] から π[i-1] までの値を利用します。

π[i] は、接頭辞 P[0...i] に対する値です。これを計算するために、P[0...i-1] に対する値 π[i-1] を利用することを考えます。
π[i-1] は、接頭辞 P[0...i-1] において、長さ k = π[i-1] の適切な接頭辞 P[0...k-1] が適切な接尾辞 P[i-k...i-1] と一致することを示しています。

パターン P:  P[0] ... P[k-1] P[k] ... P[i-1] P[i]
接頭辞 P[0...i-1]:  P[0] ... P[k-1]           = P[i-k ... i-1]
                                ^             ^
                                (k-1)         (i-1)

ここで、P[i] と P[k] を比較してみましょう。
もし P[i] == P[k] ならば、接頭辞 P[0...i] において、長さ k+1 の接頭辞 P[0...k] が接尾辞 P[i-k...i] と一致していることになります (P[0...k-1] が P[i-k...i-1] と一致しており、かつ P[k] が P[i] と一致するため)。
この場合、π[i] = k + 1 = π[i-1] + 1 となります。

P[0] ... P[k-1] P[k] ... P[i-1] P[i]
接頭辞 P[0...i]: P[0] ... P[k]             = P[i-k ... i]  (長さ k+1)
                 ^       ^                   ^       ^
                 (0)     (k)                 (i-k)   (i)

もし P[i] != P[k] ならば？
長さ k = π[i-1] + 1 の接頭辞 P[0...k] は、接尾辞 P[i-k...i] と一致しませんでした。
では、これより短い、次に長い一致する接頭辞/接尾辞の長さはいくつでしょうか？
それは、接頭辞 P[0...k-1] (P[0...π[i-1]]) において、適切な接頭辞と適切な接尾辞が一致する最長の長さ、すなわち π[k-1] です。
新しい長さ k' を π[k-1] とします。そして、P[i] と P[k'] を再び比較します。

P[0] ... P[k'-1] P[k'] ... P[k-1] P[k] ... P[i-1] P[i]
接頭辞 P[0...k-1] において: P[0] ... P[k'-1] = P[k-k'...k-1] (長さ k')
不一致時: P[i] != P[k] (k = π[i-1]+1 だった)
次の候補の長さは k' = π[k-1]
比較対象は P[i] と P[k']

このプロセスは、k' が 0 になるまで（または P[i] == P[k'] となるまで）繰り返されます。k の初期値は π[i-1] ですが、実際にはアルゴリズム内で現在の「マッチしている接頭辞の長さ」を保持する変数（ここでは len とします）を使用します。

π 計算アルゴリズム (0-indexed):

入力: パターン P (長さ m)
出力: π 配列 (長さ m)

```
π[0] = 0
len = 0 // len は現在考慮している接頭辞 P[0...i] における、
// 最長一致する適切な接頭辞/接尾辞の長さ
// π[i-1] の値を保持しているイメージ (厳密には少し違うが、直観的に)

for i = 1 to m-1:
// len は P[0...i-1] に対する最長一致長 π[i-1] に相当する (π[i-1] が positive の場合)
// P[0...len-1] は P[i-len...i-1] と一致している
while len > 0 and P[i] != P[len]:
// P[i] と P[len] が一致しない
// 次に短い、一致する接頭辞/接尾辞の長さを試す
// これは、P[0...len-1] における最長一致長の π[len-1] に等しい
len = π[len-1]

// ここに来た時点で、len == 0 か、P[i] == P[len] が成り立つ

if P[i] == P[len]:
    // P[i] と P[len] が一致した
    // 一致する接頭辞/接尾辞の長さが1増えた
    len = len + 1

// len が P[0...i] に対する最長一致長となる
π[i] = len

return π
```

π 計算の具体例: P = "ABACABAGA" (m=9)

i P[i] len (計算前) P[i] vs P[len] len > 0? whileループ内部 (len = π[len-1]) P[i] == P[len]? len (計算後) π[i] 備考
0 A - - - - - 0 0 π[0] = 0 (定義より)
1 B 0 'B' vs P[0]='A' No - No 0 0 P[0...1] = "AB". 無し。
2 A 0 'A' vs P[0]='A' No - Yes 1 1 P[0...2] = "ABA". "A" (P[0]) = "A" (P[2]). 長さ1。
3 C 1 'C' vs P[1]='B' Yes len = π[1] = 0 'C' vs P[0]='A' No 0 P[0...3] = "ABAC". 無し。 (P[0] vs P[3] は一致せず、len=0 に)
4 A 0 'A' vs P[0]='A' No - Yes 1 1 P[0...4] = "ABACA". "A" (P[0]) = "A" (P[4]). 長さ1。
5 B 1 'B' vs P[1]='B' Yes - Yes 2 2 P[0...5] = "ABACAB". "AB" (P[0..1]) = "AB" (P[4..5]). 長さ2。 (len=1 から P[5] vs P[1] 一致 -> len=2)
6 A 2 'A' vs P[2]='A' Yes - Yes 3 3 P[0...6] = "ABACABA". "ABA" (P[0..2]) = "ABA" (P[4..6]). 長さ3。 (len=2 から P[6] vs P[2] 一致 -> len=3)
7 G 3 'G' vs P[3]='C' Yes len = π[3] = 0 'G' vs P[0]='A' No 0 P[0...7] = "ABACABAG". 無し。 (len=3 から P[7] vs P[3] 不一致 -> len=π[3]=0. P[7] vs P[0] 不一致 -> len=0)
8 A 0 'A' vs P[0]='A' No - Yes 1 1 P[0...8] = "ABACABAGA". "A" (P[0]) = "A" (P[8]). 長さ1。 (len=0 から P[8] vs P[0] 一致 -> len=1)

π配列: [0, 0, 1, 0, 1, 2, 3, 0, 1]

この計算アルゴリズムの計算量は O(m) です。なぜなら、i は m-1 まで単調増加し、len は if P[i] == P[len] の場合に最大で1増え、while ループ内では必ず減少します。len の最大値は m ですから、len が増える総量は高々 m です。while ループで len が減少する総量も、増えた総量を超えることはありません。したがって、全体の操作回数は i のループ m-1 回と、len の増減による操作の合計で O(m) となります。

KMP検索アルゴリズム

失敗関数 π の計算方法が理解できたので、いよいよKMP検索アルゴリズム本体です。このアルゴリズムは、テキスト T とパターン P を左から右へ同時に比較していきます。

アルゴリズムの概要:

テキスト上の現在の位置を i、パターン上の現在の位置を j とします。
i はテキスト T のインデックス、j はパターン P のインデックスです。
初期値は i = 0、j = 0 です。

  1. T[i] と P[j] を比較します。
  2. 一致した場合 (T[i] == P[j]):
    • 両方のポインタを次に進めます: i++、j++。
    • もし j がパターン長 m に達したら、パターンがテキストの i-m の位置で発見されたことを意味します。発見を報告し、パターン検索を継続する場合は、パターンのポインタ j を π[m-1] に戻して（つまり、見つかったパターンの接尾辞部分を次の検索の接頭辞として利用して）、テキストの現在の位置 i から検索を続けます。
  3. 不一致の場合 (T[i] != P[j]):
    • ケース1: j > 0 の場合（パターンの途中まで一致していた場合）: パターンのポインタ j を、失敗関数を使って戻します。新しい j の値は π[j-1] となります。これにより、一致していた接頭辞 P[0...j-1] の情報（最長一致する適切な接頭辞/接尾辞の長さ π[j-1]）を利用し、テキストポインタ i はそのままに、パターンを「適切な量だけ」ずらして次の比較を行います。
    • ケース2: j == 0 の場合（パターンの先頭文字から一致しなかった場合）: パターンをずらすことはできません。テキストの現在の文字 T[i] ではパターンの先頭文字が見つからなかったということなので、テキストポインタ i を1つ進めて、テキストの次の文字 T[i+1] とパターンの先頭文字 P[0] を比較し直します。パターンのポインタ j は 0 のままです。
  4. テキストの末尾 (i == n) に達するまで、またはパターンが見つかるまで、ステップ1に戻って処理を繰り返します。

KMP検索アルゴリズム (0-indexed):

入力: テキスト T (長さ n), パターン P (長さ m), 失敗関数 π (長さ m)
出力: パターンが見つかったテキスト内のインデックス (複数または最初の一つ)

```
i = 0 // テキストのインデックス
j = 0 // パターンのインデックス

while i < n:
if P[j] == T[i]:
// 文字が一致した場合
i = i + 1
j = j + 1

if j == m:
    // パターン全体が一致した場合 (見つかった!)
    print "パターンはテキストのインデックス", i - j, "で見つかりました"
    // 次の出現を探すために、パターンポインタ j を失敗関数に基づいて戻す
    j = π[j - 1]

elif i < n and P[j] != T[i]:
    // 文字が一致せず、テキストの末尾ではない場合
    if j != 0:
        // パターンの途中まで一致していた場合
        // パターンポインタ j を失敗関数に基づいて戻す
        j = π[j - 1]
    else:
        // パターンの先頭文字から一致しなかった場合
        // テキストポインタ i を1つ進める
        i = i + 1

```

KMP検索の具体例:

テキスト T = "ABABDABACDABABCABAB" (n=19)
パターン P = "ABABCABAB" (m=9)
失敗関数 π = [0, 0, 0, 1, 2, 3, 4, 5, 6] (※このπ配列はP="ABABCABAB"に対する正しい値です。先ほどのπ計算例とはパターンが異なります。)

π計算例: P = "ABABCABAB" (m=9)
π[0] = 0
i=1, P[1]='B', len=0: 'B'!=P[0]='A', len=0 -> π[1]=0
i=2, P[2]='A', len=0: 'A'==P[0]='A', len=1 -> π[2]=1
i=3, P[3]='B', len=1: 'B'==P[1]='B', len=2 -> π[3]=2
i=4, P[4]='C', len=2: 'C'!=P[2]='A', len>0, len=π[2]=1. 'C'!=P[1]='B', len>0, len=π[1]=0. 'C'!=P[0]='A', len=0 -> π[4]=0
i=5, P[5]='A', len=0: 'A'==P[0]='A', len=1 -> π[5]=1
i=6, P[6]='B', len=1: 'B'==P[1]='B', len=2 -> π[6]=2
i=7, P[7]='A', len=2: 'A'==P[2]='A', len=3 -> π[7]=3
i=8, P[8]='B', len=3: 'B'==P[3]='B', len=4 -> π[8]=4

修正後のπ配列: [0, 0, 1, 2, 0, 1, 2, 3, 4]

では、このπ配列を使って検索を実行します。

状況 i j T[i] P[j] T[i]==P[j]? 処理 π[j-1] π[j] 備考
初期化 0 0 - - - - -
比較 0 0 A A Yes i++, j++ T[0]==P[0]
比較 1 1 B B Yes i++, j++ T[1]==P[1]
比較 2 2 A A Yes i++, j++ T[2]==P[2]
比較 3 3 B B Yes i++, j++ T[3]==P[3]
比較 4 4 D C No j != 0. j = π[j-1]=π[3] 2 T[4]!=P[4]. j=4 -> π[3]=2. 新しいj=2.
比較 4 2 D A No j != 0. j = π[j-1]=π[1] 0 T[4]!=P[2]. j=2 -> π[1]=0. 新しいj=0.
比較 4 0 D A No j == 0. i++ T[4]!=P[0]. j=0 -> i=5. jは0のまま.
比較 5 0 A A Yes i++, j++ T[5]==P[0]
比較 6 1 B B Yes i++, j++ T[6]==P[1]
比較 7 2 A A Yes i++, j++ T[7]==P[2]
比較 8 3 C B No j != 0. j = π[j-1]=π[2] 1 T[8]!=P[3]. j=3 -> π[2]=1. 新しいj=1.
比較 8 1 C B No j != 0. j = π[j-1]=π[0] 0 T[8]!=P[1]. j=1 -> π[0]=0. 新しいj=0.
比較 8 0 C A No j == 0. i++ T[8]!=P[0]. j=0 -> i=9. jは0のまま.
比較 9 0 D A No j == 0. i++ T[9]!=P[0]. j=0 -> i=10. jは0のまま.
比較 10 0 A A Yes i++, j++ T[10]==P[0]
比較 11 1 B B Yes i++, j++ T[11]==P[1]
比較 12 2 A A Yes i++, j++ T[12]==P[2]
比較 13 3 B B Yes i++, j++ T[13]==P[3]
比較 14 4 C C Yes i++, j++ T[14]==P[4]
比較 15 5 A A Yes i++, j++ T[15]==P[5]
比較 16 6 B B Yes i++, j++ T[16]==P[6]
比較 17 7 A A Yes i++, j++ T[17]==P[7]
比較 18 8 B B Yes i++, j++ T[18]==P[8]
パターン一致 19 9 - - - j == m. 発見報告. 4 j=9 (m). 発見位置 i-j = 19-9=10. 次のj=π[8]=4
(次の検索開始) 19 4 - - - i=19 (n). ループ終了 テキストの終わりに達した。

テキストのインデックス 10 でパターンが見つかりました。ナイーブ法のようにテキストポインタを巻き戻すことなく、効率的に検索が進んでいます。不一致が発生した際（例: i=4, j=4 -> i=4, j=2 -> i=4, j=0 -> i=5, j=0）、パターンポインタ j が適切にスキップされているのがわかります。

KMP検索アルゴリズムの計算量:

KMP検索アルゴリズムの計算量は、テキスト長 n、パターン長 m とすると、O(n + m) となります。これは、失敗関数 π の計算に O(m)、そして実際の検索に O(n) かかるためです。

πの計算が O(m) であることは先に説明しました。検索が O(n) である理由は以下の通りです。

  • テキストポインタ i は、P[j] == T[i] となるか、j == 0 で不一致となる場合にのみインクリメントされます。i は決してデクリメントされないため、最大で n 回しかインクリメントされません。
  • パターンポインタ j は、P[j] == T[i] となるか、パターン発見時にインクリメントされます。不一致時には j = π[j-1] となり、必ず減少します（π[j-1] < j が保証されるため）。
  • j の値は 0 から m-1 の間を遷移します。j がインクリメントされる回数は、テキストポインタ i が進む回数（最大 n 回）と、パターンが見つかる回数（最大 n/m 回）の合計で O(n) を超えません。j がデクリメントされるのは while P[j] != T[i] のループ内ですが、j がデクリメントされる総量は、それまでにインクリメントされてきた総量を超えることはありません。
  • 全体の比較回数およびポインタの移動回数は、i の移動 O(n) と j の移動 O(n) の合計で O(n) となります。

したがって、KMP法の全体の計算量は、π計算の O(m) と検索の O(n) を合わせて O(n + m) となります。これは、テキストの各文字を最大でも数回しか見ないことを意味し、ナイーブ法の O(nm) に比べて非常に効率的です。特にテキストが非常に長い場合に、KMP法の優位性が発揮されます。

KMP法の利点と適用分野

KMP法の最大の利点は、その計算量 O(n + m) です。これはテキストおよびパターンの長さに線形であり、理論的にこれ以上高速なアルゴリズムは存在しません（テキストの全ての文字を最低一度は読まなければならないため）。

また、KMP法はオンラインアルゴリズムとしての性質を持ちます。これは、テキストを最初から最後まで一度だけ順に読み進めるだけで検索が完了することを意味します。テキスト全体をメモリに保持する必要はなく、ストリームとして入力されるテキストに対しても処理が可能です（ただし、π関数はパターン全体を見て事前に計算する必要があります）。

KMP法の適用分野は多岐にわたります。

  • テキストエディタやワープロソフトでの検索・置換: 高速なキーワード検索に利用されます。
  • DNAやRNAなどのゲノム配列解析: 長大な塩基配列の中から特定のパターン（遺伝子配列など）を探す際に非常に有用です。
  • ネットワークセキュリティ: 侵入検知システム (IDS) において、パケットのストリームの中から既知の攻撃パターンやシグネチャを高速に検出するために使用されることがあります。
  • コンパイラやインタプリタ: 字句解析の段階で、入力ソースコードの中からキーワードや識別子といったパターンを認識するために使われることがあります。
  • データ圧縮: LZ77などの一部のデータ圧縮アルゴリズムの内部で、重複する文字列の検索に似た処理が行われることがあります。

まとめ

KMP法は、Knuth、Morris、Prattによって開発された、効率的な文字列検索アルゴリズムです。ナイーブ法が持つ、不一致時の非効率なテキストポインタの巻き戻しという問題を、「失敗関数（π関数）」という事前計算された情報を用いて解決します。

失敗関数 π[i] は、パターン P の接頭辞 P[0...i] において、適切な接頭辞かつ適切な接尾辞となる最長の文字列の長さを格納します。この π テーブルはパターンに対して O(m) で計算可能です。

KMP検索アルゴリズムは、テキストとパターンを順に比較していき、不一致が発生した際に、π関数を利用してパターンのポインタを適切にジャンプさせることで、テキストポインタを巻き戻すことなく検索を続行します。この検索プロセスは O(n) で完了するため、KMP法全体の計算量は O(n + m) となります。

KMP法は、その計算量の優位性から、様々な分野で高速な文字列検索を実現するために活用されています。その洗練されたアイデア、特に失敗関数によるパターンの賢いシフトのメカニズムは、アルゴリズムの美しさを示す典型例と言えるでしょう。

本稿を通して、KMP法の「なぜ効率的なのか」「どのように動作するのか」についての理解が深まったことを願います。もしさらに深く学びたい場合は、π関数の計算や検索アルゴリズムを実際にプログラムとして実装してみることをお勧めします。それが、アルゴリズムを真に自分のものにする最も良い方法です。また、Boyer-Moore法など、他の高速な文字列検索アルゴリズムについても学んでみると、文字列検索の世界の奥深さに触れることができるでしょう。

コメントする

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

上部へスクロール