Applicazioni della sottosquadra crescente più lunga

Question

Quanto è utile il problema LIS (Longest Increasing Subsequence) nell'affrontare altri problemi CS? Ci sono alcuni algoritmi, usando l'ordinamento della pazienza, la programmazione dinamica o con gli alberi decisionali. Come vengono utilizzati nella vita reale - forse per flussi di dati o qualcosa del genere?

Per ricordare, ho messo in grassetto la più lunga sequenza crescente

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

Come bonus, c'è un modo per utilizzare il risultato che a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n? Per esempio. La nostra lista come lunghezza 16, quindi ci dovrebbe essere una sequenza crescente di lunghezza 5 o sequenza decrescente di lunghezza 5. Nel nostro caso 0,2,6,9,11,15.

Anche una sequenza crescente di lunghezza 8 o una sequenza decrescente di lunghezza 3: nel nostro caso 12,10,1.

Answer 1

Un'interessante applicazione nel mondo reale di LIS è la pazienza Diff, un diffing algoritmo Bram Cohen (il creatore di BitTorrent) che viene utilizzato nel sistema di controllo di versione Bazaar.

L'algoritmo diff regolare comporta il calcolo dell'LCS (Longest Common Subsequence) tra due documenti. Pur essendo efficiente, questo approccio ha un problema, che è: spesso i risultati non sono del tutto rispettosi dell'umano.

Un semplice esempio di come un diff regolare può riuscire:

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

void func2() { 
    x += 2 
} 

Il vantaggio dell'algoritmo Diff pazienza è che permette di calcolare le differenze più accuratamente, in modo più strettamente corrispondente a come un essere umano si esibirebbe.

Nel precedente caso Pazienza Diff ha visto la differenza meglio:

void func1() { 
    x += 1 
} 

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

In poche parole, l'algoritmo è:

1. Trova linee uniche che sono comuni a entrambi i documenti.
2. Prendere tutte queste righe dal primo documento e ordinarle in base al loro aspetto nel secondo documento.
3. Calcolare il LIS della sequenza risultante (facendo un Patience Sort), ottenendo la sequenza di linee di corrispondenza più lunga, una corrispondenza tra le righe di due documenti.
4. Recurse l'algoritmo su ogni intervallo di righe tra quelle già abbinate.

Dai uno sguardo allo the code.