KMP法(Knuth-Morris-Pratt)アルゴリズム入門 | サンプルコード付き

テキストの中から特定の部分文字列（パターン）を見つけ出す処理は、文字列処理における基本的な操作の一つです。この処理を行うアルゴリズムは数多く存在しますが、その中でも効率性とエレガントさで際立っているのが、KMP法(Knuth-Morris-Pratt)アルゴリズムです。

この記事では、KMP法の背後にある考え方、具体的な動作、そしてその実装について、サンプルコードを交えながら詳細に解説します。

1. 文字列検索アルゴリズムの基礎

KMP法を理解する前に、まず基本的な文字列検索アルゴリズムの考え方をおさらいしておきましょう。

1.1 ナイーブな文字列検索アルゴリズム

最も単純な方法は、ナイーブな文字列検索です。これは、テキストとパターンを先頭から順番に比較し、一致しなければテキスト側の比較開始位置を一つ進めて再度比較を行う、というものです。

例えば、テキスト"ABCABDABACDABABCABAB"からパターン"ABAB"を検索する場合、以下のようになります。

テキストの最初の4文字"ABCA"とパターン"ABAB"を比較。一致しない。
テキストの2文字目から4文字"BCAB"とパターン"ABAB"を比較。一致しない。
テキストの3文字目から4文字"CABD"とパターン"ABAB"を比較。一致しない。
…
テキストの17文字目から4文字"ABAB"とパターン"ABAB"を比較。一致。

この方法は非常に直感的ですが、非効率な面があります。特にパターンの中に同じ文字が繰り返し現れる場合、何度も同じ比較を繰り返してしまう可能性があります。最悪の場合、テキストの長さがn、パターンの長さがmのとき、O(n*m)の計算量が必要となります。

1.2 ナイーブなアルゴリズムの課題

ナイーブなアルゴリズムの課題は、一致しなかった場合に比較開始位置を必ず1つ進める点にあります。一致しなかった箇所に、パターンをずらすことで一致する可能性があるにも関わらず、それを無視してしまうのです。

例えば、上記の例で、テキスト"ABCABDABACDABABCABAB"とパターン"ABAB"を比較している途中で、以下のような状況になったとします。

テキスト: ABCABDABACDABABCABAB パターン: ABAB

この状況で、ナイーブなアルゴリズムでは、テキストの比較開始位置を1つ進めて、"CABD"と"ABAB"を比較します。しかし、"ABAB"の最初の"AB"は、テキストの"AB"と一致しているため、パターンを1つずらすのではなく、もっと効率的にずらすことができるはずです。

2. KMP法の核心：最長接頭辞・最長接尾辞の利用

KMP法は、このナイーブなアルゴリズムの非効率性を解消するために、最長接頭辞・最長接尾辞という概念を利用します。

2.1 接頭辞と接尾辞

ある文字列Sに対して、以下の2つを定義します。

接頭辞: Sの先頭から始まる部分文字列。例えば、"ABAB"の接頭辞は、"", "A", "AB", "ABA", "ABAB"です。
接尾辞: Sの末尾から始まる部分文字列。例えば、"ABAB"の接尾辞は、"", "B", "AB", "BAB", "ABAB"です。

2.2 最長接頭辞・最長接尾辞（Proper Prefix/Suffix）

ある文字列Sに対して、S自身を除いた接頭辞と接尾辞の中で、最長のものをそれぞれ最長接頭辞と最長接尾辞と呼びます。ただし、最長接頭辞と最長接尾辞は一致している必要があります。

例えば、"ABABC"の場合:

接頭辞: "", "A", "AB", "ABA", "ABAB"
接尾辞: "", "C", "BC", "ABC", "BABC"

この場合、最長接頭辞と最長接尾辞は存在しません（空文字列を除く）。

一方、"ABAB"の場合:

接頭辞: "", "A", "AB", "ABA"
接尾辞: "", "B", "AB", "BAB"

この場合、最長接頭辞・最長接尾辞は"AB"です。

2.3 最長接頭辞・最長接尾辞の活用

KMP法では、パターンの各部分文字列に対して、その部分文字列の最長接頭辞・最長接尾辞の長さを事前に計算しておきます。この情報を利用することで、パターンがテキストと一致しなかった場合に、どれだけパターンをずらせば良いかを効率的に判断できます。

例えば、パターン"ABAB"を検索していて、テキストとの比較が以下のようになったとします。

テキスト: ...ABABX... パターン: ABABY

