Wie finden Sie unbekannte wiederholte Muster in der Reihe von Strings?

Question

Hier ist eine Beschreibung eines Problems. Angenommen, Sie haben eine Menge von Strings (bis zu 10 Milliarden Strings, jede String-Länge bis zu 10k Zeichen, es gibt 1000 eindeutige Symbole, aus denen String konstruiert werden könnte). Wie kann ich Muster mit einer Länge von 2 bis zu einer Länge N finden (sagen wir 10 zur Vereinfachung). Außerdem möchte ich nur die Muster sehen, die mindestens in 1% der gesamten Zeichenfolge vorkommen (ein gewisser Schwellenwert).

Ich möchte einen Algorithmus finden, der mir helfen kann, dieses Problem zu lösen. Die Zahlen sind nicht exakt, haben aber die gleiche Größenordnung wie im Projekt.

Danke

Answer 1

Index alle Ihre Strings in einem Suffix-Baum (link). Dies kann O (Anzahl der Zeichen) sein und Sie müssen es nur einmal tun, bevor Sie beginnen.

Ein Suffixbaum ermöglicht es Ihnen schnell (O (Musterlänge)) festzustellen, ob ein Muster in einer der Zeichenfolgen angezeigt wird, die Sie indiziert haben, und wie oft.

Sie können einen weiteren Durchlauf durch die Struktur durchführen und die Anzahl der Blätter in jedem Teilbaum (O (N) erneut) zählen und Sie erfahren, wie oft Sie den Teilstring vom Stamm zu diesem Knoten finden können Sie oder tun, was Sie wollen, basierend auf wie üblich sie sind.

Jetzt sind 10 Milliarden Strings der Länge 10k, mit 2-Byte-Zeichen (um die 1000 eindeutigen Symbole zu passen) ziemlich groß (18TB, wenn meine Mathematik richtig ist), die nicht in RAM passt. Sie müssen also entweder eine Weile warten oder mehr Computer und eine verteilte Lösung einrichten. Sie können die obige Lösung auf Zeichenketten anwenden, so dass sie in den verfügbaren Speicher passen. Die Suche in der Struktur muss jedoch mit der Anzahl der Stapel multipliziert werden, die Sie ausführen.

Wenn alles in Stapeln ist, dann wäre der effizienteste Weg, Stapel so groß wie möglich zu machen. Wenn Sie den Suffixbaum für einen Stapel erstellt haben, führen Sie alle Ihre Abfragen durch, speichern Sie die Ergebnisse und legen Sie den Pfad ab Baum, um Speicher für den nächsten Stapel von Eingabezeichenfolgen freizugeben.