Es gibt zwei Herausforderungen:
A. Die parallele Ausführung der Levenstein-Distanz - anstelle einer sequentiellen Schleife
B. Die Anzahl der Vergleiche: Wenn unsere Quellenliste 4 Millionen Einträge hat, sollten wir theoretisch 16 Billionen Levenstein Distanzmaße laufen lassen, was unrealistisch ist, selbst wenn wir die erste Herausforderung lösen.
Um meinen Gebrauch der Sprache klar zu machen, hier sind unsere Definitionen
- Wir wollen die Levenstein-Distanz zwischen den Ausdrücken messen.
- Jeder Ausdruck hat zwei Abschnitte, den übergeordneten Namen A und den vollständigen Namen B, die durch ein Pluszeichen getrennt sind
- Die Reihenfolge der Abschnitte ist wichtig (dh zwei Ausdrücke (1, 2) sind identisch, wenn Parent A von Ausdruck 1 = Parent A von Ausdruck 2 und Parent B oder Ausdruck 1 = Parent B von Ausdruck 2 ist. Ausdrücke werden nicht berücksichtigt identisch, wenn Parent A von Ausdruck 1 = Parent B von Ausdruck 2 und Parent B von Ausdruck 1 = Parent A von Ausdruck 2)
- Ein Abschnitt (oder ein vollständiger Name) ist eine Reihe von Wörtern, die durch Leerzeichen oder Bindestriche getrennt sind und dem Vor- und Nachnamen einer Person entsprechen
- wir nehmen an, dass die maximale Anzahl von Wörtern in einem Abschnitt 6 ist (Ihr Beispiel hat Abschnitte von 2 oder 3 Wörtern, ich nehme an, dass wir bis zu 6 Wörter haben können) die Reihenfolge der Wörter in einem Abschnitt ist wichtig (der Abschnitt ist immer ein Vorname, gefolgt von einem Nachnamen und nie der Nachname zuerst, zum Beispiel Jack John und John Jack sind zwei verschiedene Personen).
- gibt es 4 Millionen Ausdrücke Es wird angenommen, dass
- Ausdrücke nur englische Zeichen enthalten. Zahlen, Leerzeichen, Satzzeichen, Bindestriche und andere nicht englische Zeichen können ignoriert werden.
- wir gehen davon aus, dass die einfachen Übereinstimmungen bereits erledigt sind (wie der exakte Ausdruck übereinstimmt) und wir nicht nach exakten Übereinstimmungen suchen müssen
Technisch besteht das Ziel darin, eine Reihe übereinstimmender Ausdrücke in der Liste der 4 Millionen Ausdrücke zu finden. Zwei Ausdrücke gelten als übereinstimmender Ausdruck, wenn ihr Levenstein-Abstand kleiner als 2 ist.
Praktisch erstellen wir zwei Listen, die genaue Kopien der ursprünglichen 4-Millionen-Liste von Ausdrücken sind. Wir rufen dann die linke Liste und die rechte Liste auf. Jedem Ausdruck wird vor dem Duplizieren der Liste eine Ausdrucks-ID zugewiesen. Unser Ziel ist es, Einträge in der rechten Liste zu finden, die einen Levenstein-Abstand von weniger als 2 zu Einträgen der linken Liste haben, mit Ausnahme des gleichen Eintrags (gleiche Ausdrucks-ID).
Ich schlage einen zweistufigen Ansatz vor, um die beiden Herausforderungen getrennt zu lösen. Der erste Schritt wird die Liste der möglichen übereinstimmenden Ausdrücke reduzieren, der zweite wird die Levenstein-Distanzmessung vereinfachen, da wir nur sehr enge Ausdrücke betrachten. Bei der verwendeten Technologie handelt es sich um einen herkömmlichen Datenbankserver, da die Datensätze für die Leistung indexiert werden müssen.
HERAUSFORDERUNG A
Die Herausforderung A besteht darin, die Anzahl der Entfernungsmessungen zu reduzieren. Wir starten von maximal ca. 16 Billionen (4 Millionen zur Macht von zwei) und wir sollten ein paar Zehn oder Hunderte von Millionen nicht überschreiten. Die hier zu verwendende Technik besteht darin, nach mindestens einem ähnlichen Wort im vollständigen Ausdruck zu suchen. Abhängig davon, wie die Daten verteilt werden, reduziert dies die Anzahl der möglichen passenden Paare dramatisch. Alternativ können wir, abhängig von der geforderten Genauigkeit des Ergebnisses, auch nach Paaren mit mindestens zwei ähnlichen Wörtern oder mit mindestens der Hälfte ähnlicher Wörter suchen.
Technisch schlage ich vor, die Ausdruckliste in eine Tabelle zu legen. Fügen Sie eine Identitätsspalte hinzu, um eine eindeutige ID pro Ausdruck zu erstellen, und erstellen Sie 12-Zeichen-Spalten. Parsen Sie dann die Ausdrücke und setzen Sie jedes Wort jedes Abschnitts in eine separate Spalte. Dies wird aussehen (ich habe nicht alle 12 Spalten dargestellt, aber die Idee ist unten):
%Vor%Es gibt leere Spalten (da es nur sehr wenige Ausdrücke mit 12 Wörtern gibt), aber das spielt keine Rolle.
Dann replizieren wir die Tabelle und erstellen einen Index für jede ... Spalte. Wir führen 12 Joins durch, die ähnliche Wörter suchen, etwa
%Vor%Wir sammeln die Ausgabe in 12 temporären Tabellen und führen eine Vereinigungsabfrage der 12 Tabellen durch, um eine kurze Liste aller Ausdrücke zu erhalten, die potentielle übereinstimmende Ausdrücke mit mindestens einem identischen Wort haben. Dies ist die Lösung für unsere Herausforderung A. Wir haben jetzt eine kurze Liste der wahrscheinlich passenden Paare. Diese Liste enthält Millionen von Datensätzen (Paare von linken und rechten Einträgen), aber keine Milliarden.
HERAUSFORDERUNG B
Das Ziel von Herausforderung B besteht darin, eine vereinfachte Levenstein-Distanz im Stapel zu verarbeiten (anstatt sie in einer Schleife auszuführen). Zuerst sollten wir uns einigen, was eine vereinfachte Levenstein-Distanz ist. Zuerst stimmen wir zu, dass die levenstein-Distanz zweier Ausdrücke die Summe der levenstein-Distanz aller Wörter der beiden Ausdrücke ist, die denselben Index haben.Ich meine die Levenstein-Distanz von zwei Ausdrücken ist die Entfernung ihrer zwei ersten Wörter plus der Abstand ihrer zwei zweiten Wörter usw. Zweitens müssen wir eine vereinfachte Levenstein-Distanz erfinden. Ich schlage vor, den N-Gramm-Ansatz mit nur zwei Gramm Zeichen zu verwenden, die einen absoluten Indexunterschied von weniger als 2 haben.
z.B. Der Abstand zwischen Peter und Pieter wird wie folgt berechnet:
%Vor%Peter und Pieter haben 4 gemeinsame 2-Gramm mit einer absoluten Indexdifferenz von weniger als 2 'et', 'te', 'er', 'r_'. Es gibt 6 mögliche 2-Gramm in der größten der beiden Wörter, die Entfernung ist dann 6-4 = 2 - Die Levenstein-Entfernung wäre auch 2, weil es eine Bewegung von 'eter' und eine Buchstabeneinfügung 'i' gibt.
Dies ist eine Annäherung, die nicht in allen Fällen funktionieren wird, aber ich denke, in unserer Situation wird es sehr gut funktionieren. Wenn wir mit der Qualität der Ergebnisse nicht zufrieden sind, können wir es mit 3 Gramm oder 4 Gramm versuchen oder einen Sequenzunterschied von mehr als 2 Gramm ermöglichen. Aber die Idee ist, viel weniger Berechnungen pro Paar durchzuführen als im traditionellen Levenstein-Algorithmus.
Dann müssen wir das in eine technische Lösung umwandeln. Was ich vorher gemacht habe, ist folgendes: Isoliere zuerst die Wörter: da wir nur die Entfernung zwischen den Wörtern messen müssen, und dann diese Abstände pro Ausdruck summieren, können wir die Anzahl der Berechnungen weiter reduzieren, indem wir eine bestimmte Auswahl auf der Wörterliste ausführen (wir haben bereits die Liste vorbereitet Wörter im vorherigen Abschnitt).
Dieser Ansatz erfordert eine Zuordnungstabelle, die die Ausdrucks-ID, die Abschnitts-ID, die Wort-ID und die Wortfolgenummer für das Wort verfolgt, so dass die ursprüngliche Ausdrucksdistanz am Ende des Prozesses berechnet werden kann.
Wir haben dann eine neue Liste, die viel kürzer ist und eine Kreuzverbindung aller Wörter enthält, für die das 2-Gramm-Abstandsmaß relevant ist. Dann wollen wir diese 2-Gramm-Distanzmessung im Batch-Verfahren verarbeiten, und ich schlage vor, dies in einem SQL-Join zu tun. Dies erfordert einen Vorverarbeitungsschritt, der darin besteht, eine neue temporäre Tabelle zu erstellen, die alle 2 Gramm in einer separaten Zeile speichert - und das Wort Id, die Wortfolge und den Abschnittstyp verfolgt
Dies geschieht technisch, indem man die Liste der Wörter mit einer Reihe (oder einer Schleife) der Teilzeichenfolge schneidet, wie folgt (unter der Annahme der Wortlistentabellen gibt es zwei Kopien, eine links und eine rechts - enthalten zwei Spalten word_id und Wort):
%Vor%Und dann
%Vor%usw.
Etwas, das "Steward" so aussehen lässt (angenommen, das Wort id ist 152)
%Vor%Vergessen Sie nicht, einen Index für die Spalten word_id, gram und gram_seq zu erstellen, und die Entfernung kann mit einem Join der linken und rechten Grammliste berechnet werden, wobei ON wie
aussieht %Vor%Die Entfernung ist die Länge des längsten der beiden Wörter minus der Anzahl der übereinstimmenden Gramm. SQL ist extrem schnell, eine solche Abfrage zu machen, und ich denke, ein einfacher Computer mit 8 Gigabyte RAM würde leicht mehrere hundert Millionen Zeilen in einem vernünftigen Zeitrahmen tun.
Und dann ist es nur eine Frage der Zuordnungstabelle, um die Summe der Wort-zu-Wort-Distanz in jedem Ausdruck zu berechnen, um den Gesamtausdruck zum Ausdruck zu bringen.