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

23

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.

Squiggs.
quelle
"Levenshtein distance" ist kein Algorithmus.
gnasher729
Wenn Sie keine grundlegende Analyse einführen, wird die rohe Levenstein-Distanz nicht so schön sein. Sie sollten versuchen, zumindest Wörter zu identifizieren, die Straße, Ortsnamen usw. und Straßennummern oder Postleitzahlen sein können. Dann wenden Sie vielleicht Levenstein mit einem statistischen Fuzzy-Matcher an, der von echten Orten / Straßennamen gespeist wird. Keine leichte Sache :)
7
@gnasher: Aber eine Funktion, die die Levenshtein-Distanz berechnet, ist ein Algorithmus. Ohne eine solche Funktion ist die Levenshtein-Distanz nur eine intellektuelle Neugier.
Robert Harvey
Ich habe hier eine sehr praktische Erklärung mit Beispielen gefunden: den Vergleich von Algortihms . Zusammenfassend empfehlen sie die Verwendung der Jaro-Winkler- Ähnlichkeit, da der Algorithmus von Levenstein von der Länge der Zeichenfolge abhängt. Ein Vergleich ist daher nicht sinnvoll.
Sandra Meneses

Antworten:

14

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.

Christophe
quelle
Was ist mit dem Sortieren beider Vergleichszeichenfolgen vor dem Vergleich? Ich habe festgestellt, dass dies bei der Umsetzung helfen kann.
openwonk
2

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.

Paparazzo
quelle
1

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.

Ucenna
quelle
2
Abgesehen davon, dass Straßenadressen nicht regulär sind und nicht zuverlässig durch reguläre Ausdrücke analysiert werden können. Sie können sicherlich nicht genau identifiziert werden, wenn sie nur in Freitext eingebettet sind. Sie können natürlich ein paar verschiedene reguläre Ausdrücke schreiben, um sie verschiedenen gängigen Formaten anzupassen, wenn Sie bereits wissen, wo Sie suchen.
Nutzlos
@Useless Das stimmt. Theoretisch ist das machbar, aber ich habe den Arbeitsaufwand unterschätzt. Vor allem, wenn möglicherweise bessere Optionen verfügbar sind. Ich habe meine Antwort geändert, um dies widerzuspiegeln.
Ucenna
1

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.

Dan Wilson
quelle
1
+1 Lagern Sie es aus, damit Sie die Macht von Experten haben, die Arbeit für Sie zu erledigen. Muss nicht Google sein, da es einige Dienstleister gibt. Verschwenden Sie nicht Ihre Zeit damit, es sei denn, der Adressabgleich ist Ihr Kerngeschäft.
LoztInSpace
0

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 )

John Greene
quelle
2
Was ist der Vorteil gegenüber OPs erwähntem Levensthtein?
Christophe
-1

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.

kjaquier
quelle
-1

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.

Altair7852
quelle