Wie die Berechnung der Länge der längsten gemeinsamen Teilkette zu beschleunigen?

Question

Ich habe zwei sehr große Strings und ich versuche, ihr, um herauszufinden, Längste gemeinsame Substring .

Eine Möglichkeit ist, mit Suffix Bäume (angeblich eine sehr gute Komplexität haben, obwohl eine komplexe Implementierung), und die andere ist die dynamische Programmierverfahren (beide genannt werden auf der Wikipedia-Seite verlinkt oben).

Die Verwendung dynamischer Programmierung

Das Problem ist, dass die dynamischen Programmierverfahren eine große Laufzeit (Komplexität ist O(n*m), wo n und m sind Längen der beiden Strings).

Was ich (vor dem Sprung Suffix Bäume zu implementieren) wissen will: Ist es möglich, den Algorithmus zu beschleunigen, wenn ich nur die Länge der gemeinsamen Teilzeichen wissen will (und nicht die gemeinsamen String selbst)

Answer 1

Wird es schneller in der Praxis? Ja. Wird es schneller in Bezug auf Big-Oh sein? No. Die dynamische Programmierlösung ist stets O (n * m).

Das Problem, dass Sie in mit Suffix-Bäumen laufen könnten, ist, dass Sie den Suffixbaum des lineare Zeit Scan für eine große Strafe im Raum handeln. Suffix Bäume sind in der Regel viel größer als die Tabelle, die Sie für eine dynamische Programmierung Version des Algorithmus zu implementieren, benötigen würden. Abhängig von der Länge der Saiten, dann ist es durchaus möglich, dass die dynamische Programmierung schneller sein wird.

Viel Glück:)

Answer 2

Diese werden sie schneller laufen, obwohl es immer noch O(nm) sein wird.

Eine Optimierung ist im Raum (die Ihnen eine wenig Zuteilung Zeit sparen kann) ist, dass LCSuff bemerken hängt nur von der vorherige Reihe - also, wenn Sie nur über die Länge kümmern, können Sie den O(nm) Raum nach unten zu O(min(n,m)) optimieren können <. / p>

Die Idee ist, nur zwei Reihen zu halten -. Die aktuelle Zeile, dass Sie bearbeiten, und die vorherige Zeile, die Sie gerade verarbeitet werden, und den Rest wegzuwerfen

Answer 3

Hier ist ein einfacher Algorithmus, wo Oberflächen in O ((m + n) * log (m + n)), und viel einfacher zu implementieren im Vergleich zu Suffixbaum Algorithmus, der O (m + n) Laufzeit.

lassen Sie es mit min gemeinsamer Länge (minL) start = 0 und max gemeinsame Länge (Maxl) = min (m + n) + 1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

Das verbleibende Problem ist, wie alle Teilkette mit einer Länge L in der Zeit O (n) hashen. Sie können eine Polynom Formel wie folgt verwendet werden:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

Myer-Bit-Vektor-Algorithmus Ihnen helfen können. Es funktioniert durch die Bit-Manipulation und ist eine viel schnellere Annäherung.