Anwendungen der am längsten wachsenden Subsequenz

Question

Wie nützlich ist das LIS (Longest Increasing Subsequence) Problem bei der Bewältigung anderer CS-Probleme? Es gibt ein paar Algorithmen, die Geduldsortierung, dynamische Programmierung oder Entscheidungsbäume verwenden. Wie werden diese im wirklichen Leben verwendet - vielleicht zu Datenströmen oder so?

Zur Erinnerung, habe ich in bold die längsten wachsende Folge

{, 8, 4, 12, , 10, , 14, 1, , 5 , 13, 3, , 7, }.

Als Bonus gibt es eine Möglichkeit, das Ergebnis zu verwenden, dass a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n? Z.B. Unsere Liste als Länge 16, so sollte es eine zunehmende Sequenz der Länge 5 oder abnehmender Reihenfolge der Länge 5 sein. In unserem Fall 0,2,6,9,11,15.

Auch eine zunehmende Sequenz der Länge 8 oder eine abnehmende Sequenz der Länge 3: in unserem Fall 12,10,1.

Answer 1

Eine interessante reale Anwendung von LIS ist Patience Diff, ein diffing Algorithmus von Bram Cohen (der Ersteller von BitTorrent), die im Versionskontrollsystem Bazaar verwendet wird.

Der normale Diff-Algorithmus beinhaltet die Berechnung der LCS (Longest Common Subsequence) zwischen zwei Dokumenten. Obwohl dieser Ansatz effizient ist, hat er ein Problem, nämlich - die Ergebnisse sind oft nicht sehr menschenfreundlich.

Ein einfaches Beispiel dafür, wie ein regulärer diff fehlschlagen:

void func1() { 
    x += 1 
+} 
+ 
+void functhreehalves() { 
+ x += 1.5 
} 

void func2() { 
    x += 2 
} 

Der Vorteil des Patience Diff-Algorithmus ist, dass es die Unterschiede genauer gesagt, in einer Art und Weise näher entspricht, wie ein Mensch zu berechnen erlaubt würde durchführen.

Im vorherigen Fall Geduld spots Diff die Differenz besser:

void func1() { 
    x += 1 
} 

+void functhreehalves() { 
+ x += 1.5 
+} 
+ 
void func2() { 
    x += 2 
} 

Auf den Punkt gebracht, ist der Algorithmus:

1. einzigartige Linien finden, die für beide Dokumente gemeinsam sind.
2. Nehmen Sie alle diese Zeilen aus dem ersten Dokument und ordnen Sie sie entsprechend ihrem Aussehen im zweiten Dokument an.
3. Berechnen Sie das LIS der resultierenden Sequenz (indem Sie eine Patience Sort tun), die längste übereinstimmende Sequenz von Zeilen, eine Entsprechung zwischen den Zeilen von zwei Dokumenten.
4. Rekursieren Sie den Algorithmus für jeden Zeilenbereich zwischen bereits übereinstimmenden Zeilen.

Werfen Sie einen Blick auf the code.