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

2017-12-19 09:19:34
linefo
494
最后编辑:linefo 于 2017-12-19 09:30:35

levenshtein

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

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

说明

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

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

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

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

参数

str1

求编辑距离中的其中一个字符串

str2

求编辑距离中的另一个字符串

cost_ins

定义插入次数

cost_rep

定义替换次数

cost_del

定义删除次数

返回值

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

范例

Example #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?

参见