Partielle Namensübereinstimmung in Millionen von Datensätzen

10

Wir haben eine webbasierte Anwendung für den Namensabgleich entwickelt. Dabei werden Namen in Teile zerlegt, und der Soundex- Wert jedes Teils wird in einer Datenbank gespeichert. Die Levenshtein-Abstandsmetrik wird verwendet, um die prozentuale Anpassung des Tons sowie die Rechtschreibung für einen bestimmten Namen anzuwenden.

Zur Laufzeit laden wir alle Datensätze in den Speicher und wenden den Levenshtein-Abstand auf alle Soundex-Werte und die Schreibweise aller Teile aller Namen an.

Das hat anfangs gut funktioniert, weil es maximal 20.000 Namen gab, aber jetzt hat einer unserer Kunden 30 Millionen Namen. Das Laden dieser riesigen Liste in den Speicher für jede Anforderung und das Anwenden dieser Art des Abgleichs ist ein erbärmlicher Ansatz, der viel Speicher und Ausführungszeit benötigt.

Wir suchen nach Vorschlägen für die Suche in einer Datenbank mit 30 Millionen Datensätzen oder mehr in naher Zukunft mit prozentualer Übereinstimmung von Ton und Rechtschreibung.

Kernfunktionalität

Der Endbenutzer gibt den zu vergleichenden Namen und den Mindestprozentsatz ein. Wir sollen alle Namen in der Datenbank anzeigen, für die ein Teil des Namens mit einem Teil des angegebenen Namens bis zum angegebenen Prozentsatz übereinstimmt. Der vollständige Name muss nicht übereinstimmen. Jeder Teil, der bis zum Prozentsatz übereinstimmt, ist ein Erfolg. Zum Beispiel.

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Beide Teile beider Namen stimmen nicht genau überein, aber bis zu einem gewissen Grad nehmen wir 80% an. Wenn der Benutzer also 80% eingibt, muss der Name in der Datenbank als übereinstimmender Name angezeigt werden.

bjan
quelle
1
Verwenden Sie SQL Server? Ich sehe, Sie haben es asp.net markiert. Denken Sie an die Möglichkeit einer CLR-Assembly, die den Netzwerkverkehr verhindert und SQL Server den Speicher verwalten lässt.
RubberChickenLeader
@WindRaven wir verwenden sowohl SQL Server als auch Oracle
bjan
1
Ist dies nicht das gleiche Web-Crawler-Problem, das Google löst?
candied_orange
@bjan wo werden die Namen gespeichert? werden sie in SQL Server gespeichert?
RubberChickenLeader
Was suchst du? Die Top 100 Namen, die am besten zu einer bestimmten Abfrage passen?
Doc Brown

Antworten:

6

Ohne die vollständigen Details zu kennen, möchten Sie wahrscheinlich eine der folgenden Aktionen ausführen:

Ich weiß nicht genau, worum es bei der Installation und Konfiguration von Sphinx geht. Ich habe jedoch den Eindruck, dass Sie es auf eine Datenbank verweisen, angeben können, welche Felder indiziert werden sollen, wie die Ergebnisse gewichtet werden sollen, und dass Sie eine geordnete Liste übereinstimmender Datensätze erhalten.

Verwenden Sie für benutzerbezogene oder geschäftskritische Dinge ein vorhandenes Suchwerkzeug.

Wenn Sie sich nur akademisch fühlen ... Spielen Sie mit ngrams:

Eine ngrams-Nachschlagetabelle kann als erster Satz potenzieller Übereinstimmungen dienen, und Sie können Levenshtein-Abstände verwenden, um die Ergebnisse zu beschneiden und zu sortieren.

Angenommen, Sie möchten suchen people, können Sie Folgendes tun:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Sie können Ihre Ngramme entweder regelmäßig neu erstellen oder sie im laufenden Betrieb erstellen. In jedem Fall kann ein einfacher, naiver Suchalgorithmus folgendermaßen aussehen:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Ich habe etwas Ähnliches verwendet (aber mit etwas mehr ngram "Popularität" -Tuning, Blacklists, Whitelists usw.), und ich habe gesehen, wie diese Art von Algorithmus Datensätze zwischen Datensätzen in großen Mengen unscharf zusammenführt und die benutzerdefinierte Fuzzy-Suche erleichtert Dienstprogramme und laufende Bemühungen zur Deduplizierung von Aufzeichnungen.

In meinem Fall stimmte ich nicht mit Millionen von Datensätzen überein, sondern suchte nach den bestmöglichen Zusammenführungen zwischen zwei Datensätzen in der Größenordnung von jeweils Hunderttausenden von Datensätzen. Und wir wollten, dass es ziemlich schnell funktioniert - innerhalb weniger Minuten. (Schnell, was sind 100.000 * 100.000?) Und wir waren erfolgreich.

Mit der richtigen Abstimmung kann so etwas schnell und effektiv sein. Letztendlich konnten wir in wenigen Minuten ein zusammengeführtes Set auf einer bescheidenen, veralteten Dual-Core-Maschine erstellen, wobei "fragwürdige" Zusammenführungen automatisch zur manuellen Überprüfung markiert wurden. Es hat jedoch viel Zeit gekostet, den Sweet-Spot für die Popularität / Relevanz von Ngrams und die richtigen Schwellenwerte für den String-Abstand sowie Blacklists und Whitelists usw. zu finden.

DAS GESAGT , man kann wirklich in ein Loch gesaugt werden, wenn man an diesem Zeug arbeitet. Für alle realen Dinge auf Produktionsebene sollten Sie im Allgemeinen ein gut etabliertes Tool verwenden, das bereits für diese Art der Suche erstellt und optimiert wurde .

Wie Sphinx oder Lucene .

svidgen
quelle
Ich habe gerade im Sphinx 2.2.11-Referenzhandbuch nach Fuzzy gesucht und es sieht so aus, als würde es genau mit dem Wort übereinstimmen, während ich Wörter teilweise abgleichen muss. Korrigieren Sie mich, wenn ich falsch liege.
Bjan
@bjan Ja. Wenn Sie sich die Dokumente genauer ansehen, bin ich mir nicht sicher, ob die Fuzzy-Suche von Sphinx genau das ist, wonach Sie suchen. Es kann eine Soundex-Morphologie verwenden . Basierend auf Ihrer letzten Bearbeitung möchten Sie möglicherweise Ihre eigene Suche nach ngram + string-distance durchführen. Und wie ich oben sagte, kann es eine Weile dauern, bis der Algorithmus und die Schwellenwerte angepasst sind. aber es ist nicht unmöglich. Und wenn Sie dieses Maß an Flexibilität benötigen ...
svidgen
@bjan Oh, ich habe auch Lucene total vergessen . Ich bin mir nicht sicher, ob es das tut, was Sie brauchen. Aber es ist verdammt beliebt und einen Blick wert, bevor Sie Ihre eigenen rollen. In den Dokumenten von Lucene werden Fuzzy-Suchen und Rankings anhand des Levenshtein-String-Abstands erwähnt.
Svidgen