Ich setze "Brocken-Transposition" in Anführungszeichen, weil ich nicht weiß, ob oder wie der Fachbegriff sein sollte. Es wäre sehr hilfreich zu wissen, ob es einen technischen Begriff für den Prozess gibt.
Der Wikipedia-Artikel über die Bearbeitungsentfernung gibt einen guten Überblick über das Konzept.
Indem ich "Chunk Transposition" in Betracht ziehe, meine ich das
%Vor%sollte mit
übereinstimmen %Vor%genauer als es passt
%Vor%i.e. Die Abstandsberechnung sollte erkennen, wenn Teilstrings des Textes einfach innerhalb des Textes verschoben wurden. Dies ist bei der üblichen Levenshtein-Abstandsformel nicht der Fall.
Die Strings werden höchstens einige hundert Zeichen lang sein - sie sind Autorennamen oder Listen von Autorennamen, die in verschiedenen Formaten vorliegen können. Ich mache keine DNA-Sequenzierung (obwohl ich vermute, dass Leute, die das tun, etwas über dieses Thema wissen werden).
Sehen Sie sich die Jaccard-Abstandsmetrik (JDM) an. Es ist ein Oldie-aber-Goodie, der ziemlich gut bei Diskrepanzen auf Token-Niveau ist, wie Nachname zuerst, Vorname zuletzt. Bei zwei String-Comparanden ist die JDM-Berechnung einfach die Anzahl der eindeutigen Zeichen, die die zwei Strings gemeinsam haben, geteilt durch die Gesamtzahl der eindeutigen Zeichen zwischen ihnen (mit anderen Worten die Schnittmenge über die Vereinigung). Zum Beispiel ist der Zähler bei den zwei Argumenten "JEFFKTYZZER" und "TYZZERJEFF" 7 und der Nenner ist 8, was einen Wert von 0,875 ergibt. Meine Wahl der Zeichen als Token ist nicht die einzige verfügbare, BTW - N-Gramm werden oft auch verwendet.
Im Falle Ihrer Bewerbung sollten Sie wahrscheinlich über die Anpassung einiger Algorithmen aus der Bioinformatik nachdenken.
Zum Beispiel könnten Sie zuerst Ihre Strings vereinheitlichen, indem Sie sicherstellen, dass alle Separatoren Leerzeichen oder etwas anderes sind, das Sie mögen, so dass Sie "Alan Turing" mit "Turing Alan" vergleichen würden. Und dann eine der Strings aufteilen und einen genauen String-Matching-Algorithmus (wie den Horspool -Algorithmus) mit den Stücken gegen die andere Zeichenfolge, Zählen der Anzahl der übereinstimmenden Teilstrings.
Wenn Sie Übereinstimmungen finden möchten, die nur ähnlich, aber nicht gleich sind, etwas in der Art einer lokalen Ausrichtung könnte besser geeignet sein, da es einen Score bietet, der die Ähnlichkeit beschreibt, aber der referenzierte Smith-Waterman-Algorithmus ist wahrscheinlich ein bisschen zu viel für Ihre Anwendung und nicht einmal der beste lokale Alignment-Algorithmus.
Abhängig von Ihrer Programmierumgebung besteht die Möglichkeit, dass eine Implementierung bereits verfügbar ist. Ich persönlich habe kürzlich mit SeqAn gearbeitet, das ist eine Bioinformatik-Bibliothek für C ++ und bietet definitiv die gewünschte Funktionalität.
Nun, das war eine ziemlich abstrakte Antwort, aber ich hoffe, dass es Sie in die richtige Richtung weist, aber leider bietet es Ihnen keine einfache Formel, um Ihr Problem zu lösen.
Ich glaube, Sie suchen Jaro-Winkler-Entfernung , die genau für die Namensanpassung ist.
>Sie können den Kompressionsabstand dafür nützlich finden. Siehe eine Antwort, die ich für eine sehr ähnliche Frage gegeben habe .
Oder Sie könnten ein k-Tuple basiertes Zählsystem verwenden:
Bei kleinen Alphabeten (z. B. DNA) würden Sie normalerweise einen Vektor beibehalten, der die Anzahl für jedes mögliche k-Tupel anstelle einer sortierten Liste speichert, obwohl das nicht praktisch ist, wenn das Alphabet überhaupt ein Zeichen ist - für k = 4, Sie würden ein 256 ^ 4-Array benötigen.
Eine der einfachsten und effektivsten modernen Alternativen zum Bearbeiten von Entfernungen ist der Normalized Compression Distance (NCD). Die Grundidee ist leicht zu erklären. Wählen Sie einen populären Komprimierer, der in Ihrer Sprache implementiert ist, z. B. zlib . Geben Sie dann bei gegebener Zeichenfolge A und Zeichenfolge B die C (A) die komprimierte Größe von A und
( C (AB) - min ( C (A) , C (B) )) / max ( C (A) , C (B) )
Dieser Wert wird als NCD ( A , B ) bezeichnet und ähnelt Ähnlichkeit zur Bearbeitungsentfernung, unterstützt jedoch mehr Formen der Ähnlichkeit, je nachdem, welchen Datenkompressor Sie auswählen. Natürlich unterstützt zlib die Ähnlichkeiten, die Sie beschreiben. Wenn zwei Strings ähnlich sind, wird die komprimierte Größe der Verkettung nahe der Größe jedes einzelnen sein, so dass der Zähler nahe 0 und das Ergebnis nahe 0 liegt. Wenn zwei Strings sehr unterschiedlich sind, entspricht die komprimierte Größe ungefähr der Summe von Die komprimierten Größen hinzugefügt und so das Ergebnis wird in der Nähe von 1. Diese Formel ist viel einfacher zu implementieren als die Entfernung bearbeiten oder fast jede andere explizite Zeichenfolge Ähnlichkeit messen, wenn Sie bereits Zugriff auf eine Datenkomprimierungsprogramm wie zlib haben. Dies liegt daran, dass die meisten "harten" Arbeiten wie Heuristik und Optimierung bereits im Bereich der Datenkomprimierung durchgeführt wurden und diese Formel extrahiert einfach die Menge ähnlicher Muster, die sie unter Verwendung der generischen Informationstheorie gefunden hat, die sprachunabhängig ist. Darüber hinaus ist diese Technik viel schneller als die meisten expliziten Ähnlichkeitsmaße (z. B. Bearbeitungsentfernung) für den von Ihnen beschriebenen Größenbereich von einigen hundert Byte. Für weitere Informationen zu dieser und einer Beispielimplementierung suchen Sie einfach nach Normalized Compression Distance (NCD) oder sehen Sie sich das folgende Papier- und GitHub-Projekt an:
Ссылка "Clustering durch Komprimierung"
Ссылка Implementierung der C-Sprache
Es gibt viele andere Implementierungen und Arbeiten zu diesem Thema in den letzten zehn Jahren, die Sie auch in anderen Sprachen und mit Modifikationen verwenden können.
Ich bin mir nicht sicher, ob das, was du wirklich willst, die Bearbeitungsdistanz ist - die einfach nach Zeichenketten funktioniert - oder die semantische Distanz - die passendste oder ähnliche Bedeutung wählend. Vielleicht möchten Sie sich die Themen in Information Retrieval ansehen, um Ideen zu finden, wie der am besten passende passende Ausdruck / Ausdruck ausgewählt werden kann ein bestimmter Begriff oder Ausdruck. In gewisser Weise vergleicht man also sehr kurze Dokumente und nicht Zeichenfolgen.
Tags und Links algorithm language-agnostic levenshtein-distance edit-distance