Java indexOf 函数比 Rabin-Karp 更高效？文本搜索效率

Question

几周前，我向 Stackoverflow 提出了一个问题，关于创建一种有效的算法来搜索大量文本中的模式。现在我正在使用字符串函数 indexOf 进行搜索。一个建议是使用 Rabin-Karp 作为替代方案。我写了一个小测试程序如下来测试Rabin-Karp的实现。

public static void main(String[] args) {
    String test = "Mary had a little lamb whose fleece was white as snow";

    String p = "was";
     long start  = Calendar.getInstance().getTimeInMillis();
     for (int x = 0; x < 200000; x++)
         test.indexOf(p);
     long end = Calendar.getInstance().getTimeInMillis();
     end = end -start;
     System.out.println("Standard Java Time->"+end);

    RabinKarp searcher = new RabinKarp("was");
    start  = Calendar.getInstance().getTimeInMillis();
    for (int x = 0; x < 200000; x++)
    searcher.search(test);
    end = Calendar.getInstance().getTimeInMillis();
    end = end -start;
    System.out.println("Rabin Karp time->"+end);

}

这是我正在使用的 Rabin-Karp 的实现:

import java.math.BigInteger;
import java.util.Random;

public class RabinKarp {
private String pat; // the pattern // needed only for Las Vegas
private long patHash; // pattern hash value
private int M; // pattern length
private long Q; // a large prime, small enough to avoid long overflow
private int R; // radix
private long RM; // R^(M-1) % Q
static private long dochash = -1L;

public RabinKarp(int R, char[] pattern) {
    throw new RuntimeException("Operation not supported yet");
}

public RabinKarp(String pat) {
    this.pat = pat; // save pattern (needed only for Las Vegas)
    R = 256;
    M = pat.length();
    Q = longRandomPrime();

    // precompute R^(M-1) % Q for use in removing leading digit
    RM = 1;
    for (int i = 1; i <= M - 1; i++)
        RM = (R * RM) % Q;
    patHash = hash(pat, M);
}

// Compute hash for key[0..M-1].
private long hash(String key, int M) {
    long h = 0;
    for (int j = 0; j < M; j++)
        h = (R * h + key.charAt(j)) % Q;
    return h;
}

// Las Vegas version: does pat[] match txt[i..i-M+1] ?
private boolean check(String txt, int i) {
    for (int j = 0; j < M; j++)
        if (pat.charAt(j) != txt.charAt(i + j))
            return false;
    return true;
}

// check for exact match
public int search(String txt) {
    int N = txt.length();
    if (N < M)
        return -1;
    long txtHash;
    if (dochash == -1L) {
        txtHash = hash(txt, M);
        dochash = txtHash;
    } else
        txtHash = dochash;

    // check for match at offset 0
    if ((patHash == txtHash) && check(txt, 0))
        return 0;

    // check for hash match; if hash match, check for exact match
    for (int i = M; i < N; i++) {
        // Remove leading digit, add trailing digit, check for match.
        txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
        txtHash = (txtHash * R + txt.charAt(i)) % Q;

        // match
        int offset = i - M + 1;
        if ((patHash == txtHash) && check(txt, offset))
            return offset;
    }

    // no match
    return -1; // was N
}

// a random 31-bit prime
private static long longRandomPrime() {
    BigInteger prime = new BigInteger(31, new Random());
    return prime.longValue();
}

// test client

}

Rabin-Karp 的实现是因为它返回我正在寻找的字符串的正确偏移量。令我惊讶的是运行测试程序时出现的计时统计信息。他们来了:

Standard Java Time->39
Rabin Karp time->409

这真的很令人惊讶。 Rabin-Karp(至少在这里实现的)不仅不比标准的 java indexOf String 函数快，而且慢了一个数量级。我不知道出了什么问题(如果有的话)。有人对此有什么想法吗？

谢谢，

埃利奥特

Answer 1

