Rabin-Karp 算法

2024 年 11 月 16 日 | 阅读 16 分钟

在接下来的教程中，我们将讨论 Rabin-Karp 算法。Rabin-Karp 算法是一种字符串搜索算法，以其作者 Michael O. Rabin 和 Richard M. Karp 的名字命名。

那么，让我们开始吧。

理解 Rabin-Karp 算法

Rabin-Karp 算法是一种利用哈希函数来搜索/匹配文本中模式的算法。与朴素字符串匹配算法不同，它在初始阶段不会遍历每个字符。它会过滤掉不匹配的字符，然后进行比较。

哈希函数是一种将较大的输入值映射到较小输出值的实用工具。这个输出值称为哈希值。

Rabin-Karp 算法用于在 O(Ns + Np) 时间内找到给定字符串 'S' 中提供的模式 'P' 的所有出现，其中 'Ns' 和 'Np' 分别是 'S' 和 'P' 的长度。

让我们看一个例子来更好地理解它。

假设字符串 S = "pabctxjabcjfsabcd"，模式 P = "abc"。我们需要找到 'P' 在 'S' 中的所有出现。

我们可以看到 "abc" 在 "pabctxjabcjfsabcd" 中出现了三个位置。因此，我们将返回模式 'P' 出现在字符串 'S' 的索引 1、7 和 13 处。

理解 Rabin-Karp 算法的工作原理

会检查一段字符序列，以确定给定字符串是否存在。如果找到可能性，则执行字符匹配。

让我们来看以下步骤来理解算法

步骤 1：假设给定的文本字符串是

图 1：给定的文本字符串

要在上述文本字符串中搜索的模式是

图 2：模式

步骤 2：我们开始为问题中使用的字符分配一个数值 (v)/权重。这里，我们只选择了前十个字母（即 A 到 J）。

图 3：文本权重

步骤 3：设 x 为模式的长度，y 为文本字符串的长度。这里，我们有 y = 10，x = 3。此外，设 n 为输入集中存在的字符数。因为我们有输入集 {A, B, C, D, E, F, G, H, I, J}。因此，n 将等于 10。我们可以为 n 假设任何首选值。

步骤 4：现在我们开始计算模式的哈希值

图 4：模式的哈希值

Hash Value of Pattern (P) = Σ(v * ny - 1) mod 13
= ((3 * 10²) + (4 * 101) + (4 * 10⁰)) mod 13
= 344 mod 13
= 6

注意：在上述计算中，可以选择一个素数，以便我们可以用单精度算术执行所有计算。这里，我们选择了 13 作为素数。我们稍后将讨论计算模数的目的。

步骤 5：我们现在将计算大小为 y 的文本窗口的哈希值。

For the first window ABC,
Hash Value of text string (s) =  Σ(v * nx - 1) mod 13
= ((1 * 10²) + (2 * 101) + (3 * 10⁰)) mod 13
= 123 mod 13
= 6

步骤 6：现在我们将比较模式的哈希值与文本字符串的哈希值。如果它们匹配，我们将执行字符匹配操作。

在上面的例子中，第一个窗口（即 s）的哈希值与模式（即 P）的哈希值匹配。因此，我们将开始匹配 ABC 和 CDD 之间的字符。由于模式与第一个窗口不匹配，我们将移至下一个窗口。

步骤 7：我们将通过减去第一项并加上下一项来计算下一个窗口的哈希值，如下所示

s = ((1 * 10²) + ((2 * 10¹) + (3 * 10⁰)) * 10 + (3 * 10⁰)) mod 13
= 233 mod 13
= 12

我们将以前面的哈希值进行以下优化处理

