Php/docs/function.levenshtein
levenshtein
(PHP 4 >= 4.0.1, PHP 5, PHP 7)
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。
范例
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?
参见
- soundex() - Calculate the soundex key of a string
- similar_text() - 计算两个字符串的相似度
- metaphone() - Calculate the metaphone key of a string