Wie man Levenshteins bearbeiten Entfernung ändern „benachbarte Buchstaben tauscht“, wie 1 bearbeiten zu zählen

Question

Ich spiele um mit Levenshteins bearbeiten Entfernung Algorithmus , und ich möchte diese erweitern Umstellungen zu zählen -, dass ist, den Austausch von benachbarten Buchstaben - wie 1 Bearbeiten. Die unmodifizierten Algorithmus zählt Einfügungen, Löschungen oder Substitutionen benötigt eine bestimmte Zeichenfolge von einem anderen zu erreichen. Zum Beispiel ist die Edit-Distanz von „KITTET“ auf „SITZT“ 3. Hier ist die Erklärung von Wikipedia:

1. Kätzchen ? sitten (Substitution von 'k' mit 's')
2. sitten ? Sittin (Substitution von 'e' mit 'i')
3. Sittin ? Sitz (insert 'g' am Ende).

Nach dem gleichen Verfahren wird die Edit-Distanz von „chiar“ auf „Stuhl“ ist 2:

1. chiar ? CHAR (delete 'I')
2. CHAR ? STUHL (insert 'I')

würde Ich mag diese zählen, als „1 bearbeiten“, da ich nur zwei benachbarte Buchstaben auszutauschen. Wie würde ich gehen, um dies zu tun?

Answer 1

Sie müssen einen weiteren Fall, in dem Algorithmus aus 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

Sie haben zu ändern, wie Sie die dynamische Programmierung Tabelle aktualisieren. In dem ursprünglichen Algorithmus betrachtet man den Schwanz (oder Köpfe) der beiden Worte, die am meisten durch Länge abweichen. Das Update ist das Minimum aller solcher Möglichkeiten.

Wenn Sie den Algorithmus, so dass Änderungen in zwei benachbarten Standorten zählen als eine ändern wollen, muss der Mindest oben über Schwanz berechnet werden (oder Köpfe), die von höchstens zwei unterscheiden. Sie können dies zu größeren Nachbarschaften erweitern aber die Komplexität exponentiell in der Größe dieser Nachbarschaft erhöhen.

Sie können verallgemeinern weiter und assign Kosten, die auf den Charakter abhängen (n) gelöscht, eingefügt oder substituiert, aber Sie müssen sicherstellen, dass die Kosten, die Sie zu einem Paar-edit zuweisen niedriger als zwei einzelne Änderungen, da sonst die beiden einzelne Bearbeitungen werden immer gewinnen.

Lassen Sie die Worte 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 die && ist, dass diese Linien nur in Betracht gezogen werden sollten, wenn die Bedingungen erfüllt sind.

Answer 3

Die anderen Antworten sind zur Durchführung des optimalen String Alignment-Algorithmus, nicht Damerau Levenshtein was ich denke, ist das, was Sie beschreiben.

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