php - 在 PHP 中查找最相似的字符串？

Question

我有一个包含 17,000 个字符串的数组。许多字符串具有相似的匹配项，例如：

User Report XYZ123
Bob Smith
User Report YEI723
User Report
User Report
Number of Hits 27
Frank's Weekly Transaction Report
Transaction Report 123

找到顶部“相似字符串”的最佳方法是什么？例如，使用上面的示例，我希望将“用户报告”和“交易报告”视为两个顶级“相似字符串”。

Answer 1

在不提供所有源代码的情况下，您可以遍历数组并删除您认为无用的组件，例如任何带有数字的字母等等。

然后，您可以使用array_count_values()该数组并对其进行排序以查看所涉及的最重要的数组。

Answer 2

您可以计算每个字符串与其他字符串相比的Levenstein 距离，然后按该值对它们进行排序。

$strings = array('str1', 'str2', 'car', 'dog', 'apple', 'house', 'str3');
$len = count($strings);

$distances = array_fill(0, $len, 0);

for($i=0; $i<$len-1; ++$i)
    for($j=$i+1; $j<$len; ++$j)
    {
        $dist = levenshtein($strings[$i], $strings[$j]);
        $distances[$i] += $dist;
        $distances[$j] += $dist;
    }

// Here $distances indicates how of "similar" is each string
// The lower values are more "similar"

Answer 3

我想您可以对每个字符串进行 foreach 并消除您不希望用于特定搜索的字符串。然后在您离开后（可能与另一个 foreach）一起检查并继续减少您感兴趣的字符串的数量，直到只有几个。然后按字母顺序对它们进行排序。

Answer 4

如果您能够将所有字符串作为数组获取并foreach()像这样循环它们：

$string_array = array('string', 'string1', 'string2', 'does-not-match');
$needle = 'string';

$results = array();
foreach($string_array as $key => $val):
    if (fnmatch($needle, $val):
        $results[] = $val;
    endif;
endforeach;

最后，您应该结束匹配的条目$needle。作为替代fnmatch()你可以使用preg_match()和作为模式/string/i

$string_array = array('string', 'string1', 'string2', 'does-not-match');
$needle = '/string/i';

$results = array();
foreach($string_array as $key => $val):
    if (!empty(preg_match($needle, $val)):
        $results[] = $val;
    endif;
endforeach;

请注意，使用 empty() 并传递 preg_match() 的结果时可能会出现问题：

在 PHP 5.5 之前，empty() 只支持变量；其他任何事情都会导致解析错误。换句话说，以下内容将不起作用：empty(trim($name))。相反，使用 trim($name) == false。

PHP 版本 5.3.x < 5.4 不会出现错误