Rabin-Karp Algoritması

Sıralama ya da string içinde arama gibi fonksiyonlar, kullanılan argümana bağlı olarak çalışma zamanı önemli ölçüde değişen fonksiyonlar. Bu gibi durumlarda framework'un kendi içinde bulunan metodlar yeterli olmayabiliyor. Misal Java, her ne kadar her durumda QuickSort kullanmak daha mantıklı gibi görünse de Object dizileri için MergeSort kullanıyor. MergeSort stable sıralama algoritması Object dizisinin önceki sıralamasını da bozmamış oluyor böylece.

String içinde arama (indexOf) fonksiyonunda ise Java'da naif yöntem denilen, \(O(nm)\)'lik yöntem kullanılıyor. Tam tasarım kararını bilmemekle beraber bu yöntemin herhangi bir ekstra bellek gerektirmemesi, ekstra hesaplamalar yapmaması, bu yüzden daha kolay bir çalışma zamanı hesabı olması belki sebep olabilir. Fakat pratikte, büyük String'lerle bu işlemi yapan bir sistemde bu metod biraz canınızı acıtabilir.

Bu arada naif yöntemin kodu da aşağıda görülebilir.

Buna alternatif olarak kullanılabilecek birkaç algoritma var. Bunlardan Aho-Corasick algoritması, her dakika kodlayabilmek ve sonraki yazılımcıya aktarabilmek için gereğinden fazla karmaşık bir algoritma. Knuth-Morris-Pratt ise, Rabin-Karp gibi yazması gayet basit ve çalışma zamanı efektif bir algoritma ama onu da kodunun daha uzun olması ve \(O(m)\) gibi bir ekstra bellek gereksinimi olması sebebiyle atlıyoruz :)

Rabin-Karp bu diğer iki algoritmadan daha basit bir çalışma mantığına sahip. Aslında algoritma, naif arama algoritmasının biraz daha akıllısı. Akıllı olduğu kısım ise "eşit String'leri tutarlı bir hash algoritmasından geçirirsek aynı değeri verirler" gibi bir mantığa dayanıyor.

Algoritmayı adım adım özetlersek

- İlk adımda, aranacak String'in bir hash değeri hesaplanır. Bu hash değerinin ne kadar ayırt edici olacağı bize kalmış bir şey. Genel yaklaşım olarak (Burada sadece küçük harfli İngilizce metinlerle uğraştığımızı düşünelim), maksimum değere yakın bir asal sayı ile her bir karakteri çarpıp toplama ekleyerek bu toplamı da başka bir sayıyla çarpabiliriz. Sonuç büyük olabileceği için büyük bir sayıya göre modunu alırsak yeterince iyi bir fonksiyon elde etmiş oluruz (En iyisini yapmak isteyenlere başlangıç noktası burası). Kodu aşağıdaki gibi bir şey olacak (hesabın rahatlığı için asal sayı kullanmadım).

- Sonraki adımlarda yine String'i naif yöntemdeki gibi dolaşıp arama yapacağız fakat burada her alt String'de arama yapmak yerine sadece hash değerleri \(h\)'ye eşit olan alt String'leri karşılaştıracağız. Hash fonksiyonumuzun "perfect" olmadığını varsayarak her eşleşen hash'te String'i bulduk diyemiyoruz o yüzden eşleşen hashleri bulduğumuzda bu iki String'i karşılaştırmak gerekecek.

ile içinde arama yapılacak String'in ilk \(m\) karakterinin hash değerini oluşturabiliriz. Aşağıdaki kod ile de iki eşit hash'e sahip stringi karşılaştırıyoruz.

- Baştaki \(1..m\) karakterlerini kontrol ettikten sonra \(2..m+1\) karakterlerini kontrol etmemiz gerekiyor. Bu karakterler için tekrar bir hash değeri hesaplamak gerekecek. Rabin-Karp'ın güzelliği, bu değeri baştan hesaplamadan, önceki değeri kullanarak bu işlemi yapacağız.

\(123123\) şeklinde bir String'in olduğunu ve bunun karakterlerini ikişer ikişer alıp ondalık değerlerini hesapladığımızı düşünelim. İlk iki karakter için bu değer

\[h_0 = 2 + 10*1\]

olacak. \(23\) için bu değeri hesaplarken aynı hesabı baştan yapmak yerine

\[h_1 = (h_0 - 10)*10 +3\]

işlemini kullanabiliriz. Burada yaptığımız işlem en yüksek basamağı sonuçtan çıkarıp sayıyı sola kaydırmak ve en sağdakini eklemek.

Bu işlem ile her seferinde \(O(m)\) adımlık bir hash maliyetinden kurtulmuş olduk.

Bu algoritmanın en iyi çalışma zamanı \(O(n-m)\) toplama işlemi ve \(O(m)\) ilk hash maliyeti ile toplamda kabaca \(O(n)\) (hash'in eşit olduğu durum olmaması koşulu). En kötü çalışma zamanı ise naif algoritmayla aynı yani \(O(nm)\).

Algoritmanın tam koduna buradan bakılabilir.

Matplotlib ile algoritma animasyonları

Matplotlib, kullanım kolaylığı, arayüzünün güzelliği ve en önemlisi bir Python kütüphanesi olması sebebiyle en sevdiğim kütüphanelerden bir tanesi :). Büyük boyutta veriyle çalışırken çok uygun olacağını düşünmüyorum fakat özellikle algoritma geliştirirken, küçük dataset'ler üzerinde denemeler yaparken gayet uygun.

Matplotlib'in grafik çizme dışındaki yeteneklerinden biri de animasyon oluşturabilmesi. Grafik çizerken yapılan işlerin aynısını matplotlib'in sağladığı bir callback mekanizması içinde yaparak istenilen parametreler ile animasyonlar oluşturulabiliyor.

Kullanılacak fonksiyonlar matplotlib.animation modülü içerisinde bulunuyor.

Sonrasında, pyplot ile bir figür nesnesi yaratıp bunu aşağıdaki gibi animasyona vermek gerekiyor

Buradaki değişkenlere bakacak olursak;

generate_random : Her bir adımda çağırılacak fonksiyon. Bu isim benim denediğim örnekte yazdığım bir fonksiyonun ismiydi yani matplotlib'e özel bir şey değil.

25 : Fonksiyonun kaç kez çağırılacağını belirten parametre.

fargs : Fonksiyon çağrısında fonksiyona geçilecek argümanlar.

interval : Fonksiyon çağrısının kaç milisaniyede bir yapılacağı.

blit : Fonksiyonun, çizilecek nesneleri bir iterator içinde dönüp dönmeyeceği.

Ben örnekte Metropolis Algoritması'nı uyguladım. Algoritma basitçe her adımda bir doğru oluşturup ekrana çiziyor. Bu fonksiyon aşağıdaki gibi.

blit = True  verdiğimiz için bu fonksiyon her seferinde geriye,  Line2D  nesnelerinden oluşan bir liste dönüyor ve her seferinde bu liste ekrana çiziliyor.

Animasyonu ekrana çizdirdiğimiz gibi çeşitli formatlarda dosyalara da kaydedebiliyoruz. Aşağıda görülen gif dosyasını kaydetmek için şöyle bir kod yazmak gerekiyor;

Oluşan animasyon ise şöyle bir şey :)

animation

 

Örnek koda şuradan ulaşılabilir.