Rabin-Karpアルゴリズムは、ハッシュ関数を使用してパターンとテキストの部分文字列のハッシュ値を計算し、一致するかどうかを検証します。アルゴリズムの基本的な手順は以下の通りです。
- パターンのハッシュ値を計算する。
- テキスト内の最初のパターンの長さ分の部分文字列のハッシュ値を計算する。
- パターンのハッシュ値とテキストの部分文字列のハッシュ値を比較する。
- ハッシュ値が一致した場合、実際に文字列を比較して一致するかどうかを確認する。
- パターンが見つかった場合、その位置を記録する。
- テキスト内の次の部分文字列のハッシュ値を計算し、ステップ3に戻る。
- テキストの終端まで繰り返す。
Rabin-Karpアルゴリズムの利点は、ハッシュ値を使用することで、パターンのハッシュ値と部分文字列のハッシュ値を効率的に比較できる点です。また、部分文字列のハッシュ値の再計算を最小限に抑えることもできます。
以下にRabin-KarpアルゴリズムのPythonコードの例を示します。
def rabin_karp(pattern, text):
pattern_hash = hash(pattern)
pattern_length = len(pattern)
text_length = len(text)
result = []
for i in range(text_length - pattern_length + 1):
if hash(text[i:i+pattern_length]) == pattern_hash:
if text[i:i+pattern_length] == pattern:
result.append(i)
return result上記のコードでは、rabin_karp関数を定義し、patternとtextを引数として受け取ります。関数は一致する位置のリストを返します。
このブログ投稿では、Rabin-Karpアルゴリズムの基本的な仕組みと実装方法を解説しました。このアルゴリズムは文字列マッチングの効率的な手法の一つであり、大規模なテキスト処理や文字列検索に活用されています。ぜひ実際に試してみてください。