27

我目前正在学习模式匹配算法，并且遇到过这两种算法。我有以下一般想法：

KMP

  • 从左到右比较文本
  • 使用故障阵列智能转移
  • 需要 O(m)，其中 m 是模式的长度，来计算失败数组
  • 需要 O(m)，空间
  • 花费 O(n)，时间来搜索一个字符串

BM

  • 比较最后一个字符的模式
  • 使用坏字符跳转和好的后缀跳转
  • 需要 O(m + 字母大小) 来计算表格
  • 需要 O(m + 字母大小), 空间
  • 需要 O(n)，但通常更好地搜索

我遇到了以下引发此问题的问题（对或错）：

如果我们想在许多不同的文本中重复搜索相同的模式，Knuth-Morris-Pratt (KMP) 算法是一个不错的选择。

所以我相信答案是正确的，因为假设每次你在不同的文本上运行算法时，预处理只是 O(n)，而对于 BM，它是 O(n + 字母大小)。但是，我不确定我是否做出了正确的假设，即每次重新运行算法时都会重新计算一个新表。因为说文本总是落在英文字母表中。我只需要计算一次表并重用该表。因此，归根结底，这个问题的答案是否取决于算法都在同一字母表中包含的文本上运行的事实，还是有其他可能影响它的因素？

4

1 回答 1

23

理论上，两种算法都会有“相似”的性能；在最坏的情况下， KMP 将在搜索阶段进行大约 2n 次比较，而 Boyer-Moore 将在搜索阶段进行大约 3n 次比较。在这两种情况下，您都不需要在获得新文本时重复预处理。

但真正的答案是，你不应该在实践中使用任何一种。

由于所有额外的内存访问，这两种算法所需的线性辅助存储都会导致现代架构的性能相当……粗糙。

然而，Boyer-Moore 和 KMP 背后的想法是大多数快速字符串匹配算法的基础。我所知道的每一个实际有效的字符串匹配算法都使用了类似 KMP 的“故障函数”的想法；事实证明，您可以动态计算模式的次优“故障函数”，该模式仍然为您提供线性时间匹配，同时只需要恒定的额外空间。在将固定模式与随机噪声匹配的“平均情况”中，Boyer-Moore 比线性更快，这在许多实际情况下都得到证实。

于 2013-04-18T16:39:19.220 回答