最受欢迎

如何按与输入单词的相似性对数组进行排序

How to sort an array by similarity in relation to an inputted word.

本文关键字：数组 排序 相似性 何按 输入 单词 | 更新日期: 2023-09-27

我在PHP数组上有，例如：

$arr = array("hello", "try", "hel", "hey hello");

现在我想重新排列数组，这将基于数组和我的$search var 之间最接近的单词。

我该怎么做？

这是一个使用 http://php.net/manual/en/function.similar-text.php 的快速解决方案：

这将计算两个字符串之间的相似性，如 Oliver 的编程经典：实现世界上最好的算法 (ISBN 0-131-00413-1( 中所述。请注意，此实现不使用 Oliver 伪代码中的堆栈，而是使用递归调用，这可能会也可能不会加快整个过程。另请注意，此算法的复杂性为 O(N**3(，其中 N 是最长字符串的长度。

    $input = 'Bradley123';
    $list = array('Bob', 'Brad', 'Britney');
    usort($list, fn($a, $b) => similar_text($input, $a) <=> similar_text($input, $b));
    
    var_dump($list); //output: array("Brad", "Britney", "Bob");
<小时 />

或使用 http://php.net/manual/en/function.levenshtein.php：

Levenshtein 距离定义为将 str1 转换为 str2 时必须替换、插入或删除的最小字符数。该算法的复杂度为 O(m*n(，其中 n 和 m 是 str1 和 str2 的长度(与 similar_text(( 相比相当不错，后者是 O(max(n，m(**3(，但仍然很昂贵(。

    $input = 'Bradley123';
    $list = array('Bob', 'Brad', 'Britney');
    usort($list, fn($a, $b) => levenshtein($input, $a) <=> levenshtein($input, $b));
    var_dump($list); //output: array("Britney", "Brad", "Bob");

您可以使用 levenshtein 函数

<?php
// input misspelled word
$input = 'helllo';
// array of words to check against
$words  = array('hello' 'try', 'hel', 'hey hello');
// no shortest distance found, yet
$shortest = -1;
// loop through words to find the closest
foreach ($words as $word) {
    // calculate the distance between the input word,
    // and the current word
    $lev = levenshtein($input, $word);
    // check for an exact match
    if ($lev == 0) {
        // closest word is this one (exact match)
        $closest = $word;
        $shortest = 0;
        // break out of the loop; we've found an exact match
        break;
    }
    // if this distance is less than the next found shortest
    // distance, OR if a next shortest word has not yet been found
    if ($lev <= $shortest || $shortest < 0) {
        // set the closest match, and shortest distance
        $closest  = $word;
        $shortest = $lev;
    }
}
echo "Input word: $input'n";
if ($shortest == 0) {
    echo "Exact match found: $closest'n";
} else {
    echo "Did you mean: $closest?'n";
}
?>

如果你想对数组进行排序，你可以这样做：

$arr = array("hello", "try", "hel", "hey hello");
$search = "hey"; //your search var
for($i=0; $i<count($arr); $i++) {
   $temp_arr[$i] = levenshtein($search, $arr[$i]);
}
asort($temp_arr);
foreach($temp_arr as $k => $v) {
    $sorted_arr[] = $arr[$k];
}

然后，$sorted_arr应按降序排列，从最接近搜索词的单词开始。

虽然@yceruto的答案是正确的，内容丰富，但我想扩展其他见解并演示更现代的实现语法。

  • 来自 PHP7+ 的三向比较运算符(又名"宇宙飞船操作员"(<=>
  • 箭头函数语法，允许额外的变量从 PHP7.4+ 进入自定义函数范围。

首先是关于从各个函数生成的分数...

  1. levenshtein()和similar_text()区分大小写，因此与h相比，大写H与数字6不匹配一样多。
  2. levenshtein()和similar_text()不是多字节感知的，所以像ê这样的重音字符不仅会被视为e的不匹配，而且可能会因为每个字节的不匹配而受到更重的惩罚。

如果要进行不区分大小写的比较，只需在执行之前将两个字符串都转换为大写/小写即可。

如果您的应用程序需要多字节支持，则应搜索提供此功能的现有存储库。

对于那些愿意更深入研究的人来说，其他技术包括metaphone((和soundex((，但我不会在这个答案中深入研究这些主题。

分数：

Test vs "hello" |  levenshtein   |  similar_text  |   similar_text's percent   |
----------------+----------------+----------------+----------------------------|
H3||0           |       5        |      0         |       0                    |
Hallo           |       2        |      3         |      60                    |
aloha           |       5        |      2         |      40                    |
h               |       4        |      1         |      33.333333333333       |
hallo           |       1        |      4         |      80                    |
hallå           |       3        |      3         |      54.545454545455       |
hel             |       2        |      3         |      75                    |
helicopter      |       6        |      4         |      53.333333333333       |
hellacious      |       5        |      5         |      66.666666666667       |
hello           |       0        |      5         |     100                    |
hello y'all     |       6        |      5         |      62.5                  |
hello yall      |       5        |      5         |      66.666666666667       |
helów           |       3        |      3         |      54.545454545455       |
hey hello       |       4        |      5         |      71.428571428571       |
hola            |       3        |      2         |      44.444444444444       |
hêllo           |       2        |      4         |      72.727272727273       |
mellow yellow   |       9        |      4         |      44.444444444444       |
try             |       5        |      0         |       0                    |
<小时 />

按levenshtein()排序 PHP7+ (演示(

usort($testStrings, function($a, $b) use ($needle) {
    return levenshtein($needle, $a) <=> levenshtein($needle, $b);
});

排序方式 levenshtein() PHP7.4+ (演示(

usort($testStrings, fn($a, $b) => levenshtein($needle, $a) <=> levenshtein($needle, $b));
<小时 />

**请注意，$a 和 $b 在 DESC 排序的<=>评估中发生了变化。请注意，不能保证将hello定位为第一个元素

排序方式 similar_text() PHP7+ (演示(

usort($testStrings, function($a, $b) use ($needle) {
    return similar_text($needle, $b) <=> similar_text($needle, $a);
});

排序方式 similar_text() PHP7.4+ (演示(

usort($testStrings, fn($a, $b) => similar_text($needle, $b) <=> similar_text($needle, $a));
<小时 />

请注意通过 similar_text(( 的返回值与 similar_text(( 的百分比值对 hallå 和helicopter的评分差异。

按similar_text()百分比排序 PHP7+ (演示(

usort($testStrings, function($a, $b) use ($needle) {
    similar_text($needle, $a, $percentA);
    similar_text($needle, $b, $percentB);
    return $percentB <=> $percentA;
});

按similar_text()百分比排序 菲律宾比索7.4+(演示(

usort($testStrings, fn($a, $b) => 
    [is_int(similar_text($needle, $b, $percentB)), $percentB]
    <=>
    [is_int(similar_text($needle, $a, $percentA)), $percentA]
);

请注意，我通过将similar_text()的返回值转换为 true 来中和不需要的返回值，然后使用生成的percent值 - 这允许在不过早返回的情况下生成百分比值，因为箭头函数语法不允许多行执行。

<小时 />

按levenshtein()高效排序，然后仅在需要决胜时调用similar_text()，PHP7+(演示(

usort($testStrings, function($a, $b) use ($needle) {
    return levenshtein($needle, $a) <=> levenshtein($needle, $b)
           ?: similar_text($needle, $b) <=> similar_text($needle, $a);
});

按levenshtein()高效排序，然后仅在需要平局时调用similar_text()并使用其百分比， PHP7.4+ (演示(

usort($testStrings, fn($a, $b) =>
    levenshtein($needle, $a) <=> levenshtein($needle, $b)
    ?: similar_text($needle, $b) <=> similar_text($needle, $a)
);

就我个人而言，我在我的项目中从不使用除levenshtein()之外的任何东西，因为它始终如一地提供我正在寻找的结果。

<小时 />

为了减少总函数调用并提高性能，所有这些方法都可以转移到array_multisort()实现中。 您只需要构建评估的平面数组，然后将这些数组添加为参数，然后最后一个参数应该是原始数组。

另一种方法是使用similar_text函数，该函数以百分比返回结果。查看更多 http://www.php.net/manual/en/function.similar-text.php 。

相关文章：
最新更新
www.56WenDa.com 2012-2023 | php问答网 | php学习