Edit Question - KnowledgeHub

Title Body

I'm trying to align strings in PHP using Levenshtein distance algorithm. The problem is that my back tracing code does not work properly for all cases. For example when the second array has inserted lines at the beginning. Then the back tracing will only go as far as when i=0. How to properly implement back tracing for Levenshtein distance? Levenshtein distance, $s and $t are arrays of strings (rows) 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][$j-1], $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; } }

Tags (comma-separated) Cancel