So ändern Sie die Levenshteins-Editierdistanz, um "benachbarte Buchstabentauschvorgänge" als 1 Bearbeitung zu zählen

Question

Ich spiele herum mit Levenshteins Edit-Distanz-Algorithmus und ich möchte dies dahingehend erweitern, dass Transpositionen - d. h. der Austausch benachbarter Buchstaben - als 1 Bearbeitung gezählt werden. Der unveränderte Algorithmus zählt Einfügungen, Löschungen oder Ersetzungen, die notwendig sind, um eine bestimmte Zeichenkette von einer anderen zu erreichen. Zum Beispiel ist der Abstand von "KITTEN" zu "SITTING" 3. Hier ist die Erklärung aus Wikipedia:

1. kitten sitten (Ersetzung von 'k' durch 's')
2. sitten sittin (Ersetzung von 'e' durch 'i')
3. sittin sitting (am Ende ein 'g' einfügen).

Nach der gleichen Methode beträgt der Bearbeitungsabstand von "CHIAR" zu "CHAIR" 2:

1. CHIAR CHAR (streichen Sie 'I')
2. CHAR CHAIR (einfügen 'I')

Ich würde dies gerne als "1 Bearbeitung" zählen, da ich nur zwei benachbarte Buchstaben austausche. Wie würde ich vorgehen?

Answer 1

Im Algorithmus von Wikipedia wird ein weiterer Fall benötigt:

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

Sie müssen die Art und Weise ändern, wie Sie die dynamische Programmiertabelle aktualisieren. Im ursprünglichen Algorithmus berücksichtigt man die Schwänze (oder Köpfe) der beiden Wörter, die sich höchstens um die Länge eins unterscheiden. Die Aktualisierung ist das Minimum aller dieser Möglichkeiten.

Wenn Sie den Algorithmus so ändern wollen, dass Änderungen an zwei benachbarten Stellen als eine zählen, muss das obige Minimum über Schwänze (oder Köpfe) berechnet werden, die sich um höchstens zwei unterscheiden. Man kann dies auf größere Nachbarschaften ausdehnen, aber die Komplexität nimmt mit der Größe der Nachbarschaft exponentiell zu.

Sie können weiter verallgemeinern und Kosten zuweisen, die von den gelöschten, eingefügten oder ersetzten Zeichen abhängen, aber Sie müssen sicherstellen, dass die Kosten, die Sie einem Paar-Edit zuweisen, niedriger sind als zwei Einzel-Edits, da sonst die beiden Einzel-Edits immer gewinnen werden.

Die Wörter seien w1 und 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))
                ) 

Was ich damit meine, ist die && ist, dass diese Linien nur berücksichtigt werden sollten, wenn die Bedingungen erfüllt sind.

Answer 3

Die anderen Antworten implementieren den Optimal String Alignment Algorithmus, nicht Damerau Levenshtein Ich glaube, das ist es, was Sie beschreiben.

Ich habe eine Java-Implementierung von OSA mit einigen Optimierungen hier: https://gist.github.com/steveash/5426191