levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

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

说明

levenshtein(string $str1, string $str2): int

levenshtein(
    string $str1,
    string $str2,
    int $cost_ins,
    int $cost_rep,
    int $cost_del
): int

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

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

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

参数

str1: 求编辑距离中的其中一个字符串
str2: 求编辑距离中的另一个字符串
cost_ins: 定义插入次数
cost_rep: 定义替换次数
cost_del: 定义删除次数

返回值

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

范例

示例 #1 levenshtein() 例子：

<?php 
// 输入拼写错误的单词$input = 'carrrot';
// 要检查的单词数组$words  = array('apple','pineapple','banana','orange',                'radish','carrot','pea','bean','potato');
// 目前没有找到最短距离$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: $input\n";
if ($shortest == 0) {
    echo "Exact match found: $closest\n";
}
 else {
    echo "Did you mean: $closest?\n";
}
?>

以上例程会输出：

Input word: carrrot
Did you mean: carrot?

参见

soundex() - Calculate the soundex key of a string
similar_text() - 计算两个字符串的相似度
metaphone() - Calculate the metaphone key of a string

PHP（0）