Guter Algorithmus, um alle Zeichenfolgenpaare zwischen 2 Sätzen zu finden, sodass alle Wörter aus der 1. Zeichenfolge alle in der 2. Zeichenfolge enthalten sind?

Question

Ich habe 2 große Sätze von Zeichenfolgen (eigentlich sind es Produktnamen)."Groß" bedeutet einige Millionen Saiten.

Beispiel:

Satz 1:

Some good product
Another product
Some name
Blah

Satz 2:

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

Set 1 enthält "gute" Namen.Satz 2 enthält "schmutzige" Namen.

Ich will: für jeden Artikel aus Set 2 (weiter:item2) finde den längsten Gegenstand aus Set 1 (weiter:item1), so dass alle Wörter aus item1 in item2 enthalten sind.

Für das gegebene Beispiel sind die Paare die folgenden:

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah

Bisher konnte ich mir nichts Besseres vorstellen als einen Brute-Force-Algorithmus:

1. Teilen Sie jede Zeichenfolge aus Satz 1 in Wörter auf = wir erhalten eine Reihe von Wortlisten, lassen Sie sie 3 setzen
2. Teilen Sie jede Zeichenfolge aus Satz 2 in Wörter auf = wir erhalten eine Reihe von Wortlisten, lassen Sie sie auf 4 setzen
3. Nimm eine Liste von Wörtern aus Satz 3 (weiter:liste3), vergleichen Sie es mit allen Wortlisten aus Satz 4, bis Sie eine Liste gefunden haben, die vollständig in der Liste 3 enthalten ist.

Es hat jedoch eine ziemlich hohe Komplexität und arbeitet ziemlich langsam.Meine einfache Implementierung dauert ungefähr 1,8 Sekunden, um 1 Paar zu finden (Satz 1 enthält 3 Millionen Elemente, Satz 2 enthält 4 Millionen Elemente).Wenn ich dieselbe Aufgabe mit MySQL-Volltextindizes implementiere (es ermöglicht die Suche nach Zeichenfolgen, die alle angegebenen Wörter enthalten), dauert 1 Suche ungefähr 0,4 Sekunden.Ich frage mich also, ob es einige gute Ansätze gibt, die hier mit kleinem Blut angewendet werden könnten :)

Meine Programmiersprache ist PHP7.Die Daten werden in MySQL DB gespeichert.

Answer 1

Ich werde zwei mögliche Ansätze auflisten, die in der Praxis einigermaßen effektiv sein könnten, obwohl ihre Worst-Case-Laufzeit nicht besser ist als die von Ihnen aufgeführte.

Index

Sie können für jedes Wort einen Index erstellen.Erstellen Sie eine Hash-Tabelle.Für jedes Wort, das in einem sauberen Namen vorkommt, ordnet die Hashtabelle dieses Wort einer Liste aller schmutzigen Namen zu, die dieses Wort enthalten.Diese Hashtabelle kann einmal in einem linearen Scan der Menge der schmutzigen Namen (Set2) aufgebaut werden.

Durchlaufen Sie dann bei einem sauberen Namen die Wörter im sauberen Namen.Suchen Sie für jedes Wort in der Hash-Tabelle nach, durchlaufen Sie alle schmutzigen Namen, die dieses Wort enthalten, und überprüfen Sie, wie viele Wörter es mit dem sauberen Namen gemeinsam hat.Behalte die beste Übereinstimmung.

Dies kann etwas optimiert werden.Wenn der saubere Name ein Wort enthält, das in vielen schmutzigen Namen vorkommt, ist die Verarbeitung dieses Wortes langsam.Sie könnten also herausfinden, wie oft jedes Wort in einem schmutzigen Namen vorkommt (seine Häufigkeit) und dies in einer Hash-Tabelle speichern.Bei einem sauberen Namen könnten Sie dann die Wörter im sauberen Namen in der Reihenfolge zunehmender Häufigkeit durchlaufen und die beste Übereinstimmung verfolgen, die Sie bisher gefunden haben.Wenn Sie eine Übereinstimmung der Länge gefunden haben $\ell$, dann können Sie die Iteration vorzeitig stoppen, ohne zu iterieren $\ell-1$ wörter mit der höchsten Häufigkeit im sauberen Namen, ohne dass gültige Übereinstimmungen fehlen.

Versuchen

Die Reihenfolge der Wörter in einem Namen ist irrelevant, also sortieren Sie die Wörter in jeder Phrase.Zum Beispiel wird 'ein gutes Produkt' zu 'ein gutes Produkt'.Tun Sie dies für jeden Namen in jedem Satz.

Erstellen Sie als Nächstes einen Versuch, um die Menge der guten Namen (Set1) darzustellen.Zum Beispiel wird in Ihrem Beispiel der Versuch sein

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

Wähle jetzt einen schmutzigen Namen.Wir wollen vom Trie eine Übereinstimmung dafür finden.Ich schlage vor, Sie verwenden einen rekursiven Algorithmus, um alle Übereinstimmungen zu finden:so finden Sie eine Übereinstimmung für den Namen $w_1 \punkte w_n$ im trie $T$, überprüfen Sie, ob es eine Kante aus der Wurzel von gibt $T$ etikettiert $w_1$, und wenn ja, finden Sie rekursiv alle Übereinstimmungen für $w_2 \punkte w_n$ in der Subtrie, auf die diese Kante zeigt;finden Sie auch rekursiv alle Übereinstimmungen für $w_2 \punkte w_n$ in $T$.Wenn Sie alle Übereinstimmungen gefunden haben, behalten Sie die längste.

Zum Beispiel für 'ein anderer sehr langer Produktname', nach dem Sortieren wird dies zu 'ein anderer langer Name Produkt sehr'.Sie suchen das im Versuch nach, indem Sie rekursiv alle Übereinstimmungen für 'Langnamensprodukt sehr' im Unterteil finden +-- product --+, und indem Sie alle Übereinstimmungen für 'long name product very' im Hauptversuch finden.

Dieser Suchprozess kann auf verschiedene Arten optimiert werden, z. B. indem die längste bisher gefundene Übereinstimmung verfolgt und frühzeitig gestoppt wird, wenn der rekursive Aufruf keine Möglichkeit hat, eine längere Übereinstimmung zu finden, basierend darauf, wie viele Wörter Sie bisher gefunden haben und wie viele Wörter verbleiben.

Es ist nicht erforderlich, nach lexikografischer Reihenfolge zu sortieren.Sie können in jeder anderen Reihenfolge sortieren, solange diese konsistent ist.Sie könnten beispielsweise nach der Häufigkeit der Wörter im gesamten Datensatz sortieren (zuerst nach den am wenigsten verbreiteten Wörtern), wodurch die Anzahl der rekursiven Aufrufe verringert werden kann.