跳到主要内容

Rabin-Karp算法

提示
  1. 基本概念：Rabin-Karp算法是一种利用哈希函数进行文本中字符串搜索/匹配的算法，与朴素算法不同，它通过哈希值过滤掉不匹配的字符后进行比较。
  2. 算法工作原理：通过计算模式串和文本的哈希值来确定潜在匹配，如果哈希值匹配，则进行进一步的字符比较。
  3. 哈希函数的应用：哈希函数将大量的输入映射到较小的输出（哈希值），在Rabin-Karp算法中用于快速筛选不匹配的情况，提高匹配效率。

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

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

Rabin-Karp 算法的工作原理​

首先，取一个字符序列并检查其中是否可能存在所需字符串的可能性。如果可能性存在，那么进行字符匹配。

让我们通过以下步骤来理解该算法：

  1. 假设文本如下： rabin karp 算法的文本

    要在上述文本中搜索的字符串如下： rabin karp 算法的模式

  2. 让我们为问题中要使用的字符分配数值值(v)/权值。在这里，我们只使用前十个字母（即 A 到 J）。 文本权值

  3. 让 n 表示模式的长度，m 表示文本的长度。在这里，m = 10，n = 3。 假设 d 表示输入集中的字符数。在这里，我们使用输入集 {A, B, C, ..., J}。所以 d = 10。你可以为 d 指定任何合适的值。

  4. 计算模式的哈希值。 文本的哈希值

模式(p) 的哈希值 = Σ(v * dm-1) mod 13
                  = ((3 * 102) + (4 * 101) + (4 * 100)) mod 13
                  = 344 mod 13
                  = 6

在上面的计算中，选择一个质数（这里是 13），以便我们可以使用单精度算术来执行所有计算。

计算模块的原因在 以下 给出。

  1. 计算大小为 m 的文本窗口的哈希值。
对于第一个窗口 ABC，
文本(t) 的哈希值 = Σ(v * dn-1) mod 13
                = ((1 * 102) + (2 * 101) + (3 * 100)) mod 13
                = 123 mod 13
                = 6
  1. 比较模式的哈希值与文本的哈希值。如果它们匹配，然后进行字符匹配。 在上面的示例中，第一个窗口（即 t）的哈希值与 p 匹配，因此进行字符匹配，比较 ABC 和 CDD。由于它们不匹配，因此继续下一个窗口。
  2. 我们通过以下方式计算下一个窗口的哈希值，通过减去第一个项并添加下一个项来实现。
t = ((1 * 102) + ((2 * 101) + (3 * 100)) * 10 + (3 * 100)) mod 13
  = 233 mod 13
  = 12

为了优化这个过程，我们利用前一个哈希值进行如下处理。

