在PHP中加速levenshtein / similar_text

Question

我目前正在使用 similar_text 来比较字符串尽管由于比较次数很多，但是〜50,000的列表仍有效。比较~500个独特的字符串大约需要11分钟。

在运行之前，我会检查数据库以查看它是否已经过去处理，因此每次运行后它都会接近即时。

我确信使用 levenshtein 会稍快一些LevenshteinDistance函数有人发布在手册中看起来很有趣。我错过了一些可以使这个显着加快的东西吗？

Answer 1

最后， levenshtein 和 similar_text 对于必须通过的字符串数量来说都太慢了，即使有很多检查并只使用它们一个他们作为最后的手段。

作为一项实验，我将一些代码移植到C＃中，看看它与嵌入式代码的速度有多快。它使用相同的数据集在大约3分钟内运行。

接下来，我在表中添加了一个额外字段，并使用双元电话PECL扩展为每一行生成键。结果很好，虽然由于一些包含的数字，这导致重复。我想我可以通过上述功能运行每一个，但决定不这样做。

最后我选择了最简单的方法，MySQL的全文非常好用。偶尔会出现错误，尽管它们易于检测和纠正。它运行速度非常快，大约3-4秒。

Answer 2

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

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

Answer 3

当使用levenshtein自动机（匹配距离为 k 的字符串的自动机）时，你可以检查 O（n）中的匹配，其中 n 是您要检查的字符串的长度。构造自动机将采用 O（kn），其中 k 是基本字符串的最大距离和 n 长度。