Алгоритм диффузии Юджина Майерса: поиск самой длинной общей подпоследовательности «A» и «B»

Question

Я рассматривал Eugene Myers' Diff Algorithm Paper. Это алгоритм, реализованный в популярной программе diff.

На 12-й странице газеты, он представляет псевдо-код для алгоритма, чтобы найти самую длинную общую подпоследовательность A и 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]. 

Пусть А = «A» и B = " B». В этом случае N = 1 и M = 1. Средняя змея будет (x, y) = (0, 1) и (u, v) = (0, 1), потому что нет диагоналей. В этом случае D = 1, потому что алгоритм сделал только один шаг.

Алгоритм говорит, что единственное, что нужно сделать в этом сценарии, - это Output B[1..M], равное «B», поскольку N> 0, M> 0, D = 1 и M = N. Но это кажется неправильным, потому что нет общей подпоследовательности между «А» и «В». Комментарий к статье: «Если D < = 1, то B получается из A путем удаления или вставки не более одного символа» неверно, потому что «A» необходимо удалить и добавить «B».

Что я неправильно интерпретирую здесь?

Answer 1

Вы недопонимаете определение D-пути и змеи.

От страницы 4:

Пусть D-путь будет путь, начинающийся в точке (0,0), что имеет ровно D недиагональные края. Путь 0 должен состоять только из диагональных ребер. По простой индукции, то отсюда следует, что D-путь должен состоять из (D - 1) -path с последующим недиагональным краем, а затем возможно пустая последовательность диагональных ребер называется змея

Итак, в вашем примере, где A = «A» и B = «B», оптимальный путь - это 2-дорожечный (один горизонтальный и один вертикальный), а средняя змея - пустая строка. Мы знаем из проверки, что LCS - пустая строка, но мы хотели бы показать алгоритм, который будет ее доказывать.

Прежде всего, нам нужно найти среднюю змею. Если вы будете следовать алгоритму, чтобы найти среднюю змею на стр. 11, вы увидите, что длина кратчайшего скрипта редактирования равна 2 и (x, y) = (u, v) = (1,0) или (0,1). Другими словами, это пустая змея в середине пути.

Алгоритм псевдокод имеет некоторые неочевидные условные обозначения:

1. A [m..n] является пустой строкой, если п < м.
2. В рекурсивных вызовах LCS первый вызов использует потолок (D/2) как D, а второй вызов использует пол (D/2). Это сделано более ясно в тексте выше алгоритма на стр. 12.

Итак, в этом примере, предположим, что первый вызов LCS находит среднюю змею с (x, y) = (u, v) = (1,0), то, так как D = 2, то результат является расширением:

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 

Это верно, так как эти строки не имеют общую подпоследовательности.