Ich muss eine große Liste von URLs (einige Millionen Zeilen) als zu einer bestimmten Kategorie gehörend erkennen. Ich habe eine andere Liste, die Teilzeichenfolgen hat, die, wenn sie in der URL vorhanden sind, zu dieser Kategorie gehören. Sagen Sie, Kategorie A.
Die Liste der zu überprüfenden Sub-Strings hat ungefähr 10k solcher Sub-Strings. Was ich getan habe, war einfach Zeile für Zeile in der Sub-String-Datei zu gehen und nach der Übereinstimmung zu suchen. Wenn sie gefunden wird, gehört die URL zur Kategorie A. Ich habe in Tests herausgefunden, dass dies ziemlich zeitaufwendig ist.
Ich bin kein Informatikstudent, also habe ich nicht viel Wissen über die Optimierung von Algorithmen. Aber gibt es eine Möglichkeit, dies schneller zu machen? Nur einfache Ideen. Die Programmiersprache ist kein großes Problem, aber Java oder Perl wäre vorzuziehen.
Die Liste der übereinstimmenden Teilzeichenfolgen ändert sich nicht viel. Ich werde jedoch verschiedene Listen von URLs erhalten, also muss ich diese jedes Mal ausführen, wenn ich sie bekomme. Der Flaschenhals scheint die URLs zu sein, da sie sehr lang werden können.
Ja, ich habe den Aho-Corasick-Algorithmus -Algorithmus in Java für das Problem implementiert, das Sie sind suggerieren und es zeigte sich eine konsistente Verbesserung von etwa x180 bei der naiven Implementierung (was Sie tun). Es gibt mehrere Implementierungen online verfügbar, obwohl ich sie für eine bessere Leistung zwicken würde. Beachten Sie, dass die Komplexität der Lösung durch die Länge des Wortes (in Ihrem Fall die URL) und nicht durch die Anzahl der Teilzeichenfolgen begrenzt wird. außerdem benötigt es im Durchschnitt nur einen Durchlauf für die Übereinstimmung.
P. S. - wir haben diese Frage in Vorstellungsgesprächen an Menschen gestellt, daher gibt es viele Möglichkeiten, sie zu lösen. Die eine, die ich anbiete, ist diejenige, die wir im Produktionscode verwenden, die (vorerst) alle anderen Lösungen schlägt.
Bearbeiten: schrieb zuvor den falschen Algorithmusnamen, behoben ...
Perl ist sehr gut darin, lange Listen alternativer Strings in einem regulären Ausdruck zu optimieren (bis zu einer bestimmten Länge des gesamten kompilierten Regex, wo es zu einem weniger effizienten Mechanismus zurückkehrt). Sie sollten in der Lage sein, eine Regex zu erstellen, die einer bestimmten Kategorie wie folgt entspricht:
%Vor%Um dies zu optimieren, sind natürlich verschiedene Ansätze möglich. In Bezug auf Ihren Hintergrund skizziere ich Ihnen einen einfachen. Das setzt voraus, dass sich die Liste der Teilzeichenfolgen nicht sehr oft ändert.
Ich würde vorschlagen, den altehrwürdigen Grep zu verwenden, anstatt eine Programmiersprache für diese Aufgabe zu verwenden. Es verwendet den schnellen Boyer-Moore String-Suchalgorithmus , der für einige Millionen Zeilen ausreichen sollte .
Ich habe das schon mal in Perl gemacht, indem ich eine Liste von ~ 13.000 Keywords mit einem eingehenden Datenstrom von Twitter verglichen habe, um alle Tweets zu finden, die mit diesen Keywords übereinstimmen (und welche Keywords jeweils übereinstimmen). Grob gesagt sieht der Code so aus:
%Vor%Beachten Sie, dass Regexp :: Assemble verwendet wird, um die Regex zu erstellen, die nicht Teil der Kern Perl-Distribution, so müssen Sie installieren, wenn aus CPAN, wenn Sie diesen Code anpassen möchten.
Wenn Sie Perl 5.10 oder höher verwenden, gibt es auch den Operator "smart match" ( ~~ ), der ähnliche Funktionen ohne zusätzliche Module ausführen kann.
Sie könnten die Teilzeichenfolgen in Klassen komprimieren, die dasselbe Präfix verwenden. Dies sollte die Zeit deutlich reduzieren.
Wenn Sie nach Übereinstimmungen suchen, indem Sie den String bei jeder Iteration um 1 verschieben, können Sie Ihre Geschwindigkeit mit einem besseren Algorithmus (wie bei regulären Ausdrücken) erheblich verbessern.
Für Java-Bibliotheken, die gängige String-Suchalgorithmen implementieren, sehen Sie die Antworten zu Ссылка . In Verbindung mit der Parallelisierung sollten Sie in der Lage sein, Millionen von URLs schnell zu parsen. Es ist einfach genug zu tun; Sie sollten es wahrscheinlich ausprobieren und sehen, ob die Zeit akzeptabel ist oder nicht, bevor Sie zu weit in die Optimierung gehen.
Ich schrieb es zuerst als Kommentar, aber dann wurde mir klar, dass es für eine Antwort besser geeignet ist
Sie können ein Information-Retrieval-System (wie Apache Lucene in Java) verwenden und es zum Indizieren der URLs verwenden als Dokumente.
Nach der Indexierung können Sie dann die Abfragen durchlaufen und nach ihnen suchen. Das Ergebnis sind die übereinstimmenden URLs.
PROS:
Die Suche nach * erfordert keine Iteration über alle URls für jede Abfrage.
* Wenn Sie später eine Kreuzung oder Vereinigung von Teilstrings / Abfragen benötigen - die Bibliothek bietet Ihnen diese Funktionalität
CONS:
* Indizierung wird eine Weile dauern ...
* Sie benötigen möglicherweise zusätzlichen Speicherplatz auf dem RAM / Datenträger für den Index.
Ich denke, es ist eine Methode, die es wert ist, erforscht zu werden, vielleicht ist die Zeit, die während der Indexierung verbraucht wird, den Gewinn der Suche wert.
Ich arbeite gerade an diesem Problem. Ich kam zu dieser Schlussfolgerung:
Aho-corasick wird mehr Speicher verbrauchen, während er Baum macht. Wenn es kein Problem mit der Erinnerung gibt, ist es gut. Aber schau mal auf den HAT Trie. Es ist die Kombination von Hash und Trie (Baum). Es wird einen Baum auf einer bestimmten Ebene bilden und die verbleibenden Zeichen bilden einen Hash-Wert, der in der Hash-Tabelle markiert sein sollte.
Entschuldigung für mehr technische Sprache. Aber ich denke, HAT Trie ist die bessere Option, wenn Sie eine bestimmte URL aus der Liste der URL suchen. (Ich habe einen HAT-Trie gebildet, der 12 MB zum Speichern von 6-Klicks der URL verbraucht.)
Tags und Links java optimization perl search