Längste gemeinsame Subsequence

Question

Betrachten wir zwei Sequenzen X [1..m] und Y [1..n]. Der memoization Algorithmus würde die LCS in Zeit O (m * n) berechnen. Gibt es einen besseren Algorithmus, um herauszufinden, LCS wrt Zeit? Ich denke, memoization diagonal erfolgen können wir O geben (min (m, n)) Zeitkomplexität.

Answer 1

Gene Myers kam 1986 mit einem sehr schönen Algorithmus für den oben beschriebenen hier: Ein O (ND) Differenz Algorithmus und seine Variationen .

Dieser Algorithmus braucht Zeit proportional zu der Edit-Distanz zwischen den Sequenzen, so dass es viel schneller ist, wenn die Differenz klein ist. Es funktioniert durch alle möglichen bearbeiten Entfernungen Schleifen über, beginnend bei 0, bis er eine Entfernung findet, für die ein Skript bearbeiten (in gewisser Weise der dualen einen LCS) aufgebaut werden kann. Dies bedeutet, dass man „aus der Patsche helfen früh“, wenn die Differenz über einem gewissen Schwellenwert wächst, die manchmal bequem ist.

Ich glaube, dieser Algorithmus immer noch in vielen diff Implementierungen verwendet wird.

Answer 2

Wenn Sie wissen, a priori eine obere auf die maximale Größe gebunden k kümmern Sie, können Sie den LCS Algorithmus zum Beenden zwingen, früh durch Hinzufügen einer zusätzlichen Prüfung in der inneren Schleife. Das bedeutet dann, wenn k << min (m, n) können Sie kleine Laufzeiten trotz der Tatsache, Sie LCS tun bekommen.

Answer 3

ja wir einen besseren Algorithmus als Auftrag O schaffen könnten (m * n) --- d.h O (min (m, n)). eine Länge zu finden ..... nur die Diagonale elements.and vergleichen, wenn der Zuwachs erfolgt nehme an, es in c aufgetreten [2,2] dann alle den Wert von c erhöhen [2,2 ++] und c [2 ++ 2] von 1 .. und fahren bis c [m, m] .. (suppose m