Wagner-Fischer Algoritması

Merhabalar. İlk Medium yazımda String Matching (Dizgi Eşleme), Approximate String Matching (Yaklaşık Dizgi Eşleme), Levenshtein Uzaklığı ve bu uzaklığı hesaplamak için kullanılan Wagner-Fischer Algoritmasını anlatacağım. Dinamik Programlama ve Memoization konularına değineceğiz.

Siz de bir geliştirici iseniz- bu yazıyı okuyorsanız programlama bildiğinizi varsıyıyorum :)- programlama kariyerinizin bir yerinde aşağıdakine benzer bir karşılaştırma yaptığınızı düşünüyorum.

Yukarıda bir isim veritabanı içindeki isimlerle bir sorgu kelimesini (kullanıcı formundan gelen veri gibi) karşılaştırdık. Bu çok temel düzeyde bir işlem fakat burada gözden kaçırılan nokta kullanıcının mükemmel olmadığı. Arama gibi işlemler yaparken yanlış tuşa basıp istediğimizi yazamadığımız zaman aşağıdaki örnektekine benzer bir durumla karşılaşıyoruz.

Günlük hayatta kullandığımız bir çok site bu tip durumlarda bile sonuç ekranında karşımıza aslında aramak istediğimiz şeyi çıkarıyor. Bunu yapabilmelerini sağlayan şey bu yazının asıl konusu olan Approximate String Matching (Yaklaşık Dizgi Eşleme) algoritmaları.


Teorik Arkaplan

Levenshtein Uzaklığı

Uzaklık günlük hayatta iki yer arasındaki mesafe için sıkça kullandığımız bir kavram. Dizgi eşleme bağlamında ise uzaklık iki dizginin(String) birbirinden ne kadar uzak olduğunun ölçüsüdür. Değişik ölçü birimleri olmasına rağmen Levenshtein’ın tanımladığı kendi ismiyle anılan Levenshtein Uzaklığı aralarında en popüleridir.

Levenshtein’a göre iki dizgi arasındaki uzaklığı belirlemek için yapılabilecek işlemler ve maliyetleri şunlardır:

  • Ekleme: “kale” => “kalem” . ‘m’ karakteri eklendi. Maliyeti: 1
  • Çıkarma: “oklul” => “okul” . ‘l’ karakteri çıkarıldı. Maliyeti: 1
  • Değiştirme: “blog” => “blok”. ‘g’ yerine ‘k’ koyuldu. Maliyeti: 2

Değiştirme işleminin maliyetinin farklı olmasının sebebi aslında işlemin sırasıyla çıkarma ve ekleme işlemlerinden oluşmasıdır.

Minimum Uzaklık Problemi

İki dizgi arasındaki mümkün olan en kısa uzaklığı bulma problemidir. Yukarıda verilen kurallar doğrultusunda recursive bir şekilde ifade edilen çağrılarla olabilecek bütün durumlarda oluşan distancelar karşılaştırılmak suretiyle minimum uzaklık aşağıdaki kod örneğinde görüldüğü gibi hesaplanabilir.

Rekürsif Minimum Uzaklık Hesabı(Levenshtein Formülünü kullanarak)

Dinamik Programlama ?

Dinamik programlama özellikle Competitive Programming(Rekabetçi Programlama) çevrelerince sıkça kullanılan bir programlama yaklaşımı. Dinamik programlama her ne kadar daha derin bir teorik arkaplana sahipse de bizim bu yazı için odağımız çıkış noktası, memoization -memorization değil bu arada yazım hatası yok yani- tekniği ve pratikte nasıl uygulanacağı.

Klasik recursion ile Fibonacci sayıları

Dinamik programlama tekniğini var oluş sebebi klasik recursion tekniğindeki bir eksiklikten kaynaklanıyor. Bu eksikliği aşağıdaki diyagramda gözlemleyelim:

