En Uzun Ortak Alt Dizi (LCS)

İki dizinin sırasını koruyarak paylaştığı en uzun alt diziyi bir DP tablosuyla bulan algoritma; diff ve DNA hizalamanın temeli.

Önce bunlara göz at

Fibonacci ve Memoization

#Nasıl çalışır?

Bir alt dizi (subsequence), bir dizinin bazı elemanlarını silip kalanların sırasını koruyarak elde edilen dizidir; harflerin yan yana olması gerekmez. ABCBDAB ve BDCABA'nın en uzun ortak alt dizisi (LCS) BCBA'dır (uzunluk 4).

dp[i][j], X'in ilk i harfi ile Y'nin ilk j harfinin LCS uzunluğudur. Son harfler eşitse bu harf LCS'e eklenir: dp[i][j] = dp[i − 1][j − 1] + 1. Farklıysa iki harften biri dışarıda kalır ve daha iyi olan seçilir: max(dp[i − 1][j], dp[i][j − 1]).

Tablo dolduktan sonra sağ alttan geri yürünerek alt dizinin kendisi bulunur: eşit harflerde çapraz yukarı-sola gidilir ve harf eklenir, aksi halde büyük değerli komşuya geçilir.

#Kendin dene

$ longest_common-subsequence --interactive

	B	D	C	A	B	A
	0	0	0	0	0	0
A
B
C
B
D
A
B

İki kelimeyi boşlukla ayırarak yaz. Tablo, ilk i harf ile ilk j harfin en uzun ortak alt dizisinin uzunluğunu tutar.

İki kelime (boşlukla)Hız

GeziliyorYeniÇıkarılıyorBulundu / okunan

#Adım adım

01İlk satır ve sütunu 0 yap: boş bir diziyle ortak alt dizi boştur.
02Her i, j için X[i] = Y[j] ise dp[i][j] = dp[i − 1][j − 1] + 1.
03Değilse dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]).
04dp[m][n] uzunluktur; alt diziyi sağ alttan geri izleyerek oku.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def lcs(x: str, y: str) -> str:
    m, n = len(x), len(y)
    # dp[i][j] = LCS length of x[:i] and y[:j]; row 0 and column 0 stay 0.
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # Walk back from the bottom right (up on ties).
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            out.append(x[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))


result = lcs("ABCBDAB", "BDCABA")
print(len(result))
print(result)

#Karmaşıklık

İşlem	Süre
Zaman	O(m · n)
Bellek (tam tablo)	O(m · n)
Sadece uzunluk (iki satır)	O(min(m, n)) bellek
Alt diziyi geri izlemek	O(m + n)

m ve n kelimelerin uzunluklarıdır; tablonun her hücresi sabit sürede doldurulur. Sadece uzunluk gerekiyorsa iki satır yeterlidir. Hirschberg algoritması alt diziyi de doğrusal bellekle bulabilir.

#Ne zaman kullanılır?

diff ve git gibi araçların iki dosya arasındaki farkı bulması, DNA ve protein dizilerinin hizalanması, intihal tespiti ve yazım düzeltme önerileri LCS'e dayanır. Yakın akrabası düzenleme mesafesi (edit distance) aynı tablo yapısını kullanır.