PHP中查找最相似字符串的最佳方法是什么？

Question

您好，

PHP 有很多字符串函数，例如 levenshtein、similar_text 和 soundex，可以用于比较字符串的相似性。 http://www.php.net/manual/en/function.levenshtein.php

对于准确性和性能来说，哪个函数是最好的？

- giorgio79

---

我认为这更适合作为社区维基。 - Jim

不需要了解太多不同函数的实现细节，我有一种直觉感觉你不能同时追求准确性和性能。它们可能有点成反比。 - András Szepesházi

@András，您可能能够回答哪种更适合性能，哪种更适合准确性。 - Adam

我认识一个人想要类似这样的东西。他最终使用了命令行diff工具！ - Jake N

Answer 1

similar_text 的复杂度为 O(max(n,m)**3)，而 levenshtein 的复杂度为 O(m*n)，其中 n 和 m 是字符串的长度，因此 levenshtein 应该更快。两种方法都是 100％ 准确的，因为它们为相同的输入提供相同的输出，但每个函数的输出将不同。如果您使用不同的准确性度量，您将需要创建自己的比较函数。

- Mark Rose

---

实际上，刚刚在 PHP 上检查了一下，它们的复杂度是不同的：“(Levenshtein)算法的复杂度为O(m*n)，其中n和m是str1和str2的长度（与similar_text()相比相当不错，后者的复杂度为O(max(n,m)**3)，但仍然很昂贵)。” - giorgio79

这很大程度上取决于您认为什么是不同的。我发现similar_text更适合我的情况。如果字符串长度相同，levenshtein将返回更多的相似性。例如：与“rob blabla”相比，“marco blabla”的相似度为81.8%（similar_text），并且为4（levenshtein）。而“jan blabla”与“rob blabla”相比，则为70％（similar_text）和3（levenshtein）。因此，levenshtein认为最后一个更相似，而similar_text则认为前面更相似。 - Lode

Answer 2

你没有描述你的使用情况，但在许多情况下，当我们谈论自然语言时，单词比字符更重要，因此使用similar_text()和levenshtein()可能会以非常高的计算成本得到不太有意义的结果。

例如，使用以上方法在几千篇文章中搜索类似标题的文章可能会轻易地使服务器负载过高。

我通常会编写一个简单的函数，接受两个字符串，将它们按空格拆分为数组，并计算它们的交集以获得低CPU成本的更自然匹配分数。

通过一些改进，它可以在多种用例中表现出色，例如从其他内容中过滤出快速推荐博客中的文章。

我通常实施以下改进：

- 将字符串转为小写 - 按照匹配元素的长度加权得分，考虑到长字符串更难匹配，也倾向于指示主题之间更有意义的相似性。 - 在比较之前去除只调节含义的常用词汇 - 这是语言相关的，在英语中可能是这样一个列表：was，were，no，not，than，then，here，there等。 - 在比较之前去除字符串中的所有标点符号。 - 处理合成语言时，可以在选择它们的交集之前，对单词数组增加用最常见的后缀长度截断的单词变体。

这不是完美的，但是相较于同一台服务器上使用levenshtein处理同样的任务需要10-15秒，而且无法接受，这个算法可以处理大约5000篇博客文章，并快速给出3篇非常好的相似文章，同时对性能影响不明显。

如果需要差异而不是相似性，则可以取分数的倒数或者在数组diff之后使用非匹配项，而不是在数组交集之后计算匹配项的数量。

- Bence Szalai