我之前回答了这个问题，Elliot 指出我完全错了。我向社会道歉。

String.indexOf 代码没有什么神奇之处。它不是 native 优化的或类似的东西。您可以从 String 源代码复制 indexOf 方法，它的运行速度也一样快。

我们这里有的是 O() 效率和实际效率之间的差异。 Rabin-Karp 对于长度为 N 的字符串和长度为 M 的模式，Rabin-Karp 是 O(N+M) 和 O(NM) 的最坏情况。当您查看它时，String.indexOf() 也有 O(N+M) 的最佳情况和 O(NM) 的最坏情况。

如果文本包含许多与模式开头的部分匹配，Rabin-Karp 将保持接近其最佳情况的性能，而 String.indexOf 则不会。例如，我在一百万个“0”后跟一个“1”上测试了上面的代码(这次是正确的:-))，并搜索了 1000 个“0”后跟一个“1”。这迫使 String.indexOf 达到其最坏情况下的性能。对于这个高度退化的测试，Rabin-Karp 算法比 indexOf 快大约 15 倍。

对于自然语言文本，Rabin-Karp 将保持接近最佳情况，而 indexOf 只会略微恶化。因此，决定因素是在每个步骤上执行的操作的复杂性。

在它的最内层循环中， indexOf 扫描匹配的第一个字符。在每次迭代中必须:

增加循环计数器

执行两个逻辑测试

做一个数组访问

在 Rabin-Karp 中，每次迭代必须:

增加循环计数器

执行两个逻辑测试

做两次数组访问(实际上是两次方法调用)

更新一个哈希值，上面需要 9 次数值运算

因此，在每次迭代中，Rabin-Karp 都会越来越落后。我尝试将散列算法简化为仅 XOR 字符，但我仍然有额外的数组访问和两个额外的数值运算，因此它仍然较慢。

此外，当找到匹配时，Rabin-Karp 只知道哈希匹配，因此必须测试每个字符，而 indexOf 已经知道第一个字符匹配，因此少了一个测试要做。

在维基百科上读到 Rabin-Karp 被用来检测抄袭后，我拿了圣经的露丝书，去掉了所有标点符号，把所有的标点符号都变成了小写，只剩下不到 10000 个字符。然后我搜索了出现在文本末尾附近的“andthewomenher neighborsgaveitaname”。 String.indexOf 仍然更快，即使只有 XOR 哈希。但是，如果我去掉 String.indexOfs 能够访问 String 的私有(private)内部字符数组的优势并强制它复制字符数组，那么最后，Rabin-Karp 真的更快了。

然而，我特意选择了那个文本，因为在露丝书中有 213 个“and”和 28 个“andthe”。相反，如果我只搜索最后一个字符“ursgaveitaname”，那么文本中只有 3 个“urs”，因此 indexOf 返回更接近其最佳情况并再次赢得比赛。

作为更公平的测试，我从文本的第二部分中随机选择了 20 个字符串并对其进行了计时。 Rabin-Karp 比在 String 类之外运行的 indexOf 算法慢约 20%，比实际的 indexOf 算法慢 70%。因此，即使在它应该适合的用例中，它仍然不是最佳选择。

那么拉宾-卡普有什么好处呢？无论要搜索的文本的长度或性质如何，在比较每个字符时都会变慢。无论我们选择什么散列函数，我们肯定都需要进行额外的数组访问和至少两个数值运算。更复杂的哈希函数会给我们提供更少的错误匹配，但需要更多的数字运算符。 Rabin-Karp 根本无法跟上。

如上所示，如果我们需要找到以经常重复的文本块为前缀的匹配项，indexOf 可能会更慢，但如果我们知道我们正在这样做，看起来我们仍然最好使用 indexOf 搜索文本没有前缀，然后检查前缀是否存在。

根据我今天的调查，我看不到 Rabin Karp 的额外复杂性何时会得到返回。