php levenshtein 算法原理

[php]代码库

//Levenshtein算法，用于计算两个字符串之间的Levenshtein距离。而Levenshtein距离又称为编辑距离，是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

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");
//该片段来自于http://yuncode.net