java - Java indexOf函数比Rabin-Karp更有效吗？文字搜寻效率

几周前，我向Stackoverflow提出了一个问题，该问题涉及创建一种有效的算法来搜索大量文本中的模式。现在，我正在使用String函数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函数快，而且慢了一个数量级。我不知道怎么了(如果有的话)。有人对此有想法吗？

谢谢，

艾略特

最佳答案

我早些时候回答了这个问题，艾略特指出我是完全错误的。我向社区道歉。

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

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

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

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

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

递增循环计数器

执行两个逻辑测试

做一个数组访问

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

递增循环计数器

执行两个逻辑测试

执行两个数组访问(实际上是两个方法调用)

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

因此，在每次迭代中，Rabin-Karp都将越来越落后。我曾尝试将哈希算法简化为仅XOR字符，但我仍然拥有额外的数组访问权限和两个额外的数字运算，因此速度仍然较慢。

此外，找到匹配项后，Rabin-Karp仅知道哈希匹配项，因此必须测试每个字符，而indexOf已经知道第一个字符匹配项，因此需要做的测试少。

在Wikipedia上读到Rabin-Karp用于检测窃之后，我读了《圣经的路得记》，删除了所有标点符号，并将所有小写字母都留到了10000个字符以下。然后，我搜索了“andthewomenherneighboursgaveitaname”，该名称出现在文本的结尾处。即使使用XOR哈希，String.indexOf仍然更快。但是，如果我删除了String.indexOfs能够访问String的私有(private)内部字符数组并强制其复制字符数组的优点，那么最终，Rabin-Karp确实更快。

但是，我故意选择该文本，因为《路得记》中有213个“and”和28个“andthe”。相反，如果我只搜索最后一个字符“ursgaveitaname”，那么文本中只有3个“urs”，因此indexOf返回最佳状态并再次赢得比赛。

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

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

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

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