Myers Difference Algorithm
Versiyon Kontrol Sistemi, üzerinde değişiklik yaptığımız dosyadaki farklılıkları nasıl bu kadar hızlı ve doğru fark ediyor? Google, bir Android uygulamasında liste üzerinde güncelleme işlemi yapıldığında listenin tamamının bildirilmesinin neden verimsiz olduğunu düşünüyor?
Bu ve benzeri sorular eminim ki birçoğumuzda merak uyandırıyor. Ben de bu merak ile çıktığım yolda Google tarafından önerilen yöntemin kaynak kodunda (source code) Myers Difference Algorithm’ın olduğunu gördüm ve bu konu üzerinde araştırmalar yapmaya başladım. Bu yazımda sizlere Myers Difference Algorithm’ın ne olduğunu aktarırken, bu algoritmanın hangi temellere dayandığı ve nerelerde kullanıldığı ile ilgili bilgiler de vereceğim.
Eugene W. Myers tarafından geliştirilen bu greedy diff algoritması, “An O(ND) Difference Algorithm and Its Variations” isimli makale ile 1986 yılında yayımlandı.
Bilgisayar bilimlerinde, iki içeriğin karşılaştırılması sonucunda anlamlı bir fark ve benzerlik çıktısı veren algoritmaları “diff” algoritmaları olarak isimlendirmekteyiz. Çoğunlukla diff algoritmaları, iki farklı versiyonu olan aynı dosyanın karşılaştırılması sırasında karşımıza çıkmaktadır.
Bu Algoritmanın Amacı Nedir?
Myers Diff Algorithm (MDA), iki dizi arasında en uzun ortak alt diziyi (longest common subsequence) ya da en uzun ortak alt diziye ulaşan yolu (shortest edit script) bulmayı hedefleyen bir algoritmadır.
En Uzun Ortak Alt Dizi (LCS) Nedir?
İki dizinin ortak alt dizisi, her iki dizide de aynı sırada görünen öğelerin dizisidir. Örneğin “XYAZ” ve “XZOH” kümelerini karşılaştırdığımız zaman, iki uzunluğa sahip LCS’nin “XZ” olduğunu göreceğiz. “ABC” ve “ACB” örneklerini karşılaştırdığımızda ise birbirinden farklı iki uzunluklu alt küme bulacağız: “AB” ve “AC”. Bu durumda algoritma bulduğu ilk alt kümeyi dönecektir.
Peki LCS’yi Nasıl Bulabiliriz?
MDA, LCS/SES problemini bulmak için Edit Graph dediğimiz, koordinat sistemine benzetebileceğimiz bir grafiği kullanıyor. Kullanılacak dizilerin doğru konumlandırılıp ilk dizinin elemanı ile ikinci dizinin elemanının bir araya geleceği; N’nin ilk dizinin, M’nin ise ikinci dizinin boyu olduğu varsayıldığı NxM bir graph elde edilir. Amacımız ise (0,0) noktasından (N,M) noktasına olabildiğince az hareket ile ulaşmaktır. Bu algoritmanın örnek ile daha iyi açıklanabileceğini düşündüğüm için, konuyu örnek üzerinden pekiştirmeye çalışacağız.
Karşılaştırmak istediğimiz ve aralarındaki farkları bulmak istediğimiz iki dizi tanımlayalım. X dizisi eski, Y dizisi ise yeni versiyonumuz olsun:
- X = “ABDEF”
- Y = “BDAE”
Bu durumda dizi boyutları:
- N = X.size = 5
- M = Y.size = 4
Edit Graph üzerinde yatay, dikey ve çapraz hareket edebiliriz. Amacımızın hareket ederek Y dizisini elde etmek olduğunu unutmayalım. Hareket ederken bilmemiz gereken 3 kural var:
- Yatay (Horizontal) hareket, sonuç dizisinden sil anlamına gelir. Örneğin; aşağıdaki grafikte (0,0)’dan (1,0) noktasına hareket edersek, sonuç dizisinden ‘A’ harfini silmiş oluruz.
- Dikey (Vertical) hareket, sonuç dizisine ekle anlamına gelir. Örneğin; aşağıdaki grafikte (0,0)’dan (0,1) noktasına hareket edersek, sonuç dizisine ‘B’ harfini eklemiş oluruz.
- Çapraz (Diagonal) hareket ise bir değişiklik olmadığı anlamına gelir. Çapraz yol ile karşılaşıldığında hareketi sonlandırmadan çapraz yol bitene kadar devam etmeliyiz. Örneğin; (0,0) noktasından (1,0) noktasına ilerle dediğimiz zaman (1,0) ile (3,2) arasındaki çapraz yol bitmediği için tek hareket ile (3,2) noktasına gelmiş oluyoruz. Burada unutmamamız gereken önemli nokta şu ki çapraz yolları hareket olarak saymıyoruz. Yani (0,0) noktasından (3,2) noktasına üç hareket ile değil de bir hareket ile erişmiş oluyoruz.
Edit Graph üzerinde yapacağımız işlemler şu şekilde olacaktır:
- Eski diziyi (X) üst tarafa, yeni diziyi (Y) sol tarafa koy.
- MxN boyutunda bir tablo oluştur.
- İki dizinin de her bir elemanının eşleneceği kutuları çiz.
- İki dizide aynı elemanlara denk gelen kutulara çapraz hareket edilebilecek bir yol aç.
- Bu adımlardan sonra tekrarlı bir şekilde (0,0) noktasından (5,4) noktasına erişmeye çalışacağız.
- Dikey, yatay ve çapraz hareket yapabileceğimiz bu sistemde (0,0) noktasından harekete başlayınca ulaşabileceğimiz en uzak noktalar şu şekildedir:
* (0,1) noktasına 1 dikey hareket ile ulaşabiliriz.
* (1,0) noktasına ise 1 yatay hareket ile ulaşabiliriz. Buna ek olarak (1,0) noktasından sonra, hiçbir değişiklik yapma anlamına gelen çapraz çizgiler ile karşılaşmamız sonucunda, hareketimize devam etmemiz gerekir. Önce (2,1) noktasına, sonrasında (3,2) noktasına erişiriz.
- Böylece ilk hareketimizden sonra yeni bir hareketi başlatacak iki farklı başlangıç noktamız oluyor: (0,1) ve (3,2).
(0,1) noktasından yatay hareket ile (1,1) noktasına, dikey hareket ile öncelikle (0,2) noktasına, ardından (1,3) noktasına erişebiliriz.
(3,2) noktasından yatay hareket ile (4,2) noktasına, dikey hareket ile öncelikle (3,3) noktasına, ardından (4,4) noktasına erişebiliriz.
- Yukarıdaki işlemi tekrarlayıp (4,4) noktasından bir yatay hareket yapıldığında (5,4) noktasına, yani amaçladığımız noktaya erişmiş oluruz.
Böylece X dizisinden Y dizisine ulaşan en az hareket sayısına sahip yolu (path) bulmuş oluyoruz. Aynı zamanda başlangıç noktasından bitiş noktasına kadar bu yolu takip ettiğimizde, eski diziden hangi karakterlerin silindiğini (yatay hareket), değişmeyen karakterleri (çapraz hareket) ve yeni diziye eklenen karakterleri (dikey hareket) görebiliriz.
Bu hareketleri en basit hali ile açıklamak gerekirse:
- Eski diziden A harfini çıkar
- B ve D harflerine dokunma
- A harfini ekle
- E harfine dokunma
- Eski diziden F harfini çıkar
Hareket olarak sadece ekleme ve çıkarma işlemlerini saydığımız için toplam üç hareket ile eski diziden yeni dizinin nasıl elde edildiğini görmüş oluyoruz.
Bu örneği Versiyon Kontrol Sisteminden alışık olduğunuz bir görsel ile incelemek istersek:
Yukarıdaki örneğin karmaşıklığının artmaması için algoritmanın orijinal halinde bulunan D-path ve K-line dediğimiz iki farklı kavramdan örnekte bahsetmedim. Bu iki kavram en kısa yolun doğru bir şekilde bulunmasında bizlere yardımcı olmaktadır.
K-line aslında sadece iki kural içeren ve en kısa yolun bulunmasına yardımcı olan bir çapraz çizgidir:
- Bir noktadaki K’nın değerini hesaplamak istiyorsak x-y değerine bakmalıyız (K = x — y).
- Yeni bir hareket yapmayı planlıyorsak, hareketin başarılı bir şekilde tamamlanması için ulaşacağımız noktadaki K değerine bakmamız gerekir. Bu noktaya kadar oluşturduğumuz yolda en az |K| adet harekete (ekleme ya da silme) sahipsek hareketi yapabiliriz. Eğer hareket sayımız |K|’dan az ise hareketi yapamayız.
D-path ise (0,0) noktasından başlayan, D sayısınca çapraz olmayan yol ile oluşturulmuş yoldur.
Örneğimizde (0,0) noktasından yapılabilecek ilk hareketin ulaşabileceği noktaların (0,1) ve (3,2) olduğunu düşünerek D = 1 için çizgimizi çekiyoruz. Bu işlemi tekrar ederek diğer D-path’lere de ulaşabiliriz.
Myers Algoritması ile ilgili kod örnekleri ve interaktif görselleştirme araçlarının yanında detaylı analiz içeren Robert Elder’ın bloğunu okumanızı ve grafikler üzerinde oynama yapmanızı şiddetle tavsiye ederim.
Detaya inmek isteyenler için önerilerim:
— Longest common subsequence problem
— The Myers diff algorithm by James Coglan
— Myers Difference Algorithm by Raywenderlich
— Diff algorithms by Elvis Pfützenreuter
— Investigating Myers’ diff algorithm by Nicholas Butler
— Video severler için Türkçe örnek çözüm videosu: LCS Algoritması - Longest Common Subsequences
— Video severler için Dynamic Programming kullanılarak LCS mantığını anlatan bir video: Longest Common Subsequence (2 Strings) — Dynamic Programming & Competing Subproblems
