10

レーベンシュタイン距離アルゴリズムを使用して、PHP で文字列を整列させようとしています。問題は、私のバック トレース コードがすべてのケースで適切に機能しないことです。たとえば、2 番目の配列の先頭に行が挿入されている場合です。その場合、バック トレースは i=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;
    }
}
4

2 に答える 2

3

これは細かいことを言うのではなく、必要な答えを見つける (そして実装を改善する) のに役立ちます。

使用しているアルゴリズムは、レーベンシュタイン アルゴリズムではなく、ワーグナー フィッシャー アルゴリズムです。また、文字列の整列にはレーベンシュタイン距離は使用されません。厳密には距離測定です。

アライメントには、グローバルとローカルの 2 種類があります。グローバル アライメントは、2 つの文字列全体の間の距離を最小限に抑えるために使用されます。例: グローバル アライメント "RACE" を "REACH" にすると、"RxACx" が得られます。×は隙間です。

一般に、これはニードルマン-ヴンシュ アルゴリズムであり、ワーグナー-フィッシャー アルゴリズムに非常に似ています。ローカル アラインメントは、長い文字列の部分文字列を検出し、短い文字列と長い文字列の部分文字列の違いを最小限に抑えます。

例: "UMBRELLA" に "BELL" をローカルに配置すると、"BRELL" に配置された "BxELL" が得られます。ワーグナー フィッシャー アルゴリズムに非常によく似たスミス ウォーターマン アルゴリズムです。

これが、必要な正確な種類の配置をより適切に定義できるようにするのに役立つことを願っています.

于 2013-03-08T21:03:08.733 に答える
0

あなたのバグはまさにあなたが質問で言ってi==0いることだと思いますi==0 && j==0. この条件を置き換えるだけです。

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

と

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

そして、あなたは解決策の途中です。注意が必要なのは、 ifの場合、ループ本体で$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 に答える