Algoritmo di diffusione di Eugene Myers: trovare la più lunga sequenza di "A" e "B"

Question

Ho esaminato Eugene Myers' Diff Algorithm Paper. Questo è l'algoritmo implementato nel popolare programma diff.

A pagina 12 del documento, esso presenta la pseudo-codice per l'algoritmo per trovare la più lunga comuni sotto-sequenza di A e B:

LCS(A, N, B, M) 
    If N > 0 and M > 0 Then 
     Find the middle snake and the length of an optimal path for A and B. 
     Suppose it is from (x, y) to (u, v). 
     If D > 1 Then 
      LCS(A[1..x], x, B[1..y], y) 
      Output A[x+1..u] 
      LCS(A[u+1..N], N-u, B[v+1..M], M-v) 
     Else If M > N Then 
      Output A[1..N]. 
     Else 
      Output B[1..M]. 

Supponiamo che A = "A" e B = " B". In questo caso, N = 1 e M = 1. Il serpente medio sarebbe (x, y) = (0, 1) e (u, v) = (0, 1) perché non ci sono diagonali. In questo caso D = 1 perché l'algoritmo ha solo fatto un passo.

L'algoritmo dice che l'unica cosa da fare in questo scenario è Output B[1..M], uguale a "B", perché N> 0, M> 0, D = 1 e M = N. Ma questo sembra sbagliato, perché non esiste una sotto-sequenza comune tra "A" e "B". Il commento del paper che "Se D < = 1 allora B è ottenuto da A eliminando o inserendo al massimo un simbolo" non è corretto perché "A" deve essere rimosso e "B" aggiunto.

Cosa sto interpretando male qui?

Answer 1

Si sta fraintendendo la definizione di D-path e snake.

Da pagina 4:

Facciamo un D-percorso sia un percorso che inizia a (0,0) che ha esattamente D non diagonali bordi. Un percorso a 0 deve essere costituito esclusivamente da bordi diagonali. Da un semplice induzione, ne consegue che un D-percorso deve consistere in un (D - 1) -path seguita da un bordo non diagonale e poi una sequenza vuota di bordi diagonali chiamato un serpente

Quindi, nel tuo esempio in cui A = "A" e B = "B", il percorso ottimale è un 2-path (uno orizzontale e uno verticale) e il middle snake è una stringa vuota. Sappiamo che dall'ispezione la LCS è una stringa vuota, ma vorremmo mostrare l'algoritmo che funziona per dimostrarlo.

Prima di tutto dobbiamo trovare il serpente medio. Se segui l'algoritmo per trovare il serpente medio a pagina 11, vedrai che la lunghezza dello script di modifica più breve è 2 e (x, y) = (u, v) = (1,0) o (0,1). In altre parole, è un serpente vuoto nel mezzo del percorso.

Lo pseudo algoritmo ha alcuni simboli convenzionalmente non ovvie:

1. A [m..n] è una stringa vuota se n < m.
2. Nelle chiamate ricorsive a LCS, la prima chiamata utilizza il limite massimo (D/2) come D e la seconda chiamata utilizza il piano (D/2). Questo è reso più chiaro nel testo sopra l'algoritmo a pagina 12.

Quindi, in questo esempio, si supponga che la prima chiamata a LCS trovi un serpente medio con (x, y) = (u, v) = (1,0), poi dato D = 2, il risultato è l'espansione:

LCS(A[1..1], 1, B[1..0], 0) // Output nothing since M = 0 
Output A[2..1]    // Output nothing since it is an empty string. 
LCS(A[2..1], 0, B[1..1], 1) // Output nothing since N = 0 

Ciò è corretto poiché queste stringhe non hanno sub-sequenza comune.