s = ((n * (t - v[character to be eliminated] * h) + v[character to be included]) mod 13
= ((10 * (6 - 1 * 9) + 3) mod 13
= 12
Where, h = n^{y - 1} = 10^{3 - 1} = 100

步骤 8：对于 BCC，哈希值 s 将变为 12，不等于模式 P 的哈希值 6。因此，我们将移至下一个窗口。在进行一些搜索后，我们将设法在文本字符串中找到窗口 CDD 的匹配项。

图 5：不同窗口的哈希值

理解算法

既然我们已经理解了 Rabin-Karp 算法的工作原理，现在是时候了解如何在不同的编程语言中实现该算法了。

为了更好地理解，我们将整个过程分为以下步骤

步骤 1：我们将首先定义一个函数（例如，rabinKarpSearchAlgo()）来实现 Rabin-Karp 算法。此函数将接受两个参数 - 字符串 'S' 和模式 'P'。首先，我们将计算 'S' 和 'P' 的长度。

步骤 2：我们现在将选择一个素数和一个用于计算模数的数值来估计哈希值。为了最小化哈希冲突，我们将选择一个接近字符串和模式中使用的字符数的素数值。假设给定的字符串 'S' 和模式 'P' 只包含小写字母，则字符数为 26。因此，我们将选择 31 作为素数。我们现在将选择一个相当大且为素数的模数值。因此，我们将取模值为 1e + 9。

步骤 3：我们将使用以下哈希函数

步骤 4：我们现在将创建一个向量来存储“素数”的幂，并存储 (prime ^ 0) 到 (prime ^ Ns)。我们还将计算给定模式和字符串 'S' 的第一个窗口的哈希值。

步骤 5：最后，我们将一个接一个地滑动给定的模式，并计算相应子字符串或窗口的哈希值，并将其与模式的哈希值进行比较。如果成功找到匹配项，我们将在此索引处打印模式的出现。

现在让我们开始用不同的编程语言实现这种算法方法。

用不同编程语言实现 Rabin-Karp 算法

现在我们将看到 C++、Java 和 Python 等不同编程语言中 Rabin-Karp 算法的实现。

那么，让我们开始吧。

在 C++ 中实现 Rabin-Karp 算法

以下程序代码说明了在 C++ 编程语言中实现 Rabin-Karp 算法。

程序代码

// C++ code for implementation of the Rabin-Karp algorithm

// importing the bits/stdc++.h header file
#include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining the function for searching a pattern in a string using the Rabin-Karp algorithm
void rabinKarpSearchAlgo(string S, string P)
{

    // calculating the length of S and P 
    int x = S.length();
    int y = P.length();
    
    // initializing the value of prime number and mod for calculating hash values
    int primeNum = 31;
    int mod = 1e9 + 9;
    
    // calculating the power raise to the taken prime number
    vector<long long> pPow(x);
    pPow[0] = 1; 
    for (int i = 1; i < x; i++) 
    {
        pPow[i] = (pPow[i - 1] * primeNum) % mod;
    }

    vector<long long> h(x + 1, 0); 
    for (int i = 0; i < x; i++)
    {
        h[i + 1] = (h[i] + (S[i] - 'a' + 1) * pPow[i]) % mod;
    }
    
    // Calculating the hash value of P 
    long long hashP = 0; 
    for (int i = 0; i < y; i++) 
    {
        hashP = (hashP + (P[i] - 'a' + 1) * pPow[i]) % mod; 
    }
  
    /*
        Now slide the pattern by one character and check for the corresponding
        hash value to match with the hash value of the given pattern
    */
    for (int i = 0; i + y - 1 < x; i++) 
    { 
        long long currHash = (h[i + y] + mod - h[i]) % mod; 
        if (currHash == hashP * pPow[i] % mod)
            cout << "The given pattern occurs in the given text string at index : "<<i<<endl;
    }
}
  
// defining the main function
int main()
{
    // given text string
    string S = "pabcasfabcasdfabcaaf";
    // pattern to be searched
    string P = "abc";
    
    // calling the function for the Rabin-Karp algorithm
    rabinKarpSearchAlgo(S, P);
   
    return 0;
}

输出

The given pattern occurs in the given text string at index : 1
The given pattern occurs in the given text string at index : 7
The given pattern occurs in the given text string at index : 14

说明

在上面的代码片段中，我们包含了所需的头文件并使用了标准命名空间。然后，我们将函数定义为 rabinKarpSearchAlgo()，它接受两个参数 - 文本字符串 S 和要搜索的模式 P。然后，我们计算了 S 和 P 的长度。然后，我们定义并初始化了素数和模数的值。然后，我们计算了初始化素数的幂。我们还计算了模式 P 的哈希值，并检查 P 的哈希值是否与字符串的哈希值匹配。然后，我们为用户打印了模式匹配搜索的结果索引。在 main 函数中，我们初始化了文本字符串和要搜索的模式。最后，我们通过将上面两个初始化变量作为参数传递来调用 rabinKarpSearchAlgo() 方法。

结果，在给定的文本字符串 'pabcasfabcasdfabcaaf' 中搜索模式 'abc'，并分别返回索引值 1、7 和 14。

在 Java 中实现 Rabin-Karp 算法

以下程序代码说明了在 Java 编程语言中实现 Rabin-Karp 算法。

程序代码

// Java code for implementation of the Rabin-Karp algorithm

// importing the required libraries
import java.math.BigInteger;
import java.util.Random;

// defining a public class to implement the Rabin-Karp Algorithm
public class RabinKarpAlgo {
    // defining some variables
    private String pattern;         // the pattern string
    private long pattern_hash;      // hash value of pattern string
    private int P;                  // pattern length
    private long primeNum;          // a large prime for computing the hash value
    private int radix;              // radix
    private long RM;                // radix^(P-1) % primeNum
    
    // defining the method for searching a pattern in a string using the Rabin-Karp algorithm
    public RabinKarpAlgo(String pattern) {
        // saving the pattern
        this.pattern = pattern;
        // choosing a large prime number and a radix
        radix = 256;
        P = pattern.length();
        primeNum = longRandomPrime();
        // Pre-computing the radix^(P-1) % primeNum for use in removing leading digit
        RM = 1;
        for (int i = 1; i <= P - 1; i++)
            RM = (radix * RM) % primeNum;
        pattern_hash = hashValue(pattern, P);
    }
    // defining the method for Computing the hash value for pattern and initial text window
    private long hashValue(String key, int P) {
        long h = 0;
        for (int j = 0; j < P; j++)
            h = (radix * h + key.charAt(j)) % primeNum;
        return h;
    }
    // defining the method for Checking for the pattern match
    private boolean check(String text, int i) {
        return hashValue(text.substring(i, i + P), P) == pattern_hash;
    }
    // defining the method for returning a random 31-bit prime number
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }
    // defining the method searching for the pattern string in the text string
    public int search(String text) {
        int n = text.length();
        if (n < P) return n;
        long txtHashValue = hashValue(text, P);
        // checking for match at offset 0
        if (pattern_hash == txtHashValue && check(text, 0))
            return 0;
        // checking for the match of the hash value; if the hash value matches, we check for exact match
        for (int i = P; i < n; i++) {
            // removing the leading digit, adding trailing digit, and checking for the match
            txtHashValue = (txtHashValue + primeNum - RM * text.charAt(i - P) % primeNum) % primeNum;
            txtHashValue = (txtHashValue * radix + text.charAt(i)) % primeNum;
            // match
            int offset = i - P + 1;
            if (pattern_hash == txtHashValue && check(text, offset))
                return offset;
        }
        // No match found
        return n;
    }
    // defining the main function
    public static void main(String[] args) {
        // initializing the variables
        String pattern = "sample";
        String text = "This is the sample text to check the Rabin-Karp Algorithm.";

        // instantiating the RabinKarpAlgo class
        RabinKarpAlgo searcher = new RabinKarpAlgo(pattern);
        int offset = searcher.search(text);
        
        // printing the result
        if (offset != text.length()) {
            System.out.println("The given pattern occurs in the given text string at index : " + offset);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

输出

The given pattern occurs in the given text string at index : 12

说明

在上面的代码片段中，我们导入了一些构建所需的库。然后，我们定义了 RabinKarpAlgo() 类并定义了一些变量。然后，我们将方法定义为 RabinKarpAlgo()，用于使用 Rabin-Karp 算法在字符串中搜索模式，该方法接受文本字符串作为参数。在此方法内部，我们定义了一个变量并将给定的模式存储在其中。我们还初始化了较大的素数和基数。然后，我们定义了另一个名为 hashValue() 的方法来计算模式和初始文本窗口的哈希值。然后，我们定义了一个名为 check() 的方法来检查模式匹配。我们还定义了一个名为 longRandomPrime() 的方法来返回一个随机的 31 位素数。然后，我们定义了一个名为 search() 的方法来将模式字符串返回到文本字符串。对于 main 函数，我们初始化了给定的文本字符串和要在文本字符串中搜索的模式。然后，我们实例化了 RabinKarpAlgo() 类并调用其 search() 方法来查找字符串中匹配的模式并返回其索引值。然后，我们将结果打印给用户。

结果，在给定的文本字符串 "This is a sample text to check the Rabin-Karp Algorithm." 中搜索模式 "sample"，并分别返回索引值 12。

在 Python 中实现 Rabin-Karp 算法

以下程序代码说明了在 Python 编程语言中实现 Rabin-Karp 算法。

程序代码

# Python code for implementation of the Rabin-Karp algorithm

# defining the class to implement the Rabin-Karp Algorithm
class RabinKarpSearchAlgo:
    # defining the constructor
    def __init__(self, textString, pattern):
        '''
        The constructor for the class takes in the main string and the target string,
        and also sets an arbitrary prime number used for the hash value calculation.
        '''
        self.textString = textString
        self.pattern = pattern
        self.primeNumber = 101

    # defining the method to search pattern in the text string
    def searchPattern(self):
        '''
        This is the main method to search the pattern in the given text string.
        '''
        patternLength = len(self.pattern)
        textLength = len(self.textString)
        
        # calculating the hash value for the pattern, and the hash value for the first window of text string
        patternHashValue = self.createHash(self.pattern, patternLength - 1)
        textHashValue = self.createHash(self.textString, patternLength - 1)
        
        for i in range(1, textLength - patternLength + 2):
            # If the hash value of the pattern matches the hash value of the current window of text string
            # then only check individual characters for matching.
            if patternHashValue == textHashValue:
                if self.checkEqual(self.textString[i - 1:i + patternLength - 1], self.pattern[0:]):
                    return i - 1
            
            # calculating the hash value for next window of text string:
            # removing leading digit, add trailing digit from the remaining string
            if i < textLength - patternLength + 1:
                textHashValue = self.recalculateHashValue(self.textString, i - 1, i + patternLength - 1, textHashValue, patternLength)
        
        return -1
    
    # defining the method to calculate the hash value
    def createHash(self, textString, end):
        '''
        This method calculates the initial rolling hash value.
        '''
        hashValue = 0
        
        for i in range(end + 1):
            hashValue = hashValue + ord(textString[i]) * pow(self.primeNumber, i)
        return hashValue

    # defining the method to recalculate the hash value
    def recalculateHashValue(self, textString, oldIndex, newIndex, oldHash, patternLength):
        '''
        This method calculates hash value for next window of text string.
        '''
        newHash = oldHash - ord(textString[oldIndex])
        newHash = newHash // self.primeNumber
        newHash += ord(textString[newIndex]) * pow(self.primeNumber, patternLength - 1)
        return newHash
    
    # defining the method to check the match
    def checkEqual(self, text1, text2):
        '''
        This method checks if individual characters are equal in case of hash value match.
        '''
        if text1 == text2:
            return True
        else:
            return False

# main function
if __name__ == "__main__":
    # initializing the variables
    textString = "This is a sample test string for checking the Rabin-Karp Algorithm."
    pattern = "for"

    # instantiating the RabinKarpSearchAlgo() class with the text string and pattern
    rabinKarp = RabinKarpSearchAlgo(textString, pattern)
    
    # searching for the pattern in the text string
    startIndex = rabinKarp.searchPattern()

    # printing the result
    if startIndex != -1:
        print("The given pattern occurs in the given text string at index : ", startIndex)
    else:
        print("Pattern not found")

输出

The given pattern occurs in the given text string at index :  29

说明

在上面的代码片段中，我们定义了一个名为 RabinKarpSearchAlgo() 的类来实现 Rabin-Karp 算法。在此类内部，我们创建了一个构造函数，该函数接受主字符串和要搜索的模式，并为哈希值的计算设置一个任意的素数。然后，我们定义了一个方法来搜索给定文本字符串中给定的模式。然后，我们定义了一个方法来计算初始滚动哈希值。我们还定义了一个方法来重新计算文本字符串下一个窗口的哈希值。然后，我们定义了一个方法来检查给定字符串中的匹配模式（如果哈希值匹配）。在 main 函数中，我们初始化了给定的文本字符串和要搜索的模式。然后，我们实例化了 RabinKarpSearchAlgo() 类并调用 searchPattern() 方法来查找给定字符串中匹配的模式。最后，我们将结果打印给用户。

结果，在给定的文本字符串 "This is a sample test string for checking the Rabin-Karp Algorithm." 中搜索模式 "for"，并分别返回索引值 29。

Rabin-Karp 算法的性能分析

现在让我们讨论 Rabin-Karp 算法的时间和空间复杂度

时间复杂度

在 Rabin-Karp 算法中，模式的哈希值在 O(Np) 时间内计算，而遍历给定字符串以计算哈希值并将相应的哈希值与模式进行比较在 O(Ns) 时间内完成。

因此，Rabin-Karp 算法的时间复杂度为 O(Ns + Np)，其中 'Ns' 和 'Np' 分别是给定字符串和模式的长度。

空间复杂度

由于我们使用了恒定的空间，因此我们可以得出结论，Rabin-Karp 算法的空间复杂度为 O(1)。

理解 Rabin-Karp 算法的局限性

现在我们已经了解了 Rabin-Karp 算法在不同编程语言中的实现，是时候了解其局限性了。Rabin-Karp 的主要限制是虚假命中。虚假命中增加了算法的最坏情况复杂度。每当哈希值与模式的哈希值匹配，但字符串与模式不同时，就称为虚假命中。

为了减少虚假命中，我们使用模数。模数大大降低了虚假命中的概率。

Rabin-Karp 算法的一些应用

Rabin-Karp 算法是一种字符串搜索算法，用于以有效且高效的方式在给定文本中查找模式的出现。该算法的主要用途是模式匹配和字符串搜索，它具有许多优点，使其在许多领域都具有重要的实用价值。

以下是 Rabin-Karp 算法的一些用例

文字处理：搜索引擎和文本编辑器使用该算法来查找和突出显示大量文本中的关键字和短语的出现。
抄袭检测：该算法还用于识别文档、网站或学术文章中复制内容的实例。
生物序列分析：在生物信息学中，该算法用于在基因组数据库中搜索和匹配 DNA、RNA 或蛋白质序列。
数据挖掘：该算法还用于对大型数据集进行模式匹配和相似性搜索。
计算机安全：该算法实现在入侵检测系统和杀毒软件中，以识别和阻止恶意模式和签名。
压缩算法：该算法用于搜索重复的模式和子字符串，并可以更有效地压缩。
图像处理：该算法已改编用于图像识别任务。它也用于在图像中查找特定模式。
网络数据包检查：该算法用于网络安全，以识别网络数据包中的特定模式或签名。
拼写校正：拼写检查系统也使用该算法，根据文本中的相似模式建议更正。
数据去重：该算法用于数据存储系统中，以消除重复数据并优化存储容量。

常见问题解答

1. 什么是 Rabin with Karp 算法？

Rabin-Karp 算法是一种利用哈希函数来匹配模式的字符串搜索算法。只有当字符串的哈希值与模式的哈希值匹配时，它才会检查该特定字符串是否完全匹配给定的模式。

2. Rabin-Karp 算法的优点是什么？

Rabin-Karp 算法是一个相当好的算法，可以用于检查抄袭，因为它一次可以处理不同的模式。此外，它可以轻松地检测大短语的抄袭。使用良好的哈希函数，该算法对于字符串匹配可能非常高效和有效。

3. 如何使用 Rabin-Karp 算法？

Rabin-Karp 算法使用哈希函数在文本字符串中搜索模式。它沿着文本滑动一个窗口，计算模式和窗口的哈希值，然后进行比较。如果两者的哈希值相等，则检查子字符串是否精确匹配。

4. 什么是数字的 Rabin-Karp 算法？

数字的 Rabin-Karp 算法的运行方式与文本类似；然而，在这种情况下，它使用数字序列。该算法采用滚动哈希函数来识别较大的数字数据集中的特定数字序列。

结论

在上面的教程中，我们详细讨论了 Rabin-Karp 算法。我们了解到 Rabin-Karp 算法是一种字符串匹配算法，用于在给定字符串中查找给定模式。我们还理解了 Rabin-Karp 算法的工作原理以及它在 C++、Java 和 Python 等不同编程语言中的实现。然后，我们了解了它的性能分析和局限性。最后，我们讨论了它的一些应用。

下一个主题有限自动机的字符串匹配

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

DAA 教程

渐进分析

复发

排序分析

分而治之

排序

下界理论

线性时间排序

哈希

二叉搜索树

红黑树

动态规划

贪婪算法

回溯

最小生成树

最短路径

所有对最短路径

最大流

排序网络

复杂度理论

近似算法

字符串匹配

面试题

其他

Rabin-Karp 算法

理解 Rabin-Karp 算法

理解 Rabin-Karp 算法的工作原理

注意：在上述计算中，可以选择一个素数，以便我们可以用单精度算术执行所有计算。这里，我们选择了 13 作为素数。我们稍后将讨论计算模数的目的。

理解算法

用不同编程语言实现 Rabin-Karp 算法

在 C++ 中实现 Rabin-Karp 算法

在 Java 中实现 Rabin-Karp 算法

在 Python 中实现 Rabin-Karp 算法

Rabin-Karp 算法的性能分析

时间复杂度

空间复杂度

理解 Rabin-Karp 算法的局限性

Rabin-Karp 算法的一些应用

常见问题解答

结论

相关帖子

Knuth-Morris-Pratt 算法

Boyer-Moore 算法

朴素字符串匹配算法

有限自动机字符串匹配

字符串匹配介绍

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器