Distanza di Levenshtein con tracciatura posteriore in PHP

Question

Sto cercando di allineare stringhe in PHP usando l'algoritmo di distanza Levenshtein. Il problema è che il mio codice di tracciabilità posteriore non funziona correttamente per tutti i casi. Ad esempio quando il secondo array ha inserito le righe all'inizio. Quindi il tracciamento posteriore andrà solo fino a quando i = 0.

Come implementare correttamente il back tracing per la distanza di Levenshtein?

Levenshtein distanza, $ s e $ t sono array di stringhe (righe)

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

Credo che il bug è esattamente quello che dici nella tua domanda che è: si interrompe non appena i==0 , invece di andare fino a i==0 && j==0. Basta sostituire questa condizione:

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

con

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

e siete a metà strada per la soluzione. Il problema è che se $i==0, non è corretto utilizzare l'indice di array $i-1 nel corpo del ciclo. Così avrete anche a cambiare il corpo del ciclo a qualcosa di più simile

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

Questo non deve essere pignoli esigente, ma per aiutare a trovare le risposte desiderate (e migliorare l'implementazione).

L'algoritmo che si sta utilizzando è l'algoritmo di Wagner-Fischer, non l'algoritmo di Levenshtein. Inoltre, la distanza di Levenshtein non è utilizzata per allineare le stringhe. È strettamente una misurazione della distanza.

Esistono due tipi di allineamento: globale e locale. L'allineamento globale viene utilizzato per ridurre al minimo la distanza tra due intere stringhe. Esempio: allineamento globale "RACE" su "REACH", ottieni "RxACx". Le x sono lacune.

In generale, questo è l'algoritmo di Needleman-Wunsch, che è molto simile all'algoritmo di Wagner-Fischer. L'allineamento locale trova una sottostringa in una stringa lunga e riduce al minimo la differenza tra una stringa breve e una sottostringa della stringa lunga.

Esempio: local allineare "BELL" su "UMBRELLA" e si ottiene "BxELL" allineato su "BRELLO". È l'algoritmo di Smith-Waterman che, ancora una volta, è molto simile all'algoritmo di Wagner-Fischer.

Spero che questo sia utile per consentirvi di definire meglio il tipo esatto di allineamento desiderato.