Python の Rabin-Karp アルゴリズム

Python で Rabin-Karp アルゴリズムを紹介し、Python プログラムでそれを使用する方法について説明します。

Python の Rabin-Karp アルゴリズム

Rabin-Karp アルゴリズムは、特定の入力または値から特定の数字、文字、またはパターンを見つけます。 機械学習アルゴリズムは、データから洞察を抽出する必要がある場合、データ サイエンスの頼りになるソリューションであることがよくありますが、すべてのアルゴリズムが同じように作成されているわけではありません。

適切な洞察を見つけるのに優れている人もいれば、誤検知を回避するのに優れている人もいます。 適切な洞察を見つけるための最も強力な機械学習アルゴリズムの 1つは、Rabin-Karp アルゴリズムです。

Rabin-Karp アルゴリズムを使用して、一連のテキストと考えられるパスワードの間で最適な一致を見つけます。 これは主にソフトウェアで使用され、ユーザーがパスワードを忘れたときにパスワードを見つけるのに役立ちます。

当初はテキスト内の電子メール アドレスを検索するために開発され、それ以来、電話番号の検索、PDF からのテキストの抽出など、他の多くのアプリケーションで使用されてきました。 リチャード M. ラビンとエイブラハム S. カープによって設計されました。

Python での Rabin-Karp アルゴリズムの複雑さ

Rabin-Karp アルゴリズムは、配列内の個別の値の最小数を効率的に見つける方法です。 二分探索、二次探索、逐次探索など、他の一般的な最小検出アルゴリズムよりも漸近的に高速であることが証明されています。

ただし、Rabin-Karp アルゴリズムは、多くの場合、理論上の最悪の場合の複雑さ (O(n)) よりもはるかに複雑です。ここで、n は検索配列内の個別の値の数です。 Rabin-Karp アルゴリズムは、必要な値が見つかるまで、検索配列内の各値に繰り返しアクセスする必要があるため、この複雑さがあります。

Python での Rabin-Karp アルゴリズムの実装

それでは、Python の例で Rabin-Karp アルゴリズムを実装する方法を理解しましょう。

文字パターンを与え、既存の要素に与えられたパターンの可能性をチェックします。 パターンが見つかった場合は、それを出力として提供します。

まず、入力として追加された文字数の値を割り当てます。 この場合、以下に示すように 15 を割り当てます。

# python
numOfChar = 15

3つの引数を取る searchPattern として関数を定義します。 最初の引数は、Rabin-Karp アルゴリズムを使用して見つけたいパターンです。

2 番目の引数は、パターンを検索するテキストです。 そして最後の引数は素数になります。

後で長さを使用できるように、パターンとテキストの長さを変数に割り当てます。 パターンとテキストのハッシュ値も設定します。

for ループで変数 a と b を定義します。

# python
def searchPattern(pattern, text, primeNum):
    patLen = len(pattern)
    txtLen = len(text)
    a = 0
    b = 0
    p = 0  # hash value for pattern
    t = 0  # hash value for txt
    h = 1

Rabin-Karp アルゴリズムから、以下に示すように、式 pow(numOfChar, patLen-1)% primeNum を使用してまず h の値を見つけます。

# python
for a in xrange(patLen - 1):
    h = (h * numOfChar) % primeNum

次に、以下に示すように、パターンのハッシュ値とテキストの最初のウィンドウを見つけます。

# python
for a in xrange(patLen):
    p = (numOfChar * p + ord(pattern[a])) % primeNum
    t = (numOfChar * t + ord(text[a])) % primeNum

別の for ループを作成して、パターンをテキスト上で 1つずつスライドさせます。 この for ループ内で、テキストとパターンの現在のウィンドウのハッシュ値をチェックします。

ハッシュ値が一致する場合、以下に示すように、文字を 1つずつ確認します。

# python
for a in range(txtLen - patLen + 1):

    if p == t:
        for b in range(patLen):
            if text[a + b] != pattern[b]:
                break

        b += 1
        if b == patLen:
            print("Pattern found at index " + str(a))

    if a < txtLen - patLen:
        t = (numOfChar * (t - ord(text[a]) * h) + ord(text[a + patLen])) % primeNum

        if t < 0:
            t = t + primeNum

次に、以下に示すように、パラメーターに値を割り当て、関数を呼び出してその動作を確認してみましょう。

# python
text = "ABBAABCDEAABBDCAABB"
pattern = "ABB"
primeNum = 101
searchPattern(pattern, text, primeNum)

出力：

ご覧のとおり、パターンは 3つの異なる場所で見つかりました。 Rabin-Karp アルゴリズムを使用すると、特定のテキストの複数の場所でパターンを見つけることができます。