迹忆客 专注技术分享

我们将介绍 Python 中的 Rabin-Karp 算法，并讨论如何在 Python 程序中使用它。

Python 中的 Rabin-Karp 算法

Rabin-Karp 算法从给定的输入或值中查找特定的数字、字母或模式。 当您需要从数据中提取见解时，机器学习算法通常是数据科学中的首选解决方案，但并非所有算法都是一样的。

有些人比其他人更善于找到正确的见解，有些人比其他人更擅长避免误报。 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

我们将定义一个函数 searchPattern ，它将接受三个参数。 第一个参数是我们想要使用 Rabin-Karp 算法找到的模式。

第二个参数是我们要在其中寻找模式的文本。 最后一个参数是素数。

我们将模式和文本的长度分配给变量，以便稍后使用该长度。 我们还将设置模式和文本的哈希值。

我们将在 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 循环，将图案逐个滑动到文本上。 在这个 for 循环中，我们将检查当前文本和模式窗口的哈希值。

如果哈希值匹配，我们将一一检查字符，如下所示。

# 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)

输出:

正如您所看到的，我们的模式是在三个不同的位置发现的。 使用 Rabin-Karp 算法，我们可以在给定文本的多个位置找到模式。