Myers Fark Algoritması: Metin Karşılaştırma Aslında Nasıl Çalışır?

`git diff` çalıştırdıysanız, bir kod inceleme aracı kullandıysanız veya modern yazılımda iki belgeyi karşılaştırdıysanız, neredeyse kesinlikle farkında olmadan Myers fark algoritmasını kullandınız. Eugene W. Myers tarafından 1986 yılında Algorithmica dergisinde yayımlanan "An O(ND) Difference Algorithm and Its Variations" (Bir O(ND) Fark Algoritması ve Çeşitlemeleri) başlıklı makale, Unix diff'ten GitHub'a ve LineDiff'e kadar her yerde metin karşılaştırması için standart haline gelen algoritmayı tanıttı.

Myers algoritmasının nasıl çalıştığını anlamak yalnızca entelektüel merakı tatmin etmekle kalmaz — fark araçlarının neden ürettikleri çıktıyı ürettiklerini ve bu süreçte hangi ödünleşimlerin yapıldığını anlamanıza da yardımcı olur.

**Fark Nedir?**

En temel hâliyle fark, şu sorunun yanıtıdır: A ve B adlı iki dizi verildiğinde, A'yı B'ye dönüştürmek için gereken minimum değişiklik kümesi nedir? Bir "değişiklik" ya ekleme (B'de olan ama A'da olmayan bir şeyi eklemek) ya da silme (A'da olan ama B'de olmayan bir şeyi kaldırmak) olabilir. Her iki dizide de aynı göreli sırada görünen değişmemiş öğeler — ortak alt dizi olarak adlandırılır.

Herhangi bir fark algoritmasının amacı, A ve B'nin En Uzun Ortak Alt Dizisini (LCS) bulmaktır; çünkü LCS'yi öğrendikten sonra, A'da olup LCS'de olmayan her şeyin silinmiş, B'de olup LCS'de olmayan her şeyin ise eklenmiş olması gerektiğini bilirsiniz.

**Düzenleme Grafiği**

Myers, fark sorununu görsel olarak bir ızgara üzerinde, genellikle düzenleme grafiği olarak adlandırılan bir yapıda temsil eder. x ekseninin A dizisindeki konumları (orijinal belge) ve y ekseninin B dizisindeki konumları (revize edilmiş belge) temsil ettiği bir ızgara hayal edin. Sol üst köşeden (0, 0) başlar ve sağ alt köşeye (|A|, |B|) ulaşmak istersiniz.

Bir adım sağa gitmek, A'dan bir öğeyi silmek anlamına gelir. Bir adım aşağı gitmek, B'den bir öğeyi eklemek anlamına gelir. Çapraz hareket etmek — aynı anda sağa ve aşağıya — her iki dizide de aynı olan bir öğeyi korumak anlamına gelir. Bu çapraz hareket ücretsizdir; yani bir düzenleme olarak sayılmaz.

A ve B arasındaki minimum düzenleme mesafesini bulmak, bu ızgaranın sol üst köşesinden sağ alt köşesine en kısa yolu bulmakla eşdeğerdir; burada çapraz hareketler ücretsiz, yatay veya dikey hareketler ise birer düzenleme maliyeti taşır.

**En Kısa Düzenleme Betiği**

Bu en kısa yol boyunca gerçekleştirilen hareketlerin dizisine En Kısa Düzenleme Betiği (SES) denir. Myers algoritması, SES'i ızgaradaki her olası yolu keşfetmeden verimli biçimde bulur — bu, herhangi bir gerçek dünya belgesi için hesaplama açısından çözümsüz olurdu.

Myers'ın makalesindeki temel kavrayış, düzenleme grafiğini açgözlü, diyagonal öncelikli bir şekilde aramaktır. Başlangıç köşesinden genişlik öncelikli arama yapmak yerine algoritma, d=0'dan başlayarak artırılan her d düzenleme mesafesi için en uzağa ulaşan yolları izler. Her d için, en fazla d düzenleme kullanarak her k köşegeninde (k = x - y) ulaşılabilen en uzak noktayı bulur. Çapraz yollar, bir sonraki düzenleme sayılmadan önce mümkün olduğunca uzağa genişletilir.

**O(ND) Karmaşıklığı**

