3

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

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

谁能让我知道我自己在 php 中实现 Agrep/Sun Wu-Manber 是解决这个问题的好方法吗？还有别的反馈吗？

编辑：正如我在下面的评论中提到的，有数百个或更多不同的搜索关键字，所以正则表达式无济于事。所以这种反应是没有帮助的。

4

2 回答 2

1

我认为您可以通过使用“Levenshtein distance”度量来解决这个问题。

来自维基百科；

在信息论和计算机科学中，Levenshtein 距离是一种字符串度量，用于测量两个序列之间的差异量。

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

于 2012-06-15T15:38:48.547 回答
0

自 PHP 5.5 起，PHPstrtr使用 Wu-Manbers 算法进行多模式匹配。有关实现的详细信息，请参阅PHP git 存储库中的提交 ccf15cf2 。根据我的经验，它非常有效。

Aho-Corasick 算法的纯 PHP 实现可在此处获得：https ://packagist.org/packages/wikimedia/aho-corasick

于 2015-06-15T05:48:27.370 回答