字符串函数 levenshtein ()

levenshtein() 计算两个字符串之间的编辑距离

levenshtein(string str1, string str2,int insert,int replace,int delete):int

编辑距离，是指两个字串之间，通过替换、插入、删除等操作将字符串str1转换成str2所需要操作的最少字符数量。 该算法的复杂度是 O(m * n)，其中 n 和 m 分别是str1 和str2的长度 （当和算法复杂度为 O(max(n,m)**3) 的 similar_text() 相比时，此函数还是相当不错的，尽管仍然很耗时。）。

在最简单的形式中，该函数只以两个字符串作为参数，并计算通过插入、替换和删除等操作将str1转换成str2所需要的操作次数。

第二种变体将采用三个额外的参数来定义插入、替换和删除操作的次数。此变体比第一种更加通用和适应，但效率不高。

返回值：
此函数返回两个字符串参数之间的编辑距离，如果其中一个字符串参数长度大于限制的255个字符时，返回-1。

$input  = 'carrrot';

$words = ['apple','pineapple','banana','orange','radish','carrot'];

$shortest = -1;

foreach ($words as $word) {
    $lev = levenshtein($input,$word);

    if ($lev == 0) {  //完全匹配
        $closest = $word;
        $shortest = 0;
        break;
    }

    // 如果此次距离比上次找到的要短
    // 或者还没找到接近的单词
    if ($lev <= $shortest || $shortest < 0) {
        $closest = $word;
        $shortest = $lev;
    }
}

echo 'input word:<br>';
if ($shortest == 0) {
    echo 'exact match found:'.$closest.'<br>';
} else {
    echo 'did you mean: '.$closest.'<br>';
}

// input word:
// did you mean: carrot

本作品采用《CC 协议》，转载必须注明作者和本文链接