algorithm - 您什么时候会使用 KMP 而不是 BOYER-MOORE

Question

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

国民党

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

母语

• 比较最后一个字符的模式
• 使用不好的字符跳转和好的后缀跳转
• 用 O(m + 字母表的大小) 来计算表格
• 占用 O(m + 字母表的大小)，空间
• 花费 O(n)，但通常更便于搜索

我遇到了触发此问题的以下问题(对或错):

The Knuth-Morris-Pratt (KMP) algorithm is a good choice if we want to search for the same pattern repeatedly in many different texts.

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

Answer 1

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

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

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

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