Rabin‐Karp：ローリングハッシュを使用した効率的な部分文字列検索 - tanakakenji/Rinko GitHub Wiki

Rabin-Karp アルゴリズムの解説とC++実装

1. Rabin-Karp アルゴリズムとは？

Rabin-Karp アルゴリズムは、文字列内の部分文字列（パターン）を検索するためのアルゴリズムです。このアルゴリズムの特徴は、ハッシュ関数を使用して効率的に検索を行うことです。

主な特徴：

  • ローリングハッシュを使用
  • 複数のパターンを同時に検索可能
  • 平均的な時間複雑度は O(n + m)、最悪の場合 O(nm)

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

https://www.slideshare.net/slideshow/rolling-hash-60984153/60984153

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

  1. パターンのハッシュ値を計算する
  2. テキスト内の各部分文字列（パターンと同じ長さ）のハッシュ値を計算する
  3. パターンのハッシュ値と一致する部分文字列を見つけたら、文字ごとに比較して完全一致を確認する

ハッシュ値の計算には「ローリングハッシュ」という技術を使用します。これにより、テキスト内の連続する部分文字列のハッシュ値を効率的に計算できます。

3. C++での Rabin-Karp アルゴリズムの実装

まず、Rabin-Karp アルゴリズムとは、文字列の中から特定のパターンを効率的に検索するアルゴリズムです。このアルゴリズムの特徴は、ハッシュ関数とローリングハッシュを使用することで、検索の効率を高めているところにあります。

では、コードを書いていきましょう。まず、必要なヘッダファイルをインクルードします。

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

iostreamは入出力に、stringは文字列の操作に、vectorは動的配列を使用するために必要です。

次に、RabinKarpクラスを定義します。このクラスの中に、アルゴリズムに必要な関数を実装していきます。

class RabinKarp {
private:
    static const int PRIME = 101;  // ハッシュ計算に使用する素数
    
    // 文字列のハッシュ値を計算する関数
    long long calculateHash(const std::string& str, int length) {
        // ...
    }
    
    // ローリングハッシュを計算する関数
    long long recalculateHash(long long oldHash, char oldChar, char newChar, long long power) {
        // ...
    }
    
    // 256のpower乗をPRIMEで割った余りを計算する関数
    long long calculatePower(int power) {
        // ...
    }
public:
    // パターンを検索する関数
    std::vector<int> search(const std::string& text, const std::string& pattern) {
        // ...
    }
};

PRIMEは、ハッシュ計算に使用する素数です。素数を使うことで、ハッシュ値の衝突を減らすことができます。

次に、calculateHash関数を実装します。この関数は、与えられた文字列のハッシュ値を計算します。

long long calculateHash(const std::string& str, int length) {
    long long hash = 0;
    for (int i = 0; i < length; i++) {
        hash = (hash * 256 + str[i]) % PRIME;
    }
    return hash;
}

ここでは、文字列の各文字をASCIIコードに変換し、256進数のように扱って計算しています。% PRIMEを使うことで、ハッシュ値を素数で割った余りを求めています。

次は、recalculateHash関数です。この関数は、ローリングハッシュを使って、既存のハッシュ値から新しいハッシュ値を効率的に計算します。

long long recalculateHash(long long oldHash, char oldChar, char newChar, long long power) {
    long long newHash = (oldHash - oldChar * power) % PRIME;
    newHash = (newHash * 256 + newChar) % PRIME;
    return newHash < 0 ? newHash + PRIME : newHash;
}

ここでは、前の部分文字列のハッシュ値(oldHash)から、最初の文字(oldChar)を取り除き、新しい文字(newChar)を追加することで、新しい部分文字列のハッシュ値を計算しています。powerは、oldCharに掛ける値で、256の累乗をPRIMEで割った余りを表します。

calculatePower関数は、powerの値を計算するために使います。

long long calculatePower(int power) {
    long long result = 1;
    for (int i = 0; i < power; i++) {
        result = (result * 256) % PRIME;
    }
    return result;
}

最後に、search関数を実装します。この関数は、与えられたテキスト内でパターンを検索し、パターンが見つかった位置を返します。

