Welchen Algorithmus würden Sie am besten für die String-Ähnlichkeit verwenden?

Ich entwerfe ein Plugin, um Inhalte auf verschiedenen Webseiten anhand von Adressen eindeutig zu identifizieren.

Ich kann also eine Adresse haben, die so aussieht:

1 someawesome street, anytown, F100 211

später kann ich diese Adresse in einem etwas anderen Format finden.

1 someawesome street, F100 211,

oder vielleicht so vage wie

someawesome street F100

Dies sind technisch gesehen die gleichen Adressen, jedoch mit einem gewissen Grad an Ähnlichkeit. Ich möchte a) eine eindeutige Kennung für jede Adresse generieren, um Suchvorgänge durchzuführen, und b) herausfinden, wann eine sehr ähnliche Adresse auftaucht.

Welche Algorithmen / Techniken / String-Metriken sollte ich mir ansehen? Levenshtein Abstand scheint eine naheliegende Wahl, aber neugierig, ob es andere Ansätze gibt, die sich hier anbieten würden.

Der Algorithmus von Levenstein basiert auf der Anzahl der Einfügungen, Löschungen und Ersetzungen in Zeichenfolgen.

Leider wird ein häufiger Rechtschreibfehler nicht berücksichtigt, der die Umsetzung von 2 Zeichen ist (z. B. Someawesome vs Someaewsome). Daher würde ich den robusteren Damerau-Levenstein-Algorithmus vorziehen .

Ich halte es nicht für eine gute Idee, den Abstand auf ganze Saiten anzuwenden, da die Zeit mit der Länge der verglichenen Saiten abrupt zunimmt. Aber noch schlimmer, wenn Adresskomponenten wie ZIP entfernt werden, stimmen möglicherweise ganz andere Adressen besser überein (gemessen mit dem Online-Levenshtein-Rechner ):

1 someawesome street, anytown, F100 211       (reference) 
1 someawesome st.,anytown                     (difference of 15, same address)     
1 otherplaces street,anytown,F100211          (difference of 13, different ddress) 
1 sameawesome street, othertown, CA98200      (difference of 13, different ddress)
anytown, 1 someawesome street                 (28 different same address)
anytown, F100 211, 1 someawesome street       (37 different same address)

Diese Effekte verschlechtern sich bei kürzeren Straßennamen.

Verwenden Sie daher besser intelligentere Algorithmen. Zum Beispiel hat Arthur Ratz auf CodeProject einen Algorithmus für den Vergleich intelligenter Texte veröffentlicht. Der Algorithmus gibt keinen Abstand aus (er kann durchaus entsprechend angereichert werden), identifiziert jedoch einige schwierige Dinge wie das Verschieben von Textblöcken (z. B. den Wechsel zwischen Stadt und Straße zwischen meinem ersten und meinem letzten Beispiel).

Wenn ein solcher Algorithmus für Ihren Fall zu allgemein ist, sollten Sie wirklich nach Komponenten arbeiten und nur vergleichbare Komponenten vergleichen. Dies ist keine einfache Sache, wenn Sie ein Adressformat auf der ganzen Welt analysieren möchten. Aber wenn das Ziel spezifischer ist, sagen wir mal US, ist es mit Sicherheit machbar. Zum Beispiel könnten "Straße", "Str.", "Ort", "Platz" und ihre üblichen Rechtschreibfehler den Straßenteil der Adresse enthüllen, dessen führender Teil im Prinzip die Nummer wäre. Die Postleitzahl würde helfen, die Stadt zu finden, oder alternativ ist es wahrscheinlich das letzte Element der Adresse, oder wenn Sie nicht raten möchten, könnten Sie nach einer Liste von Städtenamen suchen (z. B. Herunterladen einer kostenlosen Postleitzahl-Datenbank). Sie können dann Damerau-Levenshtein nur auf die relevanten Komponenten auftragen.

Levenshtein Abstand ist besser für Worte

Wenn Wörter (hauptsächlich) richtig geschrieben sind, schauen Sie sich die Worttüte an . Ich mag wie über töten scheinen, aber TF-IDF und Cosinus Ähnlichkeit .

Oder du könntest freie Lucene benutzen. Ich denke, sie haben Cosinus-Ähnlichkeit.

Erstens müssten Sie die Webseite nach Adressen durchsuchen. RegEx ist ein Programm, das man sich nehmen muss. Es kann jedoch sehr schwierig sein, Adressen mit RegEx zu analysieren. Am Ende müssten Sie wahrscheinlich eine Liste potenzieller Adressierungsformate und eines oder mehrerer Ausdrücke durchgehen, die diesen entsprechen. Ich bin mit dem Parsen von Adressen nicht allzu vertraut, empfehle jedoch einen Blick auf diese Frage, die einer ähnlichen Überlegung folgt: General Address Parser for Freeform Text.

