Ich habe einen langen Text (ca. 5 MB Dateigröße) und einen anderen Text namens Muster (ca. 2000 Zeichen).
Die Aufgabe besteht darin, übereinstimmende Teile aus einem Genommuster zu finden, die im Langtext 15 Zeichen oder länger sind.
Beispiel:
langer Text: ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT UND VIEL Länger
Muster: ACGGTATTGAC AAAACCCCGGGGTTTTA TGTTCCCAG
Ich suche nach einem effizienten (und leicht zu verstehenden und zu implementierenden) Algorithmus.
Ein Bonus wäre eine Möglichkeit, dies mit nur char-Arrays in C ++ zu implementieren, wenn das überhaupt möglich ist.
Hier ist ein Algorithmus - ich bin mir nicht sicher, ob er einen Namen hat. Es erfordert einen "rollenden Hash" - eine (nicht-kryptografische) Hash-Funktion, die die Eigenschaft hat, dass es beim Hash einer Sequenz AB...C effizient ist, den Hash der Sequenz B...CD zu berechnen.
Berechnen Sie die rollenden Hashes der Sequenzen pattern[0..14] , pattern[1..15] , pattern[2..16] ... und speichern Sie jeden Index in pattern in einer Hash-Tabelle.
Berechne den rollenden Hash von haystack[0..14] und überprüfe, ob er sich in der Hashtabelle befindet. Wenn dies der Fall ist, vergleichen Sie haystack[0..14] mit pattern[pos..pos+14] , wobei pos aus der Hashtabelle abgerufen wurde.
Berechnen Sie aus dem rollenden Hash von haystack[0..14] effizient den rollenden Hash von haystack[1..15] und sehen Sie, ob er sich in der Hash-Tabelle befindet. Wiederholen Sie dies, bis Sie das Ende von haystack erreicht haben.
Beachten Sie, dass Ihre 15 Zeichenfolgen nur 2 30 mögliche Werte haben, also könnte Ihre "Hash-Funktion" eine einfache Zuordnung zum Wert der als 15-stellige Base-4-Nummer behandelten Zeichenfolge sein ist schnell zu berechnen, hat die rollende Hash-Eigenschaft und ist eindeutig.
Ein Weg wäre, eine Implementierung von Aho-Corasick zu bekommen und sie zu benutzen um etwas zu erstellen, das einen der 15-stelligen Chunks im Muster erkennt und dann den Text durchsucht. Mit Aho-Corasick sind die Kosten für die Erstellung des Matcher und die Kosten für die Suche linear, daher sollte dies praktisch sein.
Wenn Sie eine gute Implementierung der C-Bibliothek verwenden (oder sogar eine mittelmäßige Version wie glibc, die eine gute Implementierung dieser Funktion besitzt), wird strstr sehr gut funktionieren. Ich habe gehört, dass es einen neuen Algorithmus gibt, der besonders gut für DNA (kleines Alphabet) ist, aber ich kann die Referenz nicht finden. Ansonsten ist 2way (was glibc verwendet) optimal.
Ich würde sehr empfehlen, dass Sie in Ihre Bibliothek gehen und "Algorithms 4th Edition" von Robert Sedgwick und Kevin Wayne ausprobieren. Sie haben ein ganzes Kapitel, das sich der Teilstringsuche widmet. Darüber hinaus lohnt es sich, die Buchwebseite algs4.cs.princeton.edu zu besuchen.
TL; DR - Wenn Sie bestimmt sind, können Sie sich eine Teilstringsuche mit Char-Arrays in garantierter Zeit linear zur Eingabedauer erstellen. Es gibt Codebeispiele im Buch und online. Es wird nicht viel einfacher als das.
Ich denke, dass der "Suffix-Baum" es besser lösen kann mit einer Präformanz von O (log n)