std::vector<int> search(const std::string& text, const std::string& pattern) {
    std::vector<int> result;
    int n = text.length();
    int m = pattern.length();
    
    if (m > n) return result;
    
    long long patternHash = calculateHash(pattern, m);
    long long textHash = calculateHash(text, m);
    long long power = calculatePower(m - 1);
    
    for (int i = 0; i <= n - m; i++) {
        if (patternHash == textHash) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                result.push_back(i);
            }
        }
        
        if (i < n - m) {
            textHash = recalculateHash(textHash, text[i], text[i + m], power);
        }
    }
    
    return result;
}

この関数では、以下のステップでパターンを検索します：

  1. パターンとテキストの最初の部分文字列のハッシュ値を計算します。
  2. ハッシュ値が一致した場合、文字ごとに比較して完全一致を確認します。
  3. テキスト内の次の部分文字列に移動し、ローリングハッシュを使用して新しいハッシュ値を計算します。
  4. ステップ2と3を繰り返します。

resultベクターには、パターンが見つかった位置が格納されます。

以上が、Rabin-Karp アルゴリズムのC++実装の解説です。ハッシュ関数とローリングハッシュを使うことで、効率的な文字列検索を実現しています。

5. 使用例

では、Rabin-Karp アルゴリズムの実際の使用例を見てみましょう。

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

int main() {
    std::string text = "abracadabra";
    std::string pattern = "abr";

    RabinKarp rabinKarp;
    std::vector<int> result = rabinKarp.search(text, pattern);

    if (result.empty()) {
        std::cout << "パターンが見つかりませんでした。" << std::endl;
    } else {
        std::cout << "パターンが見つかった位置：";
        for (int i = 0; i < result.size(); i++) {
            std::cout << result[i] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

この例では、"abracadabra"という文字列の中から、"abr"というパターンを検索しています。

RabinKarpクラスのインスタンスを作成し、search関数を呼び出して検索を行います。

RabinKarp rabinKarp;
std::vector<int> result = rabinKarp.search(text, pattern);

search関数は、パターンが見つかった位置をvector<int>型で返します。

結果を確認するために、resultが空であるかどうかを確認します。空の場合は、パターンが見つからなかったことを意味します。

if (result.empty()) {
    std::cout << "パターンが見つかりませんでした。" << std::endl;
} else {
    std::cout << "パターンが見つかった位置：";
    for (int i = 0; i < result.size(); i++) {
        std::cout << result[i] << " ";
    }
    std::cout << std::endl;
}

パターンが見つかった場合は、その位置を出力します。

この例を実行すると、以下のような出力が得られます：

パターンが見つかった位置：0 7

これは、"abr"というパターンが、"abracadabra"の0番目と7番目の位置に見つかったことを示しています。

Rabin-Karp アルゴリズムは、文字列検索だけでなく、重複検出やプラグイアリズム検出などにも応用できます。

また、このアルゴリズムの時間計算量は、平均でO(n+m)（nはテキストの長さ、mはパターンの長さ）です。ただし、ハッシュ値の衝突が多く発生する場合、最悪でO(nm)になることがあります。

以上が、Rabin-Karp アルゴリズムの解説でした。アルゴリズムの仕組みを理解し、実装できるようになれば、様々な問題に応用できるようになるでしょう。

これからも、アルゴリズムの学習を楽しんでいってくださいね。がんばりましょう！

6. Rabin-Karp アルゴリズムの利点と欠点

利点：

  • 複数のパターンを同時に検索可能
  • 平均的なケースでは効率的（O(n + m)）
  • ハッシュ計算が単純で高速

欠点：

  • 最悪の場合の時間複雑度は O(nm)
  • ハッシュ衝突の可能性がある（ただし、適切な素数を選ぶことで最小化可能）

まとめ

Rabin-Karp アルゴリズムは、ハッシュ関数とローリングハッシュの概念を使用して効率的な文字列検索を実現します。特に複数のパターンを同時に検索する必要がある場合に有用です。ただし、最悪の場合のパフォーマンスや潜在的なハッシュ衝突には注意が必要です。適切な使用ケースを理解し、他のストリングマッチングアルゴリズム（例：KMP アルゴリズム）と比較検討することが重要です。

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