Come modificare Levenshteins Modifica Distanza per contare "scambi di lettere adiacenti" come 1 modifica

Question

Sto giocando con Levenshteins Edit Distance algorithm e voglio estenderlo per contare le trasposizioni - ovvero, scambi di lettere adiacenti - come 1 modifica . L'algoritmo non modificato conta inserimenti, eliminazioni o sostituzioni necessarie per raggiungere una determinata stringa da un'altra. Per esempio, la modifica distanza dal "kitten" per "seduta" è 3. Ecco la spiegazione da Wikipedia:

1. gattino → Sitten (sostituzione di 'k' con 's')
2. Sitten → sittin (sostituzione di 'e' con 'i')
3. sittin → sitting (inserire 'g' alla fine).

Seguendo lo stesso metodo, la modifica distanza dal "Chiar" a "sedia" è 2:

1. Chiar → CHAR (delete 'I')
2. CAR → SEDIA (inserire 'I ')

Vorrei contarlo come "1 modifica", poiché scambio solo due lettere adiacenti. Come potrei andare a fare questo?

Answer 1

è necessario un caso più l'algoritmo da Wikipedia:

if s[i] = t[j] then 
    d[i, j] := d[i-1, j-1] 
else if i > 0 and j > 0 and s[i] = t[j - 1] and s[i - 1] = t[j] then 
    d[i, j] := minimum 
      (
       d[i-2, j-2] + 1 // transpose 
       d[i-1, j] + 1, // deletion 
       d[i, j-1] + 1, // insertion 
       d[i-1, j-1] + 1 // substitution 
      ) 
else 
    d[i, j] := minimum 
      (
       d[i-1, j] + 1, // deletion 
       d[i, j-1] + 1, // insertion 
       d[i-1, j-1] + 1 // substitution 
      ) 

Answer 2

È necessario modificare come si aggiorna la tabella di programmazione dinamica. Nell'algoritmo originale si considerano le code (o le teste) delle due parole che differiscono al massimo dalla lunghezza uno. L'aggiornamento è il minimo di tutte queste possibilità.

Se si desidera modificare l'algoritmo in modo tale che i cambiamenti in due posizioni adiacenti contino come uno, il minimo sopra deve essere calcolato su code (o teste) che differiscono di al massimo due. Puoi estenderlo a quartieri più grandi, ma la complessità aumenterà esponenzialmente nelle dimensioni di quel quartiere.

È possibile generalizzare ulteriormente e assegnare costi che dipendono dal carattere (i) cancellato, inserito o sostituito, ma è necessario assicurarsi che il costo che si assegna ad una modifica di coppia sia inferiore a due singole modifiche, altrimenti il due singole modifiche vinceranno sempre.

Vediamo le parole siano W1 e W2

dist(i,j) = min(
       dist(i-2,j-2) && w1(i-1,i) == w2(j-1,j) else 
       dist(i-1,j-1) && w1(i) == w2(j) else 
       dist(i,j-1) + cost(w2(j)), 
       dist(i-1,j) + cost(w1(i)), 
       dist(i-1,j-1) + cost(w1(i), w2(j)), 
       dist(i, j-2) + cost(w2(j-1,j)), 
       dist(i-2, j) + cost(w1(i-1,i)), 
       dist(i-2,j-2) + cost(w1(i-1,i), w2(j-1,j)) 
       ) 

Quello che voglio dire il && è che queste linee dovrebbero essere prese in considerazione solo se le condizioni sono soddisfatte.

Answer 3

Le altre risposte stanno implementando l'algoritmo di allineamento ottimale delle stringhe, non Damerau Levenshtein che penso sia quello che stai descrivendo.

Ho un'implementazione Java di OSA con alcune ottimizzazioni qui: https://gist.github.com/steveash/5426191