In den letzten Tagen habe ich das umfassend recherchiert, ich habe so viele Dinge gelesen, dass ich jetzt mehr verwirrt bin als je zuvor. Wie findet man die längste gemeinsame Sub-Zeichenfolge in einem großen Datensatz? Die Idee besteht darin, doppelten Inhalt aus diesem Datensatz zu entfernen (mit unterschiedlichen Längen, so dass der Algo kontinuierlich ausgeführt werden muss). Unter großen Datensätzen verstehe ich ungefähr 100 MB Text.
Suffixbaum? Suffix-Array? Rabin-Karp? Was ist der beste Weg? Und gibt es da draußen eine Bibliothek, die mir helfen kann?
Ich hoffe wirklich auf eine gute Antwort, mein Kopf schmerzt sehr. Vielen Dank! : -)
Ich habe immer Suffix-Arrays verwendet. Weil mir immer gesagt wurde, das ist der schnellste Weg dorthin.
Wenn auf dem Computer, auf dem der Algorithmus ausgeführt wird, nicht genügend Arbeitsspeicher zur Verfügung steht, können Sie Ihr Array immer in einer Datei auf Ihrer Festplatte speichern. Es wird den Algorithmus erheblich verlangsamen, aber es wird das Ergebnis liefern, alt.
Und ich denke nicht, dass eine Bibliothek einen besseren Job als einen guten geschriebenen und sauberen Algorithmus machen wird.
LE: Übrigens müssen Sie keine Daten entfernen, um die längste gemeinsame Teilzeichenfolge zu finden.
Aus dem Längstes häufiges Unterstring-Problem :
%Vor%Sie müssen nichts sortieren, Sie müssen nur einmal Ihre 100 MB Daten parsen und ein n * m Array von Zeichen erstellen, um Ihre Daten zu speichern. Überprüfen Sie auch diese Seite
LE: Rabin-Karp ist ein Pattern-Matching-Algorithmus, den Sie hier nicht brauchen.
Tags und Links algorithm string large-files suffix-tree