Odległość Levenshteina z powrotem śledzenia w PHP

Question

Próbuję wyrównać ciągów w PHP przy użyciu algorytmu odległości Levenshtein. Problem polega na tym, że mój kod śledzenia wstecznego nie działa poprawnie we wszystkich przypadkach. Na przykład, gdy druga tablica wstawiła linie na początku. W takim przypadku śledzenie wstecz będzie przebiegać tak daleko, jak tylko i = 0.

Jak prawidłowo zaimplementować funkcję śledzenia wstecznego dla odległości Levenshtein?

Odległość Levenshteina, $ s i $ t są tablice ciągów (wiersze)

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; 
    } 
} 

Answer 1

Myślę, że błąd jest dokładnie to, co mówisz w swoim pytaniu, że jest: zatrzymać jak najszybciej i==0 zamiast przechodzić całą drogę do i==0 && j==0. Wystarczy wymienić ten warunek:

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

z

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

i jesteś w połowie drogi do rozwiązania. Trudny bit jest taki, że jeśli $i==0, to niewłaściwe jest używanie indeksu tablicy $i-1 w ciele pętli. Więc będziesz też musiał zmienić ciało pętli do czegoś więcej jak

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; 
} 

Answer 2

To nie ma być nit-wybredna, ale aby pomóc znaleźć odpowiedzi, które chcesz (i poprawić wdrażanie).

Algorytm, którego używasz, to algorytm Wagnera-Fischera, a nie algorytm Levenshteina. Ponadto odległość Levenshtein nie jest używana do wyrównania łańcuchów. Jest to wyłącznie pomiar odległości.

Istnieją dwa rodzaje wyrównania: globalny i lokalny. Globalne wyrównanie służy do minimalizacji odległości między dwoma ciągami. Przykład: globalne wyrównanie "RACE" w "REACH", otrzymasz "RxACx". X są lukami.

Generalnie jest to algorytm Needlemana-Wunscha, który jest bardzo podobny do algorytmu Wagnera-Fischera. Lokalne wyrównanie znajduje podciąg w długim łańcuchu i minimalizuje różnicę między krótkim ciągiem a podciągłem długiego łańcucha.

Przykład: lokalne wyrównaj "BELL" na "UMBRELLA", a otrzymasz "BxELL" ustawione na "BRELL". Jest to algorytm Smitha-Watermana, który jest znowu bardzo podobny do algorytmu Wagnera-Fischera.

Mam nadzieję, że jest to pomocne w lepszym określeniu dokładnego rodzaju wyrównania.