Längste gemeinsame Subsequenz zwischen sehr großen Strings

Question

Ich versuche das Longest Common subsequence problem zu lösen, welches das Problem ist, die längste Subsequenz zu finden, die allen Sequenzen in einer Menge von Sequenzen gemein ist (oft nur zwei Sequenzen).

Ich versuche dies zu tun, um die Überlappung zwischen 2 Strings zu berechnen.

Dies ist wohl bekannt Dynamic Programming Problem. In meinem Fall sind die Saiten jedoch zu groß. Als ich versuchte, die 2D-Matrix zum Memoisieren zu verwenden, stieß ich auf Probleme mit dem Speicher außerhalb des Bandes.

Eine Lösung könnte stattdessen eine spärliche Matrix sein, aber ich bin wenig besorgt über den Leistungsaufwand damit.

Auch ich möchte diesen Algorithmus über mehrere Zeichenfolgen durchführen. Und es wird in Ordnung sein, eine ungefähre Antwort zu geben, da ich nur versuche, die Überlappung zwischen zwei Saiten zu messen.

EDIT: Nach einigen Untersuchungen fand ich folgende Alternativen

1. Hirsch Algorithmus https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm

Originalpapier http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.348.4360&rep=rep1&type=pdf

2. Ungefähre Algorithmus: http://cs.haifa.ac.il/~ilan/online-papers/cpm09.pdf

3. Deposition und Erweiterung Ansatz zur Suche längste gemeinsame Subsequence für mehrere Sequenzen https://arxiv.org/pdf/0903.2015.pdf

4. LCS auf DNA-Sequenz http://www.sersc.org/journals/IJAST/vol47/2.pdf

5. effizienten Algorithmus http://www.sciencedirect.com/science/article/pii/S0885064X12000635

Answer 1

Speicherkomplexität zu reduzieren, die Sie nicht brauchen um die gesamte 2D-Tabelle zu speichern. Sie können nur die Zeile über und die aktuelle Zeile speichern und somit den Speicherverbrauch um O(N) reduzieren, wenn Sie das Maximum in einer anderen Datenstruktur speichern. Dies führt zu O(N) Speichernutzung, aber Zeitkomplexität bleibt O(N^2).