Ungefähre String-Matching

Question

Ich weiß, diese Frage wurde viel Zeit gefragt. Ich möchte einen Vorschlag, welcher Algorithmus für ungefähre String-Matching geeignet ist.

Die Anwendung ist nur für den Firmennamen passend und nichts anderes.

Die größte Herausforderung ist wahrscheinlich die Firma Ende Name Teil und kurze benannte Teil Beispiel: 1. companyA pty ltd vs companyA pty. GmbH. vs companyA 2. WES Engineering vs W. E. S. Ingenieurwesen (extrem seltenes Vorkommen)

Denkst du Levenshtein Edit Entfernung ist angemessen?

Ich bin mit C#

Grüße, Max

Answer 1

Es gibt verschiedene String-Distanz-Metriken, die Sie verwenden könnten.

Ich würde Jaro-Winkler empfehlen. Im Gegensatz zur Bearbeitungsdistanz, bei der das Ergebnis eines Vergleichs in einzelnen Bearbeitungseinheiten liegt, gibt Ihnen JW einen Wert von 0-1. Es ist besonders für Eigennamen geeignet. Schauen Sie auch bei this nice tutorial und this SO question.

Ich habe nicht mit C#, aber hier sind einige Implementierungen von JW Ich fand online zu verarbeiten:

Impl 1 (Sie haben eine DOT NET-Version auch, wenn Sie in der Dateiliste sehen)

Impl 2

---

Wenn Sie ein bisschen anspruchsvoller passende tun möchten, können Sie versuchen, einige benutzerdefinierte Normalisierung der Wortformen häufig in Firmennamen auftreten, zu tun wie ltd/limited, inc/incorporated, corp/corporation für Groß- und Kleinschreibung, Abkürzungen usw. Auf diese Weise erklären, wenn Sie

distance (normalize("foo corp."), normalize("FOO CORPORATION"))

Sie das Ergebnis 0 sein sollte erhalten berechnen, anstatt 14 (das, was Sie, wenn Sie erhalten würden ist berechnete Levenshtein-Bearbeitungsdistanz).

Answer 2

Ja, Levenshtein-Distanz für diese geeignet ist. Es funktioniert für alle, die Sie mindestens aufgelistet haben. Sie können auch Soundex verwenden, aber ich glaube nicht, dass Sie es brauchen.

Answer 3

In diesen einfachen Beispielen können Sie nur alle nicht-alphanumerischen Zeichen entfernen, um eine Übereinstimmung zu erzielen. Dies ist am einfachsten, da Sie die Daten auf jeder Seite vorberechnen können viel schneller als Cross-Multiplikation und Berechnung der Bearbeitungsdistanz.

Answer 4

Ich habe meine Antwort bereits in einer anderen Frage zur Verfügung gestellt.

https://stackoverflow.com/a/30120166/2282794

Ich habe auf wirklich großen Maßstab System mit ähnlichen Namen passenden Anforderungen gearbeitet, die Sie gesprochen haben. Namensabgleich ist nicht sehr einfach und die Reihenfolge der Vor- und Nachnamen kann unterschiedlich sein. Einfache Fuzzy-Namensvergleichsalgorithmen scheitern in solchen Szenarien kläglich.

Wenn wir nur über die Approximate String Matching-Algorithmen sprechen wollen, dann gibt es viele. Wenige von ihnen sind: Jaro-Winkler, Edit Entfernung (Levenshtein), Jaccard Ähnlichkeit, Soundex/Phonetik basierte Algorithmen etc. Ein einfaches googeln würde uns alle Details geben. Sie können alle von ihnen in C#

implementieren Ironie ist, sie arbeiten, während Sie versuchen, zwei gegebenen Eingabezeichenfolgen übereinstimmen. Okay, theoretisch und um die Art und Weise zu demonstrieren funktioniert fuzzy oder approximative String-Matching.

Aber grob untertriebener Punkt ist, wie wir das gleiche in Produktionseinstellungen verwenden. Nicht alle, die ich kenne, die nach einem ungefähren String-Matching-Algorithmus suchten, wussten, wie sie dasselbe in der Produktionsumgebung lösen konnten.

Ich könnte gerade über Lucene gesprochen haben, die spezifisch für Java ist, aber es gibt auch Lucene für .Net.

https://lucenenet.apache.org/