Levenshtein Entfernung/String-Matching-Algorithmus für Phrasen

Question

Ich habe zwei Tabellen, die jeweils Informationen geben über eine Reihe von Anwendungen, die auf meiner Arbeit Netzwerk ausgeführt werden. Sie wurden von zwei verschiedenen Personen geschaffen, die niemals zu korrespondieren schienen.

Als Ergebnis werden die Namen sie die Anwendungen gegeben haben, sind zwischen den Blättern nicht konstant. Sie sind jedoch ähnlich. Zum Beispiel könnte man eine Anwendung „Office 2010“, die andere „MS Office 10“ oder so nennen.

Ich habe den Levenshtein Algorithmus nachgeschlagen, aber dies scheint nur auf einzelne Wörter oder Sätze anzuwenden, wo das Wort, um konstant ist und nur die Schreibweise abweicht. (Ich bin kein Informatiker; fühlen Sie sich frei, mich diesbezüglich zu korrigieren).

Deshalb suche ich einen Algorithmus, der in einem Blatt für jeden Namen, kann in dem anderen Blatt alle Namen durchlaufen und die beste Übereinstimmung finden. Muss nicht perfekt sein, irgendetwas wird helfen.

Irgendwelche Ideen? Danke an alle, die mithelfen können.

Answer 1

Die Levenshtein-Distanz ist eine verallgemeinerte Form der Bearbeitungsdistanz, die die Anzahl der Bearbeitungen - Einfügungen, Löschungen und Ersetzungen - zählt, um eine Zeichenfolge in eine andere umzuwandeln. Du hast Recht, dass es nicht Umstellungen umgehen können sehr gut, aber je nach Bedarf kann es immer noch die Arbeit machen.

Fuzzy-String-Matching ist ein heuristischer Bereich, also ist es am besten zu spielen, um zu versuchen, Ihre spezifischen Ziele zu erreichen. Zum Beispiel könnten Sie versuchen, den Text vorläufig zu bearbeiten, indem Sie ihn falten und dann die Token lexikografisch sortieren, bevor Sie die Bearbeitungsdistanz nehmen, was in vielen Fällen bei den Transpositionen helfen würde. Sie können auch den absoluten Unterschied in der Länge zwischen den zwei Strings subtrahieren, so dass Sie einen geringen Abstand erhalten, wenn eine Zeichenfolge eine ungefähre Teilzeichenfolge der anderen ist - seien Sie jedoch vorsichtig, als ob Sie die leere Zeichenfolge zu allem passt.

Im Allgemeinen haben Sie immer einen Kompromiss zwischen Spezifität und Empfindlichkeit, also besteht der Trick einfach darin, die Heuristik so abzustimmen, dass sie so funktioniert, dass Sie sich wohl fühlen.