如何正确实施追溯Levenshtein距离?
Levenshtein距离,$s和$t是字符串(行)的数组
function match_rows($s,$t) { $m = count($s); $n = count($t); for($i = 0; $i <= $m; $i++) $d[$i][0] = $i; for($j = 0; $j <= $n; $j++) $d[0][$j] = $j; for($i = 1; $i <= $m; $i++) { for($j = 1; $j <= $n; $j++) { if($s[$i-1] == $t[$j-1]) { $d[$i][$j] = $d[$i-1][$j-1]; } else { $d[$i][$j] = min($d[$i-1][$j],$d[$i][$j-1],$d[$i-1][$j-1]) + 1; } } } // backtrace $i = $m; $j = $n; while($i > 0 && $j > 0) { $min = min($d[$i-1][$j],$d[$i-1][$j-1]); switch($min) { // equal or substitution case($d[$i-1][$j-1]): if($d[$i][$j] != $d[$i-1][$j-1]) { // substitution $sub['i'][] = $i; $sub['j'][] = $j; } $i = $i - 1; $j = $j - 1; break; // insertion case($d[$i][$j-1]): $ins[] = $j; $j = $j - 1; break; // deletion case($d[$i-1][$j]): $del[] = $i; $i = $i - 1; break; } }