ここで、テキストの"ABAB"までは一致していますが、最後の文字XとYが一致しませんでした。このとき、パターン"ABAB"の最長接頭辞・最長接尾辞は"AB"です。つまり、"ABAB"の先頭2文字"AB"と末尾2文字"AB"は同じ文字列であるということです。

したがって、パターンを以下のようにずらすことで、テキストの"AB"とパターンの"AB"を一致させることができます。

テキスト: ...ABABX... パターン: ABABY

このように、KMP法では、一致しなかった場合に、最長接頭辞・最長接尾辞の情報を用いて、パターンを効率的にずらすことで、無駄な比較を避けることができます。

3. KMP法の具体的な動作

KMP法は、以下の2つのステップで構成されます。

プレフィックス関数 (Prefix Function) の計算: パターンの各位置に対して、その位置までの部分文字列の最長接頭辞・最長接尾辞の長さを計算します。この結果は、失敗関数 (Failure Function) または next配列と呼ばれる配列に格納されます。
検索: テキストとパターンを比較し、一致しなかった場合には、失敗関数を参照してパターンの位置を効率的にずらします。

3.1 プレフィックス関数 (Prefix Function) の計算

プレフィックス関数 π[i] は、パターンの先頭から i 番目までの部分文字列 pattern[0...i] の最長接頭辞・最長接尾辞の長さを表します。

例えば、パターン"ABAB"の場合、プレフィックス関数は以下のようになります。

i	pattern[0…i]	最長接頭辞・最長接尾辞	π[i]
0	“A”	“”	0
1	“AB”	“”	0
2	“ABA”	“A”	1
3	“ABAB”	“AB”	2

したがって、失敗関数 (next配列) は [0, 0, 1, 2] となります。

プレフィックス関数の計算アルゴリズム

プレフィックス関数は、動的計画法 (Dynamic Programming) の考え方を用いて効率的に計算できます。

以下に、プレフィックス関数を計算するアルゴリズムを示します。

“`python
def compute_prefix_function(pattern):
“””
パターンに対して、プレフィックス関数 (失敗関数) を計算します。

Args:
pattern: 検索対象のパターン文字列

Returns:
prefix_function: プレフィックス関数 (next配列)
“””
m = len(pattern)
prefix_function = [0] * m
length = 0 # 一致している接頭辞の長さ

for i in range(1, m):
while length > 0 and pattern[i] != pattern[length]:
length = prefix_function[length – 1] # 一致する接頭辞が見つかるまで縮小

if pattern[i] == pattern[length]:
  length += 1

prefix_function[i] = length

return prefix_function
“`

アルゴリズムの説明

prefix_functionは、プレフィックス関数 (next配列) を格納するリストです。初期値はすべて0です。
lengthは、現在一致している接頭辞の長さを表します。初期値は0です。
ループを1からm-1まで回します。
whileループでは、lengthが0より大きく、かつ現在の文字pattern[i]とpattern[length]が一致しない場合、一致する接頭辞が見つかるまでlengthを縮小します。この処理は、lengthをprefix_function[length - 1]に更新することで行います。これは、pattern[0...length-1]の最長接頭辞・最長接尾辞の長さを取得していることになります。
現在の文字pattern[i]とpattern[length]が一致する場合、lengthを1増やします。
prefix_function[i]にlengthを格納します。

3.2 検索

テキストとパターンを比較し、一致しなかった場合には、失敗関数を参照してパターンの位置を効率的にずらす処理を行います。

以下に、検索アルゴリズムを示します。

“`python
def kmp_search(text, pattern):
“””
KMPアルゴリズムを用いて、テキストからパターンを検索します。

Args:
text: 検索対象のテキスト文字列
pattern: 検索対象のパターン文字列

Returns:
matches: パターンが見つかったインデックスのリスト
“””
n = len(text)
m = len(pattern)
prefix_function = compute_prefix_function(pattern) # プレフィックス関数を計算
matches = []
length = 0 # 一致しているパターンの長さ

for i in range(n):
while length > 0 and text[i] != pattern[length]:
length = prefix_function[length – 1] # 一致する接頭辞が見つかるまで縮小

if text[i] == pattern[length]:
  length += 1

if length == m:
  matches.append(i - m + 1)  # パターンが見つかったインデックスを追加
  length = prefix_function[length - 1]  # 次の検索のために長さを更新

return matches
“`

アルゴリズムの説明

prefix_functionは、事前に計算されたプレフィックス関数 (next配列) です。
matchesは、パターンが見つかったインデックスを格納するリストです。
lengthは、現在一致しているパターンの長さを表します。初期値は0です。
ループを0からn-1まで回します。
whileループでは、lengthが0より大きく、かつ現在の文字text[i]とpattern[length]が一致しない場合、一致する接頭辞が見つかるまでlengthを縮小します。この処理は、lengthをprefix_function[length - 1]に更新することで行います。
現在の文字text[i]とpattern[length]が一致する場合、lengthを1増やします。
lengthがmになった場合、つまりパターンが完全に一致した場合、matchesにパターンの開始インデックスi - m + 1を追加します。
次の検索のために、lengthをprefix_function[length - 1]に更新します。これは、パターンが一致した場合、最長接頭辞・最長接尾辞の長さだけパターンをずらすことに相当します。

4. KMP法の計算量

KMP法の計算量は、プレフィックス関数の計算と検索の2つのステップに分けて考えることができます。

プレフィックス関数の計算: プレフィックス関数の計算は、パターンの長さをmとした場合、O(m)の計算量で実行できます。
検索: 検索は、テキストの長さをn、パターンの長さをmとした場合、O(n)の計算量で実行できます。

したがって、KMP法全体の計算量は、O(n + m)となります。これは、ナイーブなアルゴリズムのO(n*m)と比較して、大幅に効率的です。

5. サンプルコード (Python)

以下に、KMP法をPythonで実装したサンプルコードを示します。

“`python
def compute_prefix_function(pattern):
“””
パターンに対して、プレフィックス関数 (失敗関数) を計算します。

Args:
pattern: 検索対象のパターン文字列

Returns:
prefix_function: プレフィックス関数 (next配列)
“””
m = len(pattern)
prefix_function = [0] * m
length = 0 # 一致している接頭辞の長さ

for i in range(1, m):
while length > 0 and pattern[i] != pattern[length]:
length = prefix_function[length – 1] # 一致する接頭辞が見つかるまで縮小

if pattern[i] == pattern[length]:
  length += 1

prefix_function[i] = length

return prefix_function

def kmp_search(text, pattern):
“””
KMPアルゴリズムを用いて、テキストからパターンを検索します。

Args:
text: 検索対象のテキスト文字列
pattern: 検索対象のパターン文字列

for i in range(n):
while length > 0 and text[i] != pattern[length]:
length = prefix_function[length – 1] # 一致する接頭辞が見つかるまで縮小

if text[i] == pattern[length]:
  length += 1

if length == m:
  matches.append(i - m + 1)  # パターンが見つかったインデックスを追加
  length = prefix_function[length - 1]  # 次の検索のために長さを更新

return matches

例

text = “ABCABDABACDABABCABAB”
pattern = “ABAB”

matches = kmp_search(text, pattern)

print(f”Text: {text}”)
print(f”Pattern: {pattern}”)
print(f”Matches at indices: {matches}”)
“`

実行結果

Text: ABCABDABACDABABCABAB Pattern: ABAB Matches at indices: [16]

6. KMP法の応用

KMP法は、単なる文字列検索アルゴリズムとしてだけでなく、様々な応用が可能です。

DNAシーケンス解析: DNAシーケンスにおける特定のパターンを検索するために使用できます。
テキストエディタ: テキストエディタの検索機能で、効率的な文字列検索を実現できます。
侵入検知システム (IDS): ネットワークトラフィックから悪意のあるパターンを検知するために使用できます。
データ圧縮: 特定のパターンをより短いコードに置き換えることで、データの圧縮率を向上させることができます。

7. まとめ

KMP法は、最長接頭辞・最長接尾辞の概念を利用することで、ナイーブな文字列検索アルゴリズムよりも大幅に効率的な文字列検索を実現するアルゴリズムです。その計算量はO(n + m)であり、特にパターンの中に同じ文字が繰り返し現れる場合に、その効果を発揮します。

この記事では、KMP法の背後にある考え方、具体的な動作、そしてその実装について、サンプルコードを交えながら詳細に解説しました。KMP法は、文字列処理における基本的なアルゴリズムであり、その理解はプログラミングスキルを向上させる上で非常に重要です。

KMP法を理解し、適切に活用することで、文字列処理に関する様々な問題を効率的に解決することができます。

8. 参考文献

Knuth, D. E., Morris, Jr, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323-350.
Wikipedia – Knuth–Morris–Pratt algorithm

この記事が、KMP法を理解するための助けとなれば幸いです。