Welche Art von Algorithmen + Datenstrukturen, die mir dabei helfen würden?
Eine Datei enthält wie 10000 ~ Zeilen im Speicher in einer geordneten Menge geladen. Mit einer gegebenen Suchzeichenkette möchte ich alle Zeilen erhalten können, deren Wörter vorangestellt sind und Wörter enthalten, die in Suchzeichenfolge gefunden werden. Nun, lassen Sie mich ein Beispiel geben, um dies zu verdeutlichen:
"Eine Stirn Fox fliegt."
"Hunde hassen Adler", "Delphine haben Augen und Zähne"
(schnell genug für mich dauerte es etwa 30ms ~ (einschließlich Sortieren des Endergebnisses) auf meinem PC auf einer Reihe von 10k Zeilen 3 Wörter pro Zeile)
Ich denke, was Sie wahrscheinlich wollen, ist ein trie . Konstruiere einen für die Menge aller Wörter in deinem Dokument und lasse jedes Blatt auf ein Hash-Set zeigen, das die Indizes der Zeilen enthält, in denen der Schlüssel des Blattes erscheint.
Um eine Suche auszuführen, verwenden Sie jedes Fragment der Suchzeichenfolge, um zu einem Knoten in der Baumstruktur zu navigieren und die Vereinigung über die Hashsets aller Blätter in der Unterstruktur dieses Knotens zu übernehmen. Dann würden Sie die Schnittmenge dieser Vereinigungen über die Menge der Fragmente nehmen, um die Liste der Zeilen zu erhalten, die die Suchzeichenfolge erfüllen.
Hier sind meine 2 Cent:
%Vor%Ich werde nicht viel erklären, da Code die beste Dokumentation ist: P.
Ausgabe: A brow Fox flies. AA AB AC
Wenn Sie alles effizient implementieren, wird die Laufzeit so gut wie möglich sein, da Sie jedes Wort mindestens EINMAL lesen müssen.
Weitere Optimierung kann durchgeführt werden und Threading anwenden. Sie können das PARALLEL AGGREGATION-Konzept einsehen, da dieses Problem leicht parallelisiert werden kann.
Hier ist eine ziemlich einfache Implementierung, die für Ihren Anwendungsfall geeignet sein sollte. Die Idee ist, dass Sie alle Kombinationen von kurzen Präfixen für jede Zeile (und für jede Abfrage) speichern können, da Sie nur 10.000 Zeilen haben und davon ausgehen, dass jede Zeile nicht zu viele Wörter enthält. Sehen Sie sich nun jeden Hash an, der für die Abfragezeichenfolge generiert wurde. Bei jedem Hash-Match suchen wir nach einer genauen Übereinstimmung. Für meinen Beispielcode betrachte ich nur Präfixe der Länge 1, jedoch könnte man diesen Ansatz für Präfixe der Länge 2 & amp; 3 vorausgesetzt, die Präfixe in Ihrer Abfrage haben diese Längen auch.
%Vor%