Fibonacci Algoritması Görselleştirmesi (https://visualgo.net/en/recursion kaynağından alındı.)

Fibonacci algoritmasının görselleştirilmiş halinde nasıl hız arttırımı yapabileceğimiz hakkında kafa yoralım. Toplamda 15 fonskiyon çağrısı var ve recursive Fibonaccide her çağrı Büyük-O gösteriminde(Big O Notation) O(1) yani constant sürede gerçekleşiyor.

Hız arttırımı gerçekleştirmede ilk kullanılan taktiklerden biri Hesaplamadaki Gereksizliklerden(Computational Redundancy) kurtulmaktır. Diyagrama baktığınızda

  • fib(5): 1 kere
  • fib(4): 1 kere
  • fib(3): 2 kere
  • fib(2): 3 kere
  • fib(1) ve fib(0): 8 kere

çağırılmış. Bu da demek oluyor ki aynı şeyleri cevabını önceden bildiğimiz halde tekrar tekrar hesaplamışız. Bu “gereksiz” hesaplardan kurtulmak için yapmamız gereken nedir? Biraz tecrübeli arkadaşlar içgüdüsel olarak “cache” mantığını kullanıp “sonuçları saklamayı” düşündüler. Memoization yaklaşımının çıkış noktası da budur. Aynı rekursif fonksiyonu tekrar tekrar çağırmak yerine bir kere çağrıyı yaptıktan sonra sonuçları bir arrayde saklayıp tekrar aynı çağrı yapıldığında sakladığımız array indeksinden sonuçları alalım ve böylece performans artışı sağlayalım:

Memoization ile Fibonacci Serisi

Yukarıda n+1 uzunluğunda bir array içinde önceden elde ettiğimiz sonuçları tuttuk. Eğer array içindeyse oradaki sonucu döndürüyoruz. Array içinde değilse recursive çağrılardan gelen sonuçları bir başka hesaplamada kullanmak üzere array’e kaydediyoruz. Peki bunu yaparak nasıl bir performans artışı sağladık beraber görelim:

Gördüğünüz gibi memoization vasıtası ile optimize edilmemiş kod Fibonacci(20)’yi hesapladığı halde 84 ms çalışma zamanına sahip iken Fibonacci(600)’ü hesaplayan optimize kod 8 ms kadar sürede hesaplamayı bitirdi. Dinamik programlamanın üç temel taşından¹ olan Memoization yöntemi bize basit bir problemde bile muazzam performans artışı sağladı. Şimdi öğrendiğimiz Levenshtein Minimum Distance yöntemi -ki kendisi rekursif bir fonksiyon aslında- ile Memoization tekniğinin birleştiği Wagner-Fischer Algoritmasını inceleyelim.

¹ Diğer ikisi Overlapping Subproblems ve Optimal Substructure’dır.

Python’ın Memoization Desteği (Meraklısına)

Fonksiyonel programlama dillerinin en büyük avantajlarından biri built-in (dille birlikte gelen, ekstra olmayan) memoization desteklerinin olması. Python’a bir hayli geç -3.2 sürümünde- gelen bu özellik diğer fonksiyonel programlama eklentileriyle birlikte functools modülünde bulunuyor. Python bu özelliği bir LRU Cache² vasıtasıyla gerçeklemiş.

Halihazırda varolan LRU Cache ile Otomatik Memoization ve Performansı

Kendi elimizle yaptığımız memoization kadar optimize değil fakat bir fonksiyon için elle memoization yazmak ile uğraşmak istemediğinizde lru_cache dekoratörü³ ile kolayca daha hızlı çalışan kod yazabilirsiniz.

² LRU Cache: Ünlü bir cacheleme yöntemi Bellek Allokasyonu ile ilgili problemlerde etkili bir yöntem. Sınırlı bir belleğiniz varsa -ki var- LRU Cache sıkça kullanılan objeleri bellekte tutarken daha az kullanılanlar ikincil bellekte(HDD/SSD) tutulur. Böylece sıkça kullanılan ögelere bellekten hızlı erişim sağlanır ve performans artar.

³ Dekoratör: OOP tasarımda sınıfların iç yapılarını bozmadan onlara ekstra özellikler eklemeye yarayan “Tasarım Deseni”dir.


Wagner-Fischer Algoritması

Yazının burasına kadar geldiyseniz öncelikle tebrikler :)

Yukarıda anlatılanları özümsediyseniz zaten Wagner ve Fischer adlı akademisyen abilerimizin ne yaptığını anlamışsınızdır. Ekstra bir özellik eklemeden yukarıda anlattığımız rekursif fonksiyona memoization katarak hızlandırmış ve bununla ilgili bir makale yazarak -1974 yılında- kendilerine önemli bir yer edinmişlerdir.

Wagner-Fischer Python gerçeklemesi

Performans Analizi

Performans arttırımının Fibonacci’deki gibi muazzam olmasını bekliyoruz. Bunu test etmek için bir Lorem Ipsum generatordan aldığım stringin bazı harflerini ‘k’ ile değiştirdim ve orijinal ile bu stringi algoritmaya soktum. Sonuçlar aşağıda gördüğünüz gibi:

Normal Recursion ile Wagner-Fischer hız farkı

Görüldüğü üzere Wagner-Fischer yaklaşık 100 elemanlı iki stringi normal recursion kullanan ilk algoritmamızın 5 harfli bir stringi karşılaştırdığı sürede -52 ms- karşılaştırıyor.

Özet

İnternet arama motorlarının, Kelime İşleme programlarının ve imla denetimi programlarının kullandığı ASM algoritmalarından en kolay anlaşılanı olan Wagner-Fischer’ı inceledik. Brute-Force Recursion’ın dinamik programlamaya göre nasıl geride kaldığını bu vesileyle öğrenmiş olduk. Dinamik programlamayı ve Memoization tekniğini nasıl uygulayacağımız hakkında bilgi edindik.

Ekstralar

python-Levenshtein Modülü

Bütün bunlarla uğraşmak istemiyorsanız kurabileceğiniz bir Levenshtein distance modülü var ve C tabanlı olduğu için bizim yazdığımız koda göre çok çok daha hızlı çalışıyor. Her ne kadar aktif devam ettirilen bir paket olmasa da daha çok test edilmiş ve daha hızlı olduğu için her durumda bizim kodumuzdan daha iyi.