En uzun ortak alt dizi (LCS)

Bir dosyanın iki sürümünü karşılaştırdığınızda değişmeyen satırlar, ikisinin ortak bir alt dizisidir. En uzununu bulmak, tam olarak neyin eklendiğini ve neyin silindiğini söyler. Aynı fikir DNA zincirlerini hizalar ve yazım düzeltmeleri önerir; üstelik bilgisayar biliminin en zarif tablolarından biriyle çözülür.

Üst kenarında bir kelime, yanında başka bir kelime bulunan, hücrelerinde sayılar olan bir tablo ve sağ alt köşeden yukarı tırmanan turuncu hücrelerden bir yol
Üst kenarında bir kelime, yanında başka bir kelime bulunan, hücrelerinde sayılar olan bir tablo ve sağ alt köşeden yukarı tırmanan turuncu hücrelerden bir yol

Problem

Bir kelimenin alt dizisi, harflerinin bir kısmını özgün sıralarıyla korur: ACE, ABCDE'nin bir alt dizisidir ama EA değildir. İki kelimenin ortak alt dizisi, ikisinin de alt dizisi olan dizidir ve problem en uzununu bulmaktır. n uzunluğundaki bir kelimenin 2ⁿ alt dizisi vardır, bu yüzden birkaç harften uzun kelimelerde hepsini denemek umutsuzdur.

Tablo

len[i][j], bir kelimenin ilk i harfi ile diğerinin ilk j harfinin en uzun ortak alt dizisinin uzunluğu olsun. Boş bir kelimenin hiçbir ortak harfi yoktur, bu yüzden ilk satır ve ilk sütun 0'dır. i. harf j. harfe eşitse len[i][j] = len[i − 1][j − 1] + 1 olur: eşleşme, kendinden öncekini uzatır. Değilse len[i][j], len[i − 1][j] ile len[i][j − 1] değerlerinden büyük olanıdır: iki harften birini bırakın ve daha iyi sonucu tutun.

Bir örnek

ABCBDAB ile BDCABA'yı karşılaştırın. İkinci kelimenin ilk harfi B, 2. satırdaki B ile eşleşir; üçüncü sütundaki C, 3. satırla eşleşir ve bu böyle devam eder; her eşleşme sol üst çaprazdaki hücreye bir ekler. Sağ alt hücre sonunda 4 olur. Oradan geriye doğru okumak BCBA verir, ama BCAB ve BDAB de aynı uzunluktadır: en uzun ortak alt dizinin tek olması gerekmez.

Cevabı geriye doğru okumak

Sağ alt hücreden başlayın. Satırının ve sütununun harfleri eşleşiyorsa o harf cevaba aittir: not edin ve çapraz olarak sol üste geçin. Aksi hâlde üstteki ya da soldaki komşulardan değeri büyük olana geçin, çünkü hücre değerini oradan almıştır. İlk satırda ya da ilk sütunda durun. Not edilen harfler ters çevrildiğinde alt diziyi verir.

Tarihçe ve kullanım alanları

Tablo yöntemi 1970 civarında birkaç kişi tarafından birbirinden bağımsız olarak bulundu; bunlar arasında, 1974 tarihli makaleleri yakından ilişkili düzenleme mesafesi problemini çözen Robert Wagner ve Michael Fischer de vardı. 1975'te Dan Hirschberg alt dizinin çok daha az bellekle nasıl bulunacağını gösterdi ve 1976'da James Hunt ile Douglas McIlroy, Unix diff programını satırların en uzun ortak alt dizileri üzerine kurdu. Biyologlar aynı fikri, puanlarla birlikte, DNA ve protein dizilerini hizalamak için kullanır.

Peter Adams’ın Faces of Open Source için fotoğrafladığı Douglas McIlroy. 1976’da James Hunt ile birlikte Unix diff programını satırların en uzun ortak alt dizileri üzerine kurdu.
Peter Adams’ın Faces of Open Source için fotoğrafladığı Douglas McIlroy. 1976’da James Hunt ile birlikte Unix diff programını satırların en uzun ortak alt dizileri üzerine kurdu.

Kendiniz keşfedin

Uygulamayı açın ve Adım'a basın. Karşılaştırılan iki harf başlıklarda yanar; eşleşmede sol üst çaprazdaki mavi hücre, eşleşmemede üstteki ve soldaki iki mavi hücre okunur. Tablo dolunca turuncu yol köşeden geriye doğru tırmanır ve cevabın harfleri tablonun altında belirir.

Sık sorulan sorular

LCS algoritması ne kadar zaman ve bellek gerektirir?

m ve n uzunluğundaki kelimeler için O(m·n) zaman. Cevabı geriye doğru okumak için tam tablo da O(m·n) bellek gerektirir; Dan Hirschberg 1975'te alt dizinin kendisinin yalnızca O(min(m, n)) bellekle nasıl bulunacağını gösterdi.

diff en uzun ortak alt diziyi nasıl kullanır?

Bir dosyanın her satırını tek bir sembol olarak ele alır ve iki dosyanın satırlarının en uzun ortak alt dizisini bulur. Bu alt dizideki satırlar değişmemiştir; eski dosyanın diğer satırları silinmiş, yeni dosyanın diğer satırları eklenmiştir.

Üç ya da daha fazla kelime olursa?

Tablo her kelime için bir boyut kazanır, bu yüzden n uzunluğunda üç kelime n³ hücre gerektirir. Kelime sayısı keyfi olduğunda problem NP-zordur.

LCS'nin düzenleme mesafesiyle ilişkisi nedir?

Yalnızca ekleme ve silmeye izin verilirse, iki kelimenin düzenleme mesafesi toplam uzunluklarından en uzun ortak alt dizilerinin uzunluğunun iki katı çıkarılarak bulunur. Değiştirmeye de izin verilirse Levenshtein mesafesi elde edilir; o da çok benzer bir tabloyla hesaplanır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

En uzun ortak alt diziyi deneyin