php - 在 PHP 中加速 levenshtein /similar_text

Question

我目前正在使用similar_text将字符串与〜50,000 的列表进行比较，尽管由于比较的次数非常慢，但该列表有效。比较大约 500 个唯一字符串大约需要 11 分钟。

在运行它之前，我会检查数据库以查看它是否在过去被处理过，所以每次在初始运行之后它都接近即时。

我确信使用levenshtein会稍微快一些，并且手册中发布的 LevenshteinDistance 函数看起来很有趣。我是否遗漏了一些可以显着加快速度的东西？

Answer 1

最后，两者levenshtein都similar_text太慢了，因为它必须通过的字符串数量，即使有很多检查并且只使用它们中的一个作为最后的手段。

作为一个实验，我将一些代码移植到 C# 中，看看它比交互代码快多少。它使用相同的数据集在大约 3 分钟内运行。

接下来，我在表中添加了一个额外的字段，并使用双变音位 PECL 扩展为每一行生成密钥。结果很好，尽管由于某些包含的数字导致重复。我想我可以通过上述函数运行每个函数，但决定不这样做。

最后我选择了最简单的方法，MySQLs full text 效果很好。尽管很容易发现和纠正，但偶尔也会出现错误。它的运行速度也非常快，大约 3-4 秒。

Answer 2

也许您可以通过首先比较您的字符串是否完全匹配（并首先比较长度是否相同）以及是否跳过更昂贵的similar_text调用来“短路”一些检查。

正如@jason 所说，O(N^3) 算法永远不会是一个好的选择。

Answer 3

使用 levenshtein 自动机（匹配带有 distance 的字符串的自动机k）时，您可以检查匹配 in O(n)，其中n是您要检查的字符串的长度。构造自动机需要O(kn)，其中k是基本字符串的最大距离和n长度。