你何时会在BOYER-MOORE上使用KMP

Question

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

KMP

• 从左到右比较文本
• 使用故障数组智能地转换
• 取O(m),其中m是模式的长度,以计算故障数组
• 需要O(m),空间
• 需要O(n),时间来搜索字符串

BM

• 比较最后一个字符的模式
• 使用糟糕的角色跳跃和良好的后缀跳跃
• 采用O(m +字母表大小)来计算表格
• 取O(m +字母大小),空格
• 需要O(n),但通常更好搜索

我遇到了以下引发这个问题的问题(正确还是错误):

如果我们想要在许多不同的文本中重复搜索相同的模式,那么Knuth-Morris-Pratt(KMP)算法是一个很好的选择.

所以我认为答案是正确的,因为假设每次在不同文本上运行算法时,预处理只是O(n),对于BM,它是O(n +字母表大小).但是,我不确定我是否正在做出正确的假设,即每次重新运行算法时都会重新计算新表.因为说文字总是落在英文字母表中.我只需要计算一次表,只需重用表.那么在一天结束的时候,这个问题的答案是否依赖于这样的事实:算法都是在包含在同一字母表中的文本上运行,还是有一些其他可能影响它的因素？

Answer 1

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

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

由于所有额外的存储器访问,两种算法所需的线性辅助存储器在现代架构上导致相当大的性能.

然而,Boyer-Moore和KMP背后的思想支持了大多数快速字符串匹配算法.像我所知的每个实用有效的字符串匹配算法都使用像KMP的"失败函数"这样的想法; 事实证明,你可以为即时模式计算一个次优的"失效函数",它仍然为你提供线性时间匹配,同时只需要不断的额外空间.在将固定模式与随机噪声匹配的"平均情况"中,Boyer-Moore比线性更快,这在许多实际情况中都有所体现.