string - 为什么在文本编辑器的查找功能中选择 "BM algorithm"而不是 "Sunday algorithm"？

Question

在随机字符下，Sunday算法比bm算法更快。

那么，为什么在文本编辑器的查找功能中选择“BM算法”而不是“Sunday算法”呢？

Answer 1

对于为什么选择其中一个而不是另一个没有简单的答案。 “BM”指的是“Boyer-Moore”。 “Sunday”算法是指 Boyer-Moore-Horspool 的 Sunday 变体。

正如您可能从名称中猜到的那样，周日的 Boyer-Moore-Horspool 变体与 Boyer-Moore 非常相似。

说实话，人们选择周日变体的主要原因与执行速度无关。相反，它的实现要简单得多。原始的 Boyer-Moore 算法要完全正确是极其困难的。周日的变体也不完全是微不足道的，但它仍然简单得多。

支持 Boyer-Moore 的论点是，尽管代码更复杂，但它将搜索所需的比较次数减少到接近绝对必要的最小值。最大的问题是它需要更多的预处理(和更多的内存)才能做到这一点。

您可以找到在执行速度方面对其中一种有利的情况(但是，从我所见)在文本编辑器中使用搜索可能倾向于支持周日的 Boyer-Moore-Horspool 变体。