Расстояние Левенштейна с обратной трассировкой в PHP

Я пытаюсь выровнять строки в PHP с использованием алгоритма расстояния Левенштейна. Проблема в том, что мой обратный код отслеживания не работает должным образом для всех случаев. Например, когда второй массив вставил строки в начале. Тогда обратная трассировка будет идти только до я = 0.

Как правильно выполнить обратную трассировку для расстояния Левенштейна?

Расстояние Левенштейна, $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][$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;
    }
}

Ответ 1

Это не должно быть ничтожным, но чтобы помочь вам найти нужные ответы (и улучшить вашу реализацию).

Алгоритм, который вы используете, - это алгоритм Вагнера-Фишера, а не алгоритм Левенштейна. Кроме того, расстояние Левенштейна не используется для выравнивания строк. Это строго измерение расстояния.

Существует два типа выравнивания: глобальный и локальный. Глобальное выравнивание используется для минимизации расстояния между двумя целыми строками. Пример: глобальное выравнивание "RACE" на "REACH", вы получаете "RxACx". X - промежутки.

В общем, это алгоритм Needleman-Wunsch, который очень похож на алгоритм Вагнера-Фишера. Локальное выравнивание находит подстроку в длинной строке и минимизирует разницу между короткой строкой и подстрокой длинной строки.

Пример: локальный выровнять "BELL" на "UMBRELLA", и вы получите "BxELL", выровненный по "BRELL". Это алгоритм Смита-Уотермана, который, опять же, очень похож на алгоритм Вагнера-Фишера.

Я надеюсь, что это поможет вам лучше определить точный тип выравнивания, который вы хотите.

Ответ 2

Я думаю, что ваша ошибка - это именно то, что вы говорите в своем вопросе, что это: вы останавливаетесь, как только i==0, вместо того, чтобы идти до i==0 && j==0. Просто замените это условие:

while($i > 0 && $j > 0)

while ($i > 0 || $j > 0)

и вы на полпути к вашему решению. Сложный бит заключается в том, что если $i==0, то неверно использовать индекс массива $i-1 в теле цикла. Таким образом, вам также придется изменить тело цикла на нечто большее, чем

while ($i || $j) {
    $min = $d[$i][$j];  // or INT_MAX or something
    if ($i && $j && $min > $d[$i-1][$j-1]) {
        $newi = $i-1;
        $newj = $j-1;
        $min = $d[$newi][$newj];
    }
    if ($i && $min > $d[$i-1][$j]) {
        $newi = $i-1;
        $newj = $j;
        $min = $d[$newi][$newj];
    }
    if ($j && $min > $d[$i][$j-1]) {
        $newi = $i;
        $newj = $j-1;
        $min = $d[$newi][$newj];
    }

    // What sort of transformation is this?
    if ($newi == $i && $newj == $j) {
        assert(false);  // should never happen
    } else if ($newi == $i) {
        // insertion
        $ins[] = $j;
    } else if ($newj == $j) {
        // deletion
        $del[] = $i;
    } else if ($d[$i][$j] != $d[$newi][$newj]) {
        // substitution
        $sub['i'][] = $i;
        $sub['j'][] = $j;
    } else {
        // identity
    }

    assert($newi >= 0); assert($newj >= 0);
    $i = $newi;
    $j = $newj;
}