t = ((d * (t - v[要删除的字符] * h) + v[要添加的字符] ) mod 13
  = ((10 * (6 - 1 * 9) + 3 )mod 13
  = 12
其中，h = dm-1 = 103-1 = 100。

  1. 对于 BCC，t = 12 (≠6)。因此，继续下一个窗口。 在进行几次搜索后，我们将在文本中找到窗口 CDA 的匹配。

    不同窗口的哈希值

算法​

n = t.length
m = p.length
h = dm-1 mod q
p = 0
t0 = 0
for i = 1 to m
    p = (dp + p[i]) mod q
    t0 = (dt0 + t[i]) mod q
for s = 0 to n - m
    if p = ts
        if p[1.....m] = t[s + 1..... s + m]
            print "pattern found at position" s
    If s < n-m
        ts + 1 = (d (ts - t[s + 1]h) + t[s + m + 1]) mod q

Python、Java 和 C/C++ 示例​

Python Java C C++

# Python 中的 Rabin-Karp 算法

d = 10

def search(pattern, text, q):
    m = len(pattern)
    n = len(text)
    p = 0
    t = 0
    h = 1
    i = 0
    j = 0

    for i in range(m-1):
        h = (h*d) % q

    # 计算模式和文本的哈希值
    for i in range(m):
        p = (d*p + ord(pattern[i])) % q
        t = (d*t + ord(text[i])) % q

    # 查找匹配
    for i in range(n-m+1):
        if p == t:
            for j in range(m):
                if text[i+j] != pattern[j]:
                    break

            j += 1
            if j == m:
                print("在位置找到模式: " + str(i+1))

        if i < n-m:
            t = (d*(t-ord(text[i])*h) + ord(text[i+m])) % q

            if t < 0:
                t = t+q


text = "ABCCDDAEFG"
pattern = "CDD"
q = 13
search(pattern, text, q)
// Java 中的 Rabin-Karp 算法

public class RabinKarp {
  public final static int d = 10;

  static void search(String pattern, String txt, int q) {
    int m = pattern.length();
    int n = txt.length();
    int i, j;
    int p = 0;
    int t = 0;
    int h = 1;

    for (i = 0; i < m - 1; i++)
      h = (h * d) % q;

    // 计算模式和文本的哈希值
    for (i = 0; i < m; i++) {
      p = (d * p + pattern.charAt(i)) % q;
      t = (d * t + txt.charAt(i)) % q;
    }

    // 查找匹配
    for (i = 0; i <= n - m; i++) {
      if (p == t) {
        for (j = 0; j < m; j++) {
          if (txt.charAt(i + j) != pattern.charAt(j))
            break;
        }

        if (j == m)
          System.out.println("在位置找到模式: " + (i + 1));
      }

      if (i < n - m) {
        t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q;
        if (t < 0)
          t = (t + q);
      }
    }
  }

  public static void main(String[] args) {
    String txt = "ABCCDDAEFG";
    String pattern = "CDD";
    int q = 13;
    search(pattern, txt, q);
  }
}

Rabin-Karp算法（C）​

Rabin-Karp算法是一种用于字符串匹配的有效算法，它通过计算字符串的哈希值来快速检测两个字符串是否相等。

Rabin-Karp算法代码示例（C）​

#include <stdio.h>
#include <string.h>

#define d 10

void rabinKarp(char pattern[], char text[], int q) {
  int m = strlen(pattern);
  int n = strlen(text);
  int i, j;
  int p = 0;  // 模式串的哈希值
  int t = 0;  // 文本串的哈希值
  int h = 1;

  // 计算h的值
  for (i = 0; i < m - 1; i++)
    h = (h * d) % q;

  // 计算模式串和文本串的哈希值
  for (i = 0; i < m; i++) {
    p = (d * p + pattern[i]) % q;
    t = (d * t + text[i]) % q;
  }

  // 匹配过程
  for (i = 0; i <= n - m; i++) {
    if (p == t) {
      for (j = 0; j < m; j++) {
        if (text[i + j] != pattern[j])
          break;
      }

      if (j == m)
        printf("模式串在位置:  %d 处找到\n", i + 1);
    }

    if (i < n - m) {
      t = (d * (t - text[i] * h) + text[i + m]) % q;
      if (t < 0)
        t = (t + q);
    }
  }
}

int main() {
  char text[] = "ABCCDDAEFG";
  char pattern[] = "CDD";
  int q = 13;
  rabinKarp(pattern, text, q);
}

Rabin-Karp算法（C++）​

Rabin-Karp算法代码示例（C++）​

#include <string.h>
#include <iostream>
using namespace std;

#define d 10

void rabinKarp(char pattern[], char text[], int q) {
  int m = strlen(pattern);
  int n = strlen(text);
  int i, j;
  int p = 0;
  int t = 0;
  int h = 1;

  for (i = 0; i < m - 1; i++)
    h = (h * d) % q;

  // 计算模式串和文本串的哈希值
  for (i = 0; i < m; i++) {
    p = (d * p + pattern[i]) % q;
    t = (d * t + text[i]) % q;
  }

  // 匹配过程
  for (i = 0; i <= n - m; i++) {
    if (p == t) {
      for (j = 0; j < m; j++) {
        if (text[i + j] != pattern[j])
          break;
      }

      if (j == m)
        cout << "模式串在位置: " << i + 1 << " 处找到" << endl;
    }

    if (i < n - m) {
      t = (d * (t - text[i] * h) + text[i + m]) % q;
      if (t < 0)
        t = (t + q);
    }
  }
}

int main() {
  char text[] = "ABCCDDAEFG";
  char pattern[] = "CDD";
  int q = 13;
  rabinKarp(pattern, text, q);
}

在这两个示例中，我们都是通过计算文本串和模式串的哈希值来寻找模式串在文本串中的位置。若哈希值相等，则检查实际的字符串是否匹配。这种方法减少了逐字符比较的需要，提高了搜索效率。

Rabin-Karp 算法的局限性​

伪命中​

当模式的哈希值与文本窗口的哈希值匹配，但窗口实际上不是模式时，这称为伪命中。

伪命中会增加算法的时间复杂度。为了最小化伪命中，我们使用取模运算。它大大减少了伪命中的发生。

Rabin-Karp 算法的复杂性​

Rabin-Karp 算法的平均情况和最佳情况复杂度为 O(m + n)，最坏情况复杂度为 O(mn)。

最坏情况复杂度发生在伪命中在所有窗口中都发生的情况下。

Rabin-Karp 算法的应用​

  • 用于模式匹配
  • 用于在较大的文本中搜索字符串
最后于 更新