当前位置：Gxlcms > PHP教程 > 自定义levenshtein目的：了解levenshtein算法原理

自定义levenshtein目的：了解levenshtein算法原理

时间：2021-07-01 10:21:17 帮助过：17人阅读

参考： http://www.cnblogs.com/ymind/archive/2012/03/27/fast-memory-efficient-Levenshtein-algorithm.html

function _levenshtein($src, $dst){
if (empty($src)) {
return $dst;
}
if (empty($dst)) {
return $src;
}
$temp = array();
for($i = 0; $i <= strlen($src); $i++) {
$temp[$i][0] = $i;
}
for($j = 0; $j <= strlen($dst); $j++) {
$temp[0][$j] = $j;
}
for ($i = 1;$i <= strlen($src); $i++) {
$src_i = $src{$i - 1};
for ($j = 1; $j <= strlen($dst); $j++) {
$dst_j = $dst{$j - 1};
if ($src_i == $dst_j) {
$cost = 0;
} else {
$cost = 1;
}
$temp[$i][$j] = min($temp[$i-1][$j]+1, $temp[$i][$j-1]+1, $temp[$i-1][$j-1] + $cost);
}
}
return $temp[$i-1][$j-1];
}
echo _levenshtein("hello", "HElloo");

人气教程排行