Diff-Algorithmus mit Fuzzy-Differenz-Metrik

Question

Ich bin auf der Suche nach einem Algorithmus ähnlich wie größte gemeinsame Subsequenz-Algorithmen, die eine Buchstabenähnlichkeit Metrik hat. Was ich meine ist, dass bekannte Algorithmen alle Buchstaben des Alphabets als völlig anders behandeln, mein Anwendungsfall hat Buchstaben des Alphabets, die leichter in einen anderen Buchstaben zu bearbeiten sind, daher sollten sie als ähnlich behandelt werden, indem man Diffing-Algorithmus verwendet.

Als Verwendungsbeispiel können Sie etwas über Diffing-Algorithmus an Textzeilen arbeiten, wo einige Zeilen anderen Zeilen ähnlicher sind.

Das Papier An O(ND) Difference Algorithm and Its Variations Staaten auf Seite 4: Erwägen, ein Gewicht oder Kosten zu jeder Kante hinzuzufügen. Geben Sie diagonale Kanten Gewicht 0 und nicht diagonale Kanten Gewicht 1. Ich hätte gerne eine Option, um Gewicht von [0;1] Intervall zuweisen.

Answer 1

Das größte gemeinsame Subsequenz (LCS) -Problem wird normalerweise durch dynamische Programmiermethoden berechnet, und Sie können vorhandene Methoden optimieren, um sie auf Ihren Anwendungsfall anzuwenden.

In diesem Beispiel zu erläutern, wie LCS Werke (aus Wikipedia) https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example, sollten Sie denken, den Algorithmus zwicken, so dass:

statt Scoring:

score_j = socre_i + 1, für j = i +1 (das heißt, Sie hinzufügen 1, wenn Sie einen neuen allgemeinen Artikel finden) wenn ein neuer Artikel zum LCS hinzugefügt wird, sollten Sie:

score_j = F(score_i, p(letter_i, letter_j)) egal was.

• p(letter_i, letter_j) is the probability to change from letter_i to letter_j (das ist die weight [0, 1] Sie sprechen)
• F ist eine aggreggation Funktion, score_i-score_j zu gehen, dass die Wahrscheinlichkeit p zu kennen.

Zum Beispiel F kann als operator + definiert werden. Es wäre dann ergeben:

score_j = score_i + p(letter_i, letter_j)) oder genauer:

score_j = score_i + p(letter_i, letter_j)) x 1 (lesen Sie die x 1 als of a character)

und dass woud Sie die maximale Ähnlichkeit geben (von Zeichen) der 2 Subsequenzen, dass Sie kann durch Rückverfolgung am Ende des Algorithmus finden.

Sie können Ihre eigene Funktion F finden, um bessere Ergebnisse zu erzielen.