php - PHP中的多个关键字(100s到1000s)搜索(字符串搜索算法)

Question

我在我的 PHP 项目中有这个问题需要解决，其中一些关键字(从几百到几千，长度可能会有所不同)需要在大约 100-300 个字符长的字符串中搜索，有时长度更短 30- 50 个字符。我可以预处理关键字以重新用于搜索字符串的新实例。我是 PHP 的新手，在 PHP 库中找不到执行此操作的方法。做了一些搜索，我在 Aho Corasick 算法中找到了一些不错的候选者，然后是 Sun Wu 和 Udi Manber 的改进，它似乎也被称为 agrep(或者是 agrep 的一部分):http://webglimpse.net/pubs/TR94-17.pdf

还有 Rabin Karp、Suffix Trees 等，但它们看起来不太适合，因为第一个是固定长度的关键字，而后者看起来很通用，需要大量工作。

谁能告诉我自己在 php 中实现 Agrep/Sun Wu-Manber 是否是解决此问题的好方法？还有其他反馈吗？

编辑:正如我在下面的评论中提到的，有数百个或更多不同的搜索关键字，因此正则表达式无济于事。因此，该响应没有帮助。

Answer 1

我认为您可以使用“编辑距离”度量来解决这个问题。

From wikipedia ;

In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences.

另外，PHP 有一个 levenshtein () 方法。使用您的关键字列表作为数组和可搜索字符串作为输入并迭代您的数组，并在每次迭代中使用 levenshtein() 进行匹配。