Levenshtein Abstand ist nützlich, aber nur, nachdem Sie die Adresse in seine Teile getrennt haben. Betrachten Sie die folgenden Adressen. 123 someawesome st.und 124 someawesome st.Diese Adressen sind völlig unterschiedliche Orte, aber ihre Levenshtein-Entfernung beträgt nur 1. Dies kann auch auf so etwas wie 8th st.und angewendet werden. 9th st.Ähnliche Straßennamen erscheinen normalerweise nicht auf derselben Webseite, aber es ist nicht ungewöhnlich. Auf der Webseite einer Schule kann beispielsweise die Adresse der Bibliothek auf der anderen Straßenseite oder die Adresse der Kirche ein paar Blocks weiter angegeben sein. Dies bedeutet, dass die einzigen Daten, für die die Levenshtein-Entfernung leicht verwendbar ist, die Entfernung zwischen 2 Datenpunkten sind, z. B. die Entfernung zwischen der Straße und der Stadt.

Wenn wir die Adressen selbst erhalten, ist es ziemlich einfach, herauszufinden, wie die verschiedenen Felder zu trennen sind. Zum Glück gibt es die meisten Adressen in sehr spezifischen Formaten. Mit etwas RegEx-Know-how sollte es möglich sein, sie in verschiedene Datenfelder zu unterteilen. Auch wenn die Adresse nicht gut formatiert ist, gibt es immer noch Hoffnung. Adressen folgen immer (fast) der Größenordnung. Ihre Adresse sollte sich in einem linearen Raster wie diesem befinden, je nachdem, wie viele Informationen bereitgestellt werden und wie diese lauten:

StreetNumber < Street < City < State < Country

Es kommt selten vor, dass die Adresse von einem Feld in ein nicht benachbartes Feld springt. Sie werden nicht sehr oft eine Straße, dann ein Land oder eine Straßennummer, dann eine Stadt sehen.

Sie fragen nach Ähnlichkeitsalgorithmen für Zeichenfolgen, Ihre Zeichenfolgen sind jedoch Adressen. Ich würde die Adressen an eine Standort-API wie Google Place Search senden und die formatted_addressals Vergleichspunkt verwenden. Das scheint der genaueste Ansatz zu sein.

Bei Adresszeichenfolgen, die nicht über eine API gefunden werden können, kann auf Ähnlichkeitsalgorithmen zurückgegriffen werden.

Ein cooler Algorithmus, der nützlich ist, aber eine voreingestellte Datenbank mit vorherigen Antworten erfordert, heißt: Zeilenbearbeitungsabstand.

Der Zeilenbearbeitungsabstand kann als eine Funktion "wie unterschiedlich sind diese zwei Wörter" zurückgeben.

Ein Wort wie "Dogma" und "Hund" ergibt den Wert 3 (für 3 zusätzliche Zeichen).

Oder "cat" und "hat" geben den Wert 1 zurück (für ein anderes Zeichen).

(Quelle: https://en.wikipedia.org/wiki/Edit_distance )

In der Tat scheint die Verwendung einer Distanzfunktion ein guter Ansatz zu sein. Aber das Problem ist dann, die nächste Zeichenkette von einer gegebenen Adresse zu finden, was alles andere als trivial ist.

Sie beschreiben hier eine breite Kategorie von Algorithmen. Schauen Sie sich die Suche nach dem nächsten Nachbarn an

Wie in einem Kommentar erwähnt, erleichtert dies die Aufgabe erheblich, wenn Sie eine Möglichkeit finden, die Adressbestandteile (Straßenname, Hausnummer usw.) zu trennen.

LongestCommonSubsequence (aus Apache Commons-Text) kann ein anderer Ansatz sein, um es mit Adressen zu versuchen. Wenn Sie die Ähnlichkeit von zwei als Verhältnis von " gemeinsamer Teilsequenzlänge / max (Adresslängen) " definieren, können Sie einen Toleranzschwellenwert anwenden - z. B. 0,8, der Übereinstimmung / keine Übereinstimmung definiert. Auf diese Weise können Sie Adressen wie " 1 someawesome st., Anytown " und " 1 someawesome street., Anytown " abgleichen .

Da es sich nicht um einen superschnellen Algorithmus handelt, möchten Sie möglicherweise schnelle Failbacks anwenden, um Vergleiche zu minimieren. Beispiel: - Vermeiden Sie den Vergleich, wenn die Postleitzahlen nicht übereinstimmen oder die Reihenfolge der extrahierten Ziffern unterschiedlich ist.