Effiziente Weise Ähnlichkeit Noten von Strings der Berechnung, wenn die Probengröße groß ist?

StackOverflow https://stackoverflow.com/questions/1609742

Frage

Nehmen wir an, dass Sie eine Liste von 10.000 E-Mail-Adressen haben, und Sie möchten, was einige der am nächsten „Nachbarn“ finden in dieser Liste - wie E-Mail-Adressen definiert, die verdächtig nahe an andere E-Mail-Adressen in Ihrer Liste .

Ich bin mir dessen bewusst, wie die Levenshtein Abstand zwischen zwei Strings (dank diese Frage ), die mir geben eine Punktzahl von, wie viele Operationen nötig sind, um eine Zeichenfolge in eine andere zu überführen.

Lassen Sie uns sagen, dass ich „verdächtig nahe an eine andere E-Mail-Adresse“ definieren als zwei Saiten eine Levenshtein mit Score von weniger als N.

Gibt es eine effizientere Art und Weise Saitenpaaren, deren Partitur zu finden ist unter dieser Schwelle außer in der Liste alle möglichen String in jeder anderen möglichen Zeichenfolge zu vergleichen? Mit anderen Worten, kann diese Art von Problem schneller als O(n^2) gelöst werden?

Ist Levenshtein eine schlechte Wahl von Algorithmen für dieses Problem punkten?

War es hilfreich?

Lösung

Yup - Sie alle Strings in einem bestimmten Abstand von einer Zeichenkette in O (log n) Zeit unter Verwendung eines BK-Baum . Alternative Lösungen mit jeder Zeichenfolge mit Abstand n Erzeugung können schneller für einen levenshtein Abstand von 1, aber die Menge an Arbeit Ballons schnell außer Kontrolle für längere Distanzen.

Andere Tipps

Sie können es mit Levenshtein in O(kl) tun, wo k Ihre maximale Entfernung ist und l ist die maximale Zeichenfolge.

Im Grunde genommen, wenn Sie wissen, wie grundlegenden Levenshtein zu berechnen, dann ist es einfach, herauszufinden, dass jedes Ergebnis, das als k von der Hauptdiagonale weiter ist, hat als k größer sein. Also, wenn Sie Hauptdiagonale mit einer Breite 2k + 1 Berechnung genügt.

Wenn Sie 10000 E-Mail-Adressen haben, werden Sie nicht einen schnelleren Algorithmus benötigen. Computer kann schnell genug mit O(N^2) berechnen.

Levenshtein ist recht gut für diese Art von Problem.

Auch was Sie vielleicht prüfen, ist E-Mails mit soundex Transformation vor dem Vergleich. Sie werden wahrscheinlich bessere Ergebnisse erzielen.

Dieses Problem ist bekannt als Clustering und ist ein Teil einer größeren Deduplizierung Problem (wo Sie entscheiden, erhalten, welches Mitglied des Clusters ist die „richtige“ ist) , die auch als bekannt fusionieren-Säuberung .

Ich lese einmal ein paar wissenschaftliche Arbeit zu genau diesem Thema (die Namen sind weiter unten) und im Grunde verwendeten die Autoren eine begrenzte Größe Schiebefenster über eine sortierte Liste von Strings. Sie würden nur vergleichen (mit einem Editierdistanz Algorithmus) N * N Strings innerhalb von das Fenster, wodurch die Rechenkomplexität zu reduzieren. Wenn zwei Saiten ähnlich sahen, wurden sie in ein Cluster kombiniert (durch einen Datensatz in eine separate Cluster-Tabelle eingefügt werden).

Der erste Durchlauf durch die Liste wurde gefolgt von einem zweiten Durchgang , wo die Saiten waren umgekehrt , bevor sortiert zu werden. Auf diese Weise die Saiten mit verschiedenen Köpfen hatte noch eine Chance zu nahe kommt genug, um als Teil des gleichen Fensters ausgewertet werden. Auf diesem zweiten Durchgang, wenn ein String nahe genug, um zwei sah (oder mehr) Zeichenkette in dem Fenster, und die Saiten waren bereits Teile ihrer eigenen Cluster (nach dem ersten Durchgang gefunden), würden die beiden Cluster dann verschmolzen (durch die Cluster-Tabelle zu aktualisieren) und die aktuelle Zeichenfolge würde den fusionierten Cluster hinzugefügt werden. Dieser Cluster-Ansatz ist bekannt als der Vereinigungs-Suche Algorithmus.

Dann verbesserte sie den Algorithmus durch das Fenster mit einer Liste der Top-X im Wesentlichen einzigartiger Prototypen ersetzen . Jede neue Zeichenfolge würde auf jeden der oberen X-Prototypen verglichen werden. Wenn Zeichenfolge nahe genug aussieht, um einen der Prototypen, wäre es dann auf die Prototyp-Cluster hinzugefügt werden . Wenn keiner der Prototypen ähnlich genug aussieht, würden die Zeichenfolge ein neuer Prototyp, den ältesten Prototyps Ausschieben der oberen X-Liste. (Es gab eine heuristische Logik, welche der Strings in der Prototyp des Clusters, zu entscheiden, verwendet wird, sollte als neuer Prototyp des gesamten Clusters darstellt, verwendet werden). Auch wenn die Zeichenfolge auf mehrere Prototypen ähnlich sehen, würden alle ihre Cluster zusammengefasst.

