我试图使用Levenshtein距离算法在 PHP中对齐字符串.问题是我的后跟踪代码在所有情况下都不能正常工作.例如,当第二个数组在开头插入行时.那么后面的跟踪只能在i = 0的时候进行.

如何正确实施追溯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;
    }
}