Pythonによるクヌース・モリス・プラット法(KMP法)の実装

クヌース・モリス・プラット法(Knuth-Morris-Pratt algorithm、KMP法)は、文字列検索アルゴリズムの一つで、テキスト中から特定のパターンを効率的に検索します。 KMP法は、検索対象のテキストの長さを n、パターンの長さを m とすると、時間計算量 O(n + m) で検索を実現します。この記事ではKMP法のアルゴリズムを解説し、Pythonでの実装方法を解説していきます。

• KMP法とは
  • KMP法のアルゴリズム
  • アルゴリズムの具体例
    • 1. LPS Tableの作成
    • 2. テキストの検索
• Pythonでの実装
  • 1. LPS Tableの作成
  • 2. テキストの検索
  • 3. 実行例
• KMP法の計算量
  • 時間計算量
    • 1. LPSテーブルの作成 (O(m))
    • 2. テキストの検索 (O(n))
    • 全体の時間計算量
  • 空間計算量
• まとめ

KMP法とは

KMP法は、パターンの接頭辞(prefix)と接尾辞(suffix)の情報を用いて、検索中の無駄な比較を省略します。通常の検索では不一致が起こった場合に１文字ずらし最初からやり直しますが、KMPでは不一致があってもそれまでの比較結果を活かして比較回数を減らせます。

具体的には、パターン自体の中に、そのパターンの接頭辞と接尾辞が一致する部分があるかを事前に計算しておきます。この事前計算の結果をテーブル(LPS Table)として保持し、検索時に活用します。

KMP法のアルゴリズム

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

1. LPS Table (Longest Proper Prefix which is also Suffix) の作成 パターンの各位置について、「その位置を末尾とする部分文字列」の接頭辞と接尾辞が最大何文字一致するかを記録します。ただし、接尾辞は部分文字列全体とは一致しない最長のものを採用します。

2. テキストの検索 LPS Table を参照しながら、テキストとパターンを比較します。不一致が発生した場合、LPS Table の値を利用して、パターンの比較開始位置を適切にシフトします。

アルゴリズムの具体例

パターンP = "ABABCABAB"、テキストT = "ABABDABABCABAB"として、KMP法のアルゴリズムの動作を具体的に説明します。

1. LPS Tableの作成

まず、パターンPに対するLPS Tableを作成します。

i	P[i]	部分文字列	最長接頭辞かつ接尾辞	長さ(lps[i])
0	A	A		0
1	B	AB		0
2	A	ABA	A	1
3	B	ABAB	AB	2
4	C	ABABC		0
5	A	ABABCA	A	1
6	B	ABABCAB	AB	2
7	A	ABABCABA	ABA	3
8	B	ABABCABAB	ABAB	4

このテーブルから、lps = [0, 0, 1, 2, 0, 1, 2, 3, 4] が得られます。

2. テキストの検索

次に、作成したLPS Tableを用いてテキストTからパターンPを検索します。

T[i]	P[j]	i	j	比較	jの更新(不一致時)	動作
A	A	0	0	一致		i++, j++
B	B	1	1	一致		i++, j++
A	A	2	2	一致		i++, j++
B	B	3	3	一致		i++, j++
D	C	4	4	不一致	j = lps[3] = 2	jを2に更新(Pの"AB"まで一致していたことを利用)
D	A	4	2	不一致	j = lps[1] = 0	jを0に更新
D	A	4	0	不一致		jが0なのでi++
A	A	5	0	一致		i++, j++
B	B	6	1	一致		i++, j++
A	A	7	2	一致		i++, j++
B	B	8	3	一致		i++, j++
C	C	9	4	一致		i++, j++
A	A	10	5	一致		i++, j++
B	B	11	6	一致		i++, j++
A	A	12	7	一致		i++, j++
B	B	13	8	一致		i++, j++ j==mとなり、パターン発見(位置5)
					j = lps[7] = 3	jを3に更新し、次の検索に備える

上記のように、KMP法は不一致が発生した際に、LPS Tableを利用してjを効率的に更新することで、無駄な比較を省きながらテキスト検索を行います。

Pythonでの実装

1. LPS Tableの作成

def compute_lps_table(pattern):
    """パターンのLPS Tableを計算する"""
    m = len(pattern)
    lps = [0] * m  # LPS Tableを0で初期化
    length = 0  # 一致した接頭辞の長さ
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            # 一致した場合、lengthをインクリメントし、lps[i]にlengthを記録
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # 不一致だが、lengthが0ではない場合、lengthを1つ前のLPSの値に更新
                length = lps[length - 1]
            else:
                # 不一致かつlengthが0の場合、lps[i]は0のまま
                i += 1
    return lps

2. テキストの検索

def kmp_search(text, pattern):
    """KMP法でテキストからパターンを検索する"""
    n = len(text)
    m = len(pattern)
    lps = compute_lps_table(pattern)  # LPS Tableを計算
    i = 0  # textのインデックス
    j = 0  # patternのインデックス
    results = [] # 発見したインデックスを格納

    while i < n:
        if pattern[j] == text[i]:
            # 一致した場合、両方のインデックスを進める
            i += 1
            j += 1

        if j == m:
            # パターン全体が一致した場合、結果を記録し、jをLPS Tableを使って更新
            results.append(i - j)
            j = lps[j - 1]

        elif i < n and pattern[j] != text[i]:
            # 不一致の場合、jが0でなければLPS Tableを使ってjを更新
            if j != 0:
                j = lps[j - 1]
            else:
                # jが0の場合、textのインデックスを進める
                i += 1
    return results

3. 実行例

text = "ABABDABABCABAB"
pattern = "ABABCABAB"
results = kmp_search(text, pattern)
print(f"Found pattern at indices: {results}")  # 出力: Found pattern at indices: [5]

text = "ABABAABA"
pattern = "ABA"
results = kmp_search(text, pattern)
print(f"Found pattern at indices: {results}")  # 出力: Found pattern at indices: [0, 5]

KMP法の計算量

KMP法全体の計算量は以下の通りです。

• 時間計算量: O(n + m)
  • LPSテーブルの作成: O(m)
  • テキストの検索: O(n)
• 空間計算量: O(m) （主にLPSテーブルのため）

ここで、 * n はテキストの長さ * m はパターンの長さ です。

時間計算量

時間計算量は、アルゴリズムが実行に要する時間を見積もるための指標です。KMP法では、「LPSテーブルの作成」と「テキストの検索」の2つの部分の時間計算量を合計して考えます。

1. LPSテーブルの作成 (O(m))

パターンの各文字を順番に処理していくため、パターンの長さ m に比例した時間がかかります。したがって、LPSテーブル作成の時間計算量は O(m) となります。

2. テキストの検索 (O(n))

テキストの各文字を順番に処理していくため、テキストの長さ n に比例した時間がかかります。したがって、テキスト検索の時間計算量は O(n) となります。

全体の時間計算量

LPSテーブルの作成 (O(m)) とテキストの検索 (O(n)) の時間計算量を合計して、KMP法全体の時間計算量は O(n + m) となります。

空間計算量

空間計算量は、アルゴリズムが実行中にどれくらいのメモリ（記憶領域）を使用するかを見積もる指標です。

LPSテーブルのサイズはパターンの長さ m に比例します。したがって、KMP法の空間計算量は O(m) となります。

まとめ

PythonによるKMP法の実装を、具体例と詳細な解説を交えて説明しました。KMP法は、文字列検索を効率的に行うための強力なアルゴリズムであり、特に長いテキストや繰り返し出現するパターンを検索する場合にその真価を発揮します。