ich einmal diesen Algorithmus für die Deduplizierung von Name / Adresse Datensätze mit Größen der Listen 10-50 Millionen Datensätze sind implementiert und es funktionierte ziemlich verdammt schnell (und Duplikate gut zu finden).

Insgesamt für solche Probleme ist der schwierigste Teil natürlich Suche nach dem richtigen Wert der Ähnlichkeitsschwelle . Die Idee ist es, alle dups zu erfassen w / o zu viele Fehlalarme produzieren . Daten mit unterschiedlichen Eigenschaften tendenziell unterschiedliche Schwellenwerte zu verlangen. Die Wahl eines Edit-Distanz-Algorithmus ist auch wichtig, da einige Algorithmen für OCR-Fehler besser sind, während andere besser für Tippfehler und noch andere sind besser für Laut Fehlern (wie zum Beispiel, wenn Sie einen Namen über das Telefon bekommen).

Wenn der Cluster-Algorithmus implementiert ist, ein guter Weg, es zu testen, ist eine Liste der einzigartigen Proben und künstlich jede Probe mutieren seine Variationen zu erzeugen, während die Tatsache zu bewahren, dass alle Variationen haben aus demselben Elternteil. Diese Liste wird dann gemischt und den Algorithmus zugeführt. das Original-Clustering mit dem durch die Deduplizierung Algorithmus erzeugt Clustering Beim Vergleich werden Sie die Effizienz-Score .

Bibliographie:

Hernandez M. 1995 Die Zusammenführung / Bereinigung Problem für große Datenbanken.

Monge A. 1997 Ein effizienter Domain-unabhängiger Algorithmus für etwa doppelte Datenbankdatensätze zu erkennen.

Ich glaube nicht, Sie können als O besser (n ^ 2), aber man kann einige kleinere Optimierungen tun, die gerade genug, um von einer Beschleunigung könnte Ihre Anwendung nutzbar zu machen:

  • Sie könnten zuerst sortieren alle E-Mail-Adressen von ten Teil nach dem @ und nur Adressen vergleichen, wo, dass das gleiche
    • ist
  • Sie können aufhören, den Abstand zwischen zwei Adressen berechnet wird, wenn es größer als n wird

EDIT:. Eigentlich kann man es besser machen als O (n ^ 2), nur Blick auf Nick Johnsons Antwort unten

10.000 E-Mail-Adressen klingen nicht zu viel. Für Ähnlichkeitssuche in einem größeren Raum können Sie Schindeln und min-Hashing . Dieser Algorithmus ist ein wenig komplizierter zu implementieren, aber ist viel effizienter auf einem großen Raum.

Es ist möglich, es besser zu machen, unter der Bedingung, das Problem der Umkehrung.

Ich nehme hier, dass Ihre 10.000 Adressen ziemlich ‚fixiert‘ werden, sonst müssen Sie ein Update-Mechanismus hinzuzufügen.

Die Idee ist es, die Levenshtein-Distanz zu verwenden, aber in 'Reverse' Modus, in Python: 

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

Die generate_level Verfahren erzeugt alle möglichen Variationen von der Vorherigen, minus die Variationen, die bereits auf einer früheren Ebene existieren. Es bewahrt die ‚Herkunft‘ als Wert zum Schlüssel zugeordnet ist.

Dann Sie nur Ihr Wort in den verschiedenen Set-Lookup müssen: 

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

Dabei berechnen Sie die einmal verschiedene Sets (es einige Male nimmt ... aber dann kann man es serialisiert und halten sie für immer).

Und dann Lookup ist viel effizienter als O (n ^ 2), obwohl es genau geben etwas schwierig ist, da sie von der Größe der Sätze ab, die erzeugt werden.

Als Referenz hat einen Blick auf: http://norvig.com/spell-correct.html

Angenommen, Sie haben drei Strings:

1 - "abc" 2 - "bcd" 3 - "cde"

Der L Abstand zwischen der 1 & 2 2 (subtrahieren 'a', fügen Sie 'd'). Der L Abstand zwischen 2 und 3 ist 2 (subtrahieren 'b', fügen Sie 'e').

Ihre Frage ist, ob wir einen L Abstand zwischen 1 und 3 unter Verwendung der 2 Vergleiche oben ableiten können. Die Antwort ist nein.

Der L Abstand zwischen 1 und 3 ist 3 (ersetzen jedes Zeichen), gibt es keine Möglichkeit, dass dies wegen der Punkte der ersten 2 Berechnungen abgeleitet werden kann. Die Noten zeigen nicht, ob Deletionen, Insertionen oder Substitutionsoperationen durchgeführt wurden.

Also, ich würde sagen, dass Levenshtein eine schlechte Wahl für eine große Liste ist.

Wenn Sie wirklich vergleichen E-Mail-Adressen dann eine offensichtliche Art und Weise, dies zu tun wäre, einen levenshtein Algorithmus mit Domain-Mapping zu kombinieren. Ich kann Mal denken, wenn ich mehrere Male für etwas die gleiche Domain verwenden, aber Variationen auf den Benutzernamen Teil der E-Mail-Adresse.

angemeldet haben
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top