你是否使用过KMP或BM算法？

Question

我知道KMP（Knuth-Morris-Pratt）和BM（Boyer-Moore）算法都是很好的字符串搜索操作算法。 我也知道BM比KMP快3-5倍。

在您编写工业软件的经验中，您是否曾使用过BM或KMP算法？ 这里算法真的很重要吗？

- user699656

---

我知道KMP代表什么，但不知道BM代表什么。你能否写下它们各自的含义，以防其他人不知道？ - user541686

@Mehrdad：BM 可能指的是 Boyer-Moore。 - Mike Bailey

如果你在谷歌上搜索“BM算法”，你就可以找到它。BM代表Boyer-Moore算法。 - user699656

我不确定你为什么关心，但是我在实际软件中使用了Sunday的Boyer-Moore-Horspool变种算法。 - Jerry Coffin

Answer 1

如果您查看例如Java的String.indexOf函数，似乎他们使用暴力方法进行字符串匹配。您可能会想知道为什么。

原因是这些算法中执行了一些查询预处理，这可能很昂贵（特别是如果您同时使用BM算法中的两个数组）。因此，在KMP和BM算法能够击败暴力匹配之前，您要搜索的字符串必须具有较大的大小。

使用不同算法时总是有权衡，处理大型字符串时，您可能还可以考虑对文本进行索引，而不是对查询进行索引（例如后缀树）。即使您每次处理新文本，这也可能非常有用。

在我看来，这些算法相当学术，只有在特殊情况下才有用。

- jallmer

---

有趣的是，gcc的strstr()实现（相当于String.indexOf()）使用了一种非常酷的算法，只需要线性时间，并且与BM和KMP不同，它具有恒定空间。这基本上消除了在库函数中使用天真的O(n^2)方法的任何理由，因为它更快的情况只有在极短的字符串上，而这两种算法已经非常（即足够）快了。（从MAK的答案中得到的。） - j_random_hacker

实际上，String 的 真正 indexOf 方法通常不是您在 JDK 源中看到的那个，而是由 JDK 插入的内部版本，至少在 Java 6 和 7 中的 Sun 热点中是如此。事实上，该版本确实使用了 BM 的简化变体。它仅在检查的字符根本不存在于字符串中的情况下起作用，在这种情况下，它通常（请参见注释）跳过 N 个字符，其中 N 是搜索字符串的长度。注意：通常 是因为该算法使用一个 32 个条目的哈希表来确定字符是否出现在字符串中，因此可能会发生冲突。 - BeeOnRope

有趣的是，在 iptables 中，你只能选择 BM 和 KMP... - Alexis Wilke

Answer 2

glibc的strstr函数是线性的。它使用双向算法，我认为这是Boyer-Moore算法的一种变体。因此，我想这意味着任何在gcc中使用strstr的人实际上都在使用现实世界中的快速字符串搜索算法。

至于快速算法是否重要，我个人认为只有当数据大小足够大时才重要。我们所做的许多显式字符串操作都是在非常小的字符串上进行的（例如少于500个字符）。这并不是说我们不会进行繁重的字符串操作（例如对数据库进行全文搜索），但在这种情况下，我们通常让数据库或库为我们进行繁重的工作。数据库或库使用快速字符串搜索算法-因此我不会说它们不重要，只是它们的使用对我们不是直接可见的。

- MAK

---

哇！线性时间和常数空间，它符合所有要求！不知道为什么我以前没听说过这个算法。不得不说，我无法理解http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260上的解释，所以我下载了Crochemore＆Perrin的1991年论文，但发现它有25页——超出了我的“随意阅读”门槛。 :/ 也许有一天... - j_random_hacker

@j_random_hacker：对我来说太难理解了。我猜这正是它不像KMP或Rabin Karp那样流行的原因。 - MAK

Answer 3

我曾在硬件上实现过KMP算法。如果硬件是FPGA，你可以利用可重构性来拥有一个自修改电路。这个电路获取搜索字符串，然后在硬件中进行必要的预处理，并重新配置为实际执行KMP的逻辑。但同样需要遍历大量数据才能加速处理，但也有一些情况下可以做到（例如DNA匹配）。

- flolo