Eugene Myers'ın Diff Algoritma: 'A' ve 'B'

Question

Ben Eugene Myers' Diff Algorithm Paper gözden oldum en uzun ortak sonradan bulma. Bu, popüler diff programında uygulanan algoritmadır. "

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]. 

varsayalım A = "A" ve B =:

kağıdın 12. sayfada

, bu A ve B en uzun ortak alt dizisini bulmak için algoritması için sözde kodu göstermektedir B". Bu durumda, N = 1 ve M = 1'dir. Orta yılan, (x, y) = (0, 1) ve (u, v) = (0, 1) olur, çünkü diyagonal yoktur. Bu durumda D = 1 çünkü algoritma sadece bir adım attı.

Algoritma, bu senaryoda yapılacak tek şeyin Output B[1..M], "B" ye eşit olduğunu, çünkü N> 0, M> 0, D = 1 ve M = N olduğunu söylüyor. Ancak bu yanlış görünüyor, çünkü "A" ve "B" arasında ortak bir alt sıra yoktur. Gazetenin açıklama, "D < = 1 daha sonra B ya da silerek elde edilen veya en fazla bir sembolüne sokulması durumunda", "A" kaldırılmalıdır çünkü yanlış ve "B" eklendi.

Burada ne yanlış yorumlama ben?

Answer 1

Sen D-yolu ve yılan tanımını yanlış anlama vardır. Sayfa 4

:

D-yolunu tam olarak D olmayan çapraz kenarları olan bir yol (0,0) 'dan başlayan olsun. Bir 0 yolu sadece çapraz kenarlardan oluşmalıdır. Basit bir indüksiyon ile, bir D-yolu bir madde olduğu, aşağıdaki (D - 1) olmayan bir çapraz kenar bırakılır ve diyagonal kenarları bir olasılıkla boş sırası bir yılan adı -Path

Yani, A = "A" ve B = "B" olan örnekte, en uygun yol 2 yoldur (bir yatay ve bir dikey) ve orta yılan boş bir dizedir. İncelememizden LCS'nin boş bir dizilim olduğunu biliyoruz, ancak bunu kanıtlamak için çalışan algoritmayı göstermek istiyoruz. Her şeyden

Önce orta yılan bulmalıyız. 11. sayfadaki orta yılanı bulmak için algoritmayı takip ederseniz, en kısa düzenleme komut dosyasının uzunluğunun 2 ve (x, y) = (u, v) = (1,0) veya (0,1) olduğunu göreceksiniz.). Başka bir deyişle, yolun ortasındaki boş bir yılandır.

algoritması yalancı kod

olmayan bazı belirgin simge özellikleri vardır:

1. bir [m..n] n-< m ise boş bir dizisidir. LCS özyinelemeli aramalarda
, ilk çağrı D olarak tavan (D/2) kullanan ikinci bir arama kat (D/2) kullanır. Bu, algoritmanın üstündeki metinde, sayfa 12'de daha net olarak açıklanmıştır.

Bu örnekte, LCS'ye yapılan ilk çağrının (x, y) = (u, v) ile bir orta yılan bulduğunu varsayın. Bu şeritler ortak bir alt sekansına sahiptir, çünkü bu doğrudur

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 

: = (1,0), daha sonra D = 2 olduğundan, sonuç genişlemesidir.