Algoritma O(ND) sürede çalışır; N, A ve B'nin uzunluklarının toplamı, D ise SES'teki düzenleme sayısıdır. Bu neredeyse optimaldir: D küçük olduğunda (iki belge çoğunlukla aynıysa), algoritma son derece hızlıdır. D büyük olduğunda (iki belge çok farklıysa), daha uzun sürer — ancak bu durumda temelde daha fazla iş yapılması gerekir ve hiçbir algoritma bundan kaçınamaz.

Pratikte, tipik belge karşılaştırmaları için — bir politika belgesinin iki versiyonu, bir sözleşmenin iki taslağı, iki yapılandırma dosyası — D, N'ye kıyasla küçüktür ve Myers algoritması son derece hızlıdır. LineDiff'te büyük belgelerin (100+ sayfa) bile milisaniyeler içinde sonuç üretmesinin nedeni budur.

**Anlamsal Temizlik**

Myers algoritmasının ham çıktısı sözdizimsel olarak optimaldir — en kısa düzenleme betiğini üretir — ancak insan okuyucular için her zaman anlamsal olarak optimal değildir. Bir cümlenin yarısının silindiğini ve yeni bir yarı cümlenin eklendiğini gösteren bir farkı düşünün; oysa bir insan okuyucu bunu doğal olarak "cümle yeniden yazıldı" şeklinde tanımlar. Myers'ın algoritması cümlenin ne olduğunu bilmez; yalnızca kendisine verilen karakter veya satır dizisi hakkında bilgi sahibidir.

Çoğu fark aracı, çekirdek algoritmayı çalıştırdıktan sonra anlamsal bir temizlik geçişi uygular. Bu geçiş, ham eklemeleri ve silmeleri doğal dil sınırlarıyla — kelime sınırları, cümle sınırları, paragraf sınırları — hizalamak için yeniden düzenler ve temel düzenleme kümesini değiştirmeden insanların yorumlaması için daha kolay bir fark üretir.

**LineDiff Myers'ı Web Çalışanlarında Nasıl Uyguluyor?**

LineDiff, fark hesaplamasını ayrılmış bir Web Çalışanı iş parçacığında yürütür. Bu, kullanıcı deneyimi açısından kritiktir: Myers algoritması hızlı olsa da, büyük belgeler için onlarca milisaniye sürebilir. Ana tarayıcı iş parçacığında çalıştırmak, kullanıcı arayüzünü engellerdi — fark hesaplanırken sayfa donardı. Hesaplamayı bir çalışana devrederek LineDiff, arayüzü duyarlı tutar ve fark tamamlanırken hatta aşamalı sonuçlar gösterebilir.

Çalışan, iki belgeyi dize olarak alır, satırlara (satır düzeyindeki farklar için) veya kelimelere (satır içi farklar için) dönüştürür, Myers algoritmasını çalıştırır, anlamsal temizliği uygular ve açıklamalı fark sonucunu ana iş parçacığına döndürür. Tüm ardışık düzen, 10.000 satıra kadar belgeler için genellikle 100 milisaniyenin altında tamamlanır.

**Üstüne Gelen AI Katmanı**

Myers, sözdizimsel gerçeği verir: tam olarak hangi karakterlerin değiştiğini. Anlamsal anlamı vermez: bu değişikliklerin bağlamda ne anlama geldiğini. LineDiff'in AI analiz katmanı burada değer katar.

Myers farkı hesaplandıktan sonra LineDiff, isteğe bağlı olarak değişiklik kümesini bir LLM'ye gönderir (varsayılan olarak GPT-4o veya BYOK aracılığıyla kendi OpenAI anahtarınız). AI, ham belgeler değil, yapılandırılmış farkı alır ve alana özgü bir analiz üretir: hangi değişikliklerin önemli olduğu, hangilerinin kozmetik olduğu ve revizyonun genel etkisinin ne olduğu.

Hukuki bir belge için AI, gramer açısından netlik için eklenen bir virgül ile bir tarafın yükümlülüklerini önemli ölçüde değiştiren bir madde arasında ayrım yapar. Mali bir rapor için, sayısal değerlerdeki değişiklikler ile anlatı yorumundaki değişiklikler işaretlenir. Klinik bir protokol için dozaj ve uygunluk değişiklikleri ile idari ev düzenlemesi vurgulanır.

Myers algoritması neyin değiştiğini söyler. AI ise bunun neden önemli olduğunu. Birlikte, LineDiff'i yalnızca bir fark aracından daha fazlası haline getirirler — bilgisayar biliminin en temel problemlerinden birine en iyi çözüm olmayı sürdüren 40 yıllık bir algoritma üzerine inşa edilmiş bir belge zekâsı platformu.