2

目前正在为一个 uni 模块开发一个字符串搜索程序，并且我已经成功地实现了这些算法，至少到了他们一致地找到字符串的程度。我实现了 Boyer Moore 和 Rabin Karp。当我的一个同学遇到这个确切的问题时，我也投入了蛮力，并意识到我遇到了同样的问题 - 蛮力比单词列表上的 Rabin-Karp 更快。

Rabin-Karp 似乎花费了最多的时间来执行滚动哈希，一开始我很好奇我是否只是有很多碰撞，但我设法用一个巨大的素数将碰撞降低到 3。由于质数的大小，我假设这增加了一点时间，但滚动哈希似乎很明显导致了问题。

这是滚动哈希部分：

//hashes don't match, rehash using rolling hash to move on to next string section
  if (counter < (stringLength - patternLength)) { 

            stringHash = (MAXCHAR *(stringHash - stringFile[counter] * hash) + stringFile[counter + patternLength]) % prime;


            if (stringHash < 0) {

                stringHash += prime;    //when hash value is negative, make it positive
            }

        }

        if (!found) {

            counter++; 
        }

我想尝试搜索一个巨大的文本文件，所以我使用了 Rockyou 词汇表，Boyer Moore 对此非常满意，而 Rabin-Karp 只需不到一秒钟的时间。蛮力花费的时间不到 Rabin-Karp 的一半，尽管这对我来说没有意义？

我是否误解了应该如何应用这些算法，或者我正在使用的滚动哈希过程是否存在问题？

4

1 回答 1

1

蛮力字符串搜索是 Rabin-Karp 的特例，具有恒定哈希函数（因此每个滚动哈希都匹配）。

两种算法的最坏情况复杂度相同，大多数“平均情况”定义的平均情况复杂度也是如此。

在这些情况下，由于计算和检查良好哈希的开销，Rabin-Karp 将花费更长的时间。

与 Rabin-Karp 相比，蛮力的问题在于，在现实生活中有时会出现糟糕的情况。例如，如果您正在搜索路径名，那么您的模式可能具有与文件中许多或大部分路径名和部分路径名相同的长前缀，这将使蛮力花费很长时间时间。

使用 Rabin-Karp，糟糕的情况在现实生活中不太可能发生。它们实际上只发生在“对抗”条件下，在这种情况下，文件和模式是有目的地构建的，需要很长时间，并且对您使用的散列函数有特定的了解。

即便如此...... Rabin-Karp 并不是一个很好的单模式搜索算法。当您同时搜索许多字符串并且可以在潜在匹配的字典中查找滚动哈希时，它变得更加有用。

于 2019-12-01T15:03:04.730 回答