KMP (Knuth‐Morris‐Pratt) アルゴリズムの解説とC 実装 - tanakakenji/Rinko GitHub Wiki

KMP (Knuth-Morris-Pratt) アルゴリズムの解説とC++実装

1. KMPアルゴリズムとは？

KMP (Knuth-Morris-Pratt) アルゴリズムは、文字列内の部分文字列（パターン）を効率的に検索するためのアルゴリズムです。1977年にDonald Knuth、Vaughan Pratt、James H. Morrisによって開発されました。

主な特徴：

  • パターンの接頭辞情報を利用して不要な比較をスキップ
  • 線形時間複雑度 O(n + m)
  • テキストを後戻りせずに一度だけ走査

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

2. アルゴリズムの基本的な考え方

https://www.youtube.com/watch?v=zYuWNezP50Q https://www.youtube.com/watch?v=7JjspD0qBJE https://daeudaeu.com/kmp/

  1. パターンの接頭辞情報を事前に計算し、失敗関数（または部分一致テーブル）を作成
  2. テキストとパターンを左から右へ比較
  3. 不一致が発生した場合、失敗関数を使用して次の比較位置にジャンプ
  4. テキストを一度だけ走査して検索を完了

KMPの鍵となるアイデアは、パターン自身の情報を利用して、不一致が発生した際に効率的にスキップすることです。

3. C++でのKMPアルゴリズムの実装

はい、生徒の皆さん。今日は、文字列探索アルゴリズムの中でも非常に効率的なKMP（Knuth-Morris-Pratt）アルゴリズムについて学んでいきましょう。このアルゴリズムは、大きなテキスト中から特定のパターンを高速に見つけ出すのに役立ちます。

まずは、C++を使ってこのアルゴリズムを一緒に実装していきましょう。ゆっくりと進めていきますので、しっかりついてきてくださいね。

まず、必要なヘッダーファイルをインクルードします。

#include <iostream>
#include <vector>
#include <string>

ここでは、iostreamは入出力のため、vectorは動的配列を使うため、stringは文字列を扱うために必要です。C++では、これらの標準ライブラリを使うことで、より効率的にプログラミングができるんですよ。

次に、KMPアルゴリズムのためのクラスを定義します。

class KMP {
private:
    // ここに後でプライベートメンバ関数を追加します
public:
    // ここに後でパブリックメンバ関数を追加します
};

クラスを使うことで、関連する関数とデータをまとめて管理できます。privateとpublicというキーワードは、カプセル化という概念を実現するために使われます。privateは、クラスの外からアクセスできない部分、publicは外からアクセスできる部分を指定します。

では、まず重要な部分である「失敗関数」（LPS: Longest Proper Prefix which is also Suffix）の計算を行う関数を実装しましょう。

private:
    std::vector<int> computeLPS(const std格納std::string& pattern) {
        int m = pattern.length();
        std::vector<int> lps(m, 0);
        int len = 0;
        int i = 1;

ここでは、patternの長さmを取得し、その長さと同じサイズのlpsベクターを作成しています。lpsは全て0で初期化されています。

lenは現在の最長の接頭辞かつ接尾辞の長さを、iはパターン内の現在の位置を表します。 はい、続けましょう。失敗関数の計算を完成させていきます。

        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

このwhileループは、パターン全体を走査しながらLPS（Longest Proper Prefix which is also Suffix）テーブルを構築しています。ここでの考え方を説明しましょう。

  1. pattern[i]とpattern[len]が一致する場合：

    • 最長の接頭辞かつ接尾辞の長さ（len）を1増やします。
    • その長さをlps[i]に格納します。
    • パターン内の位置（i）を次に進めます。

  2. 一致しない場合：

    • もしlenが0でなければ、前の最長の接頭辞かつ接尾辞の情報を使ってlenを更新します。
    • lenが0の場合は、lps[i]を0にしてパターン内の位置（i）を次に進めます。

このアルゴリズムは、パターン自身の中での繰り返しを効率的に見つけ出すことで、後の文字列探索を高速化するための準備をしているんです。

さて、次は実際の検索を行うメソッドを実装しましょう。publicセクションに以下のコードを追加します：

public:
    std::vector<int> search(const std::string& text, const std::string& pattern) {
        std::vector<int> result;
        int n = text.length();
        int m = pattern.length();
        std::vector<int> lps = computeLPS(pattern);
        int i = 0;  // テキストのインデックス
        int j = 0;  // パターンのインデックス

ここでは、searchメソッドを定義しています。このメソッドは、テキストとパターンを受け取り、パターンが見つかった位置のリストを返します。

  • resultベクターは、パターンが見つかった位置を格納します。
  • nとmは、それぞれテキストとパターンの長さです。
  • lpsは、先ほど実装したcomputeLPSメソッドを使って計算します。
  • iとjは、それぞれテキストとパターン内の現在の位置を表すインデックスです。

これらの準備ができたら、実際の検索処理に入ります。この部分は少し複雑なので、一緒にゆっくり見ていきましょう。 はい、では検索処理の核心部分に入っていきましょう。searchメソッドの続きを実装します：

        while (i < n) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            if (j == m) {
                result.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return result;
    }

この部分を詳しく解説していきますね。

  1. while (i < n) : テキスト全体を走査するまで続けます。

  2. if (pattern[j] == text[i]) : パターンとテキストの現在の文字が一致する場合

    • 両方のインデックス（iとj）を進めます。

  3. if (j == m) : パターン全体が一致した場合

    • 見つかった位置（i - j）をresultに追加します。
    • 次の潜在的な一致を探すため、jをlps[j - 1]にセットします。これがKMPアルゴリズムの効率的な部分です。

  4. else if (i < n && pattern[j] != text[i]) : 不一致が発生した場合

    • if (j != 0) : パターンの先頭以外で不一致が起きた場合
      • j = lps[j - 1] : LPSテーブルを使ってjをジャンプさせます。これにより、既に一致が確認された部分を再度チェックする必要がなくなります。
    • else : パターンの先頭で不一致が起きた場合
      • i++ : テキストの次の文字に移動します。

  5. 最後にreturn result : 見つかった全ての位置を返します。

このアルゴリズムの巧妙な点は、不一致が起きた時にLPSテーブルを使ってパターンのインデックス（j）を効率的に移動させることです。これにより、ブルートフォース法と比べて大幅に計算量を削減できるんです。

C++初心者の皆さんにとっては、vectorや参照渡し（const std::string&）といった概念が新しいかもしれませんね。vectorは動的配列で、サイズを変更できるリストのようなものです。参照渡しは、大きなデータを効率的に関数に渡すための方法です。

このKMPアルゴリズムを使えば、例えば長い文章の中から特定の単語や文を高速に見つけ出すことができます。ゲノム解析や文書処理など、さまざまな分野で活用されている重要なアルゴリズムなんですよ。

皆さん、ここまでついてこれましたか？質問があれば、遠慮なく聞いてくださいね。 はい、では実際にこのKMPアルゴリズムを使ってみましょう。メインプログラムを書いて、動作を確認してみましょう。

int main() {
    KMP kmp;
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";

    std::cout << "テキスト: " << text << std::endl;
    std::cout << "パターン: " << pattern << std::endl;

    std::vector<int> positions = kmp.search(text, pattern);

    if (positions.empty()) {
        std::cout << "パターンは見つかりませんでした。" << std::endl;
    } else {
        std::cout << "パターンが見つかった位置: ";
        for (int pos : positions) {
            std::cout << pos << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

このメイン関数では以下のことを行っています：

  1. KMPクラスのインスタンスを作成します。
  2. サンプルのテキストとパターンを定義します。
  3. searchメソッドを呼び出して、パターンがテキスト内で見つかる位置を取得します。
  4. 結果を表示します。パターンが見つからなかった場合はその旨を、見つかった場合は見つかった位置を出力します。

このプログラムを実行すると、次のような出力が得られるはずです：

テキスト: ABABDABACDABABCABAB
パターン: ABABCABAB
パターンが見つかった位置: 10

これは、パターン "ABABCABAB" がテキスト "ABABDABACDABABCABAB" の10番目の位置（0から数えて）で見つかったことを示しています。

さて、ここで少し復習をしましょう。KMPアルゴリズムの主な利点は何だったでしょうか？

  1. 効率性: ブルートフォース法と比べて、テキストの各文字を最大1回しか調べません。これにより、特に長いテキストやパターンで大きな効果を発揮します。

  2. 前処理: パターンの接頭辞と接尾辞の情報（LPSテーブル）を事前に計算することで、不一致が起きた際に効率的にスキップできます。

  3. 線形時間複雑度: テキストの長さをn、パターンの長さをmとすると、KMPアルゴリズムの時間複雑度はO(n+m)です。これはブルートフォース法のO(nm)よりも大幅に改善されています。

このアルゴリズムを理解することは、より複雑な文字列処理や他の効率的なアルゴリズムを学ぶ上での良い基礎となります。

皆さん、KMPアルゴリズムについて理解できましたか？もし疑問点や、もっと詳しく知りたい部分があれば、遠慮なく質問してくださいね。プログラミングは実践を通じて学ぶのが一番です。ぜひ、このコードを自分で打ち込んで実行してみてください。そして、テキストやパターンを変えて、どのように動作が変わるか確認してみるのも良いでしょう。

5. 使用例

int main() {
    KMP kmp;
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    
    std::vector<int> positions = kmp.search(text, pattern);
    
    if (positions.empty()) {
        std::cout << "Pattern not found." << std::endl;
    } else {
        std::cout << "Pattern found at positions: ";
        for (int pos : positions) {
            std::cout << pos << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

出力：

Pattern found at positions: 10

この例では、テキスト "ABABDABACDABABCABAB" 内でパターン "ABABCABAB" を検索しています。アルゴリズムは正しく位置 10 を見つけ出しています。

6. KMPアルゴリズムの利点と欠点

利点：

  • 線形時間複雑度 O(n + m)
  • テキストを一度だけ走査
  • 大きなテキストや長いパターンに対して効率的

欠点：

  • 実装がやや複雑
  • 短いパターンや小さなアルファベットに対しては、単純な文字列検索アルゴリズムの方が実際には速い場合がある

まとめ

KMPアルゴリズムは、パターンの自己情報を利用して効率的な文字列検索を実現します。特に長いテキストや頻繁に繰り返されるパターンを含むテキストに対して有効です。アルゴリズムの鍵となる部分は失敗関数（LPS）の計算と、それを利用した効率的なスキップです。

KMPアルゴリズムは、その効率性と線形時間複雑度のため、多くの文字列処理タスクで重要な役割を果たしています。ただし、実装の複雑さや、短いパターンに対する実際の性能を考慮し、使用ケースに応じて適切なアルゴリズムを選択することが重要です。

⚠️ **GitHub.com Fallback** ⚠️