10

我正在尝试使用 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][$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;
    }
}
4

2 回答 2

3

这不是挑剔，而是帮助您找到您想要的答案（并改进您的实施）。

您使用的算法是 Wagner-Fischer 算法，而不是 Levenshtein 算法。此外，Levenshtein 距离不用于对齐字符串。这是严格的距离测量。

有两种对齐方式：全局对齐和局部对齐。全局对齐用于最小化两个完整字符串之间的距离。示例：在“REACH”上全局对齐“RACE”，你会得到“RxACx”。x 是间隙。

一般来说，这是 Needleman-Wunsch 算法，它与 Wagner-Fischer 算法非常相似。局部对齐在长字符串中找到子字符串，并最小化短字符串和长字符串的子字符串之间的差异。

示例：在“UMBRELLA”上局部对齐“BELL”，然后在“BRELL”上对齐“BxELL”。这是 Smith-Waterman 算法，它再次与 Wagner-Fischer 算法非常相似。

我希望这有助于您更好地定义所需的确切对齐方式。

于 2013-03-08T21:03:08.733 回答
0

我认为您的错误正是您在问题中所说的：您立即停止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;
}
于 2013-01-01T21:34:06.567 回答