Good suffix rule (Boyer-Moore algoritması)

Boyer-Moore metin arama algoritması serisinde öğrenmeye çalışacağım ikinci algoritma good suffix rule adı altında biliniyor. Aranan metnin ne kadar sağa kayrıdılacağını belirleyen iki kuralın ikincisi ve diğer yöntemden (bad character rule) biraz daha karışıkmış.

Bad character kuralında sadece uyumsuzluk olan noktadaki karaktere bakmıştık. Bu sefer uyumsuzluğun olduğu noktadan önceki sonek kısmına bakacağım, çünkü aranan metni uyumsuz noktanın sağındaki karakterler de birbirine uymazken, sadece uyumsuzluk olan yerdeki karakterin doğru olacağı şekilde kaydırmak yeterli olmayacaktır. Yani bu şekilde bir kaydırmada aranan metnin bulunamayacağı açıktır.

Örneğin aradığımız metin HAABH ise ve aşağıdaki bir durum oluşmuşsa algoritmamız sağdan sola doğru karakterleri kontrol edecek ve en sondaki BH kısmının uyduğunu ve sonraki konumdaki H ve A karakterlerinin uyumsuz olduğunu görecek.

... A B A B H A A H B H ...
              H A A B H

Bu durumda daha önceden anlattığım bad character kuralı aranan metni sadece iki karakter sağa kaydırmayı teklif edecek, çünkü bir sonraki H karakteri iki karakter daha solda.

... A B A B H A A H B H ...
                  H A A B H

Burada ana metindeki sonekin (BH) aranan metinde eşleşen kısımdaki altmetne (AA) uymadığını kolayca görebiliriz. Demek ki bad character kuralı bize kaydırma miktarıyla ilgili yeterli bilgi vermiyormuş. Bu bilgiyi kullanmanın yolu da sonekin aranan metinde daha solda mevcut olup olmadığını kontrol etmek. Eğer varsa bu daha soldaki sonekle uyuşan kısmı ana metindeki sonekin altına getirecek kadar kaydırmak yeterli olabilir. Tabii ki bu noktada küçük bir optimizasyon yapmayı da düşünebiliriz. Örneğin son ekten hemen sonraki uyumsuz karakteri de aranan metindeki bir sonekle uyuşan bir sonraki altmetnin hemen sonunda arayabiliriz ama burada küçük bir sorun karşımıza çıkacak gibi. Hedefimiz sadece aranan metni kullanarak bu kaydırma miktarlarını hesaplamak, böylece aramaya başlamadan önce bir kereliğine bütün bu hesaplamaları yapabiliriz. Elimizde sadece aranan metin varsa da o uyumsuz noktada (yani sonekin hemen solundaki konum) hangi karakterin olduğunu henüz bilmiyoruz. Evet bu ciddi bir engel ama bunu aşmak için o noktada uyumsuz olabilecek bütün karakterler için bu hesapları bir kereliğine yapabiliriz. Buradaki sorun da hem bu bir kerelik işlemin oldukça uzun sürmesi hem de bütün bu bilgiler için hafızada çok fazla yer tutmamızın gerekmesi olacaktır. Bunun yerine çok daha basit bir bilgiyi kullanarak bazı durumlarda işimize yarayacak bir optimizasyon elde edebiliriz ama. O da, aranan metindeki daha soldaki sonek tekrarını ararken bulduğumuz altmetnin solundaki karakterin aranan metinde uyumsuzluğun olduğu karakterden farklı olup olmadığına bakabiliriz. Eğer aynıysa bu altmetin işimize yaramayacaktır çünkü altmetni kaydırdığımız zaman aynı uyumsuzluğu aynı yerde bir kere daha bulacağız. Örneğin aradığımız metnin BABHAABH olduğunu varsayalım ve aşağıdaki durumu inceleyelim.

... A B A B H A A H B H ...
        B A B H A A B H

Sağdan sola baktığımızda bulduğumuz uyumsuzluk üçüncü konumda (H ve A) ve sonekimiz BH. BH dizisini aranan metinde solda aradığımız zaman bir kere daha buluyoruz ama BH’nın hemen solundaki karakter en sonda olduğu gibi yine A. Bu durumda sonekleri altalta gelecek şekilde kaydırırsak aşağıdaki durumu elde edeceğimiz açık.

... A B A B H A A H B H ...
                B A B H A A B H

Yani aynı konumda yine aynı uyumsuzluğu (H ve A) elde edeceğiz. Bu uyumsuzluğun ana metindeki H karakterinden bağımsız olacağına dikkat edelim. Yani soneki aranan metinde sola doğru ararken bu sonekin hemen solundaki karakterin farklı bir karakter olmasına dikkat etmeliyiz. Aynı karakter ise aramaya devam edeceğiz, farklı ise aradığımız kaydırma miktarını bulduk diyeceğiz.

Bu linkte burada anlamaya çalıştığım algoritma için gerken tabloyu hesaplayan bir simulasyon hazırladım.

Knuth-Morris-Pratt algoritması

Bu algoritma failure function yazısında oluşturduğumuz tabloyu kullanarak aradığımız metni uyumsuzluğun olduğu konuma göre değişik miktarlarda kaydırmaktadır. Bu şekilde aranan metni her adımda bir karakter kaydırma algoritmasına göre bir iyileştirme elde edeceğiz.

Aşağıdaki linkle animasyon sayfasına ulaşabilirsiniz. Sayfa yüklendiği zaman aranan metin için daha önceki yazıda tanımlanan tabloyu hesaplayacak. Ardından ana metni ve aranan metni gösterip uyumlu karakterleri yeşil renkle, uyumsuz olan ilk karakteri de kırmızı ile gösterecek. Ondan sonra uyumlu ortak metin uzunluğundan tabloda seçilen sütunu yeşi ile gösterip oradan kaydırma miktarını okuyacak. Aranan metin bu miktar kadar kaydırıldıktan sonra aynı işlemleri tekrarlıyor. Animasyon aranan metin bulunana kadar devam ediyor.

Animasyon

Failure Function

Bu seferki algoritma aslında yine başka bir algoritmada kullanılan bir parça olacak. Basit metin arama algoritmasında bulmak istediğimiz metin parçasını ana metin üzerinde her adımda bir karakter kaydırarak üst üste gelen harflerin aynı olup olmadığına bakıyorduk. Bu yazıda bakacağımız algoritma her adımda bir karakter kaydırma sorununa bir çözüm bulmaya çalışacak.

Aradığımız metin parçasındaki harflerin özelliklerini kullanarak bazen birden fazla karakter kaydırma imkanını elde edebiliriz. Yani karakterleri karşılaştırırken fark olan ilk konuma kadar olan karakterlere göre birer karakter kaydırmanın bu başlangıç kısmında bir eşitlik yaratamayacağından emin olabilirsek bundan faydalanarak kaydırma adımını hızlandırabiliriz. Hedefimiz şu: Arama metnindeki ilk uyumsuzluğun konumuna göre kaç adım sıçrama yapmamız gerektiğini söyleyen bir tablo bulmak istiyoruz. Dolayısıyla normal arama işleminde yine karakterleri tek tek kontrol edeceğiz ama ilk farkta bu tablo bize bir sonraki arama için ne kadar sıçrama yapmamız gerektiğini (şansımız iyi giderse birden fazla) söyleyecek.

Wikipediadan aldığım bazı örnekleri vereyim şimdi.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

Burada ana metin S ile aradığımız metin de W ile gösterilmekte. Burada i = 3 indeksli karakter ilk uyumsuzluğun olduğu yer. Şimdi W ile gösterilen karakter dizisini birer birer sağa kaydıracağım ama bu sırada S karakter dizisinde algoritmanın henüz görmediği yerlere X koyacağım. Bu X koyulu yerlere karşılık gelecek W karakterlerini de kullanmaya gerek olmayacak çünkü bu karakterleri henüz görmediğimizden buralarda eşitlik olup olmadığını bilmiyoruz.

             1         2  
m: 01234567890123456789012
S: ABCXXXXXXXXXXXXXXXXXXXX
W:  ABC
i: 0123456

İlk kaydırmadan sonra ilk konumda (i = 1) bir eşitsizlik var. Daha bakmaya gerek yok, bir kere daha kaydıralım.

             1         2  
m: 01234567890123456789012
S: ABCXXXXXXXXXXXXXXXXXXXX
W:   ABC
i: 0123456

Yine W parçasının başı yukarıdaki S dizisinin bilinen kısmının sonuyla uyuşmadı. Demek ki bu diziyi iki adım kaydırmak da işe yaramayacak. O zaman aramaya 3 adım kaydırarak devam etmek lazım.

Bu örnekten sonra iki şeye dikkat çekmek istiyorum.

  1. Aradığımız şey aslında W dizisinin başındaki bir dizinin (önek) yine W dizisinin sonundaki bir diziyle (sonek) uyuşup uyuşmadığı. İlk X nerede olursa olsun oraya kadar S dizisiyle yine aynı konuma kadarki W dizileri aynı olduğundan yukarıdaki fikri kullanabiliriz.
  2. İlk bakışta yine her adımda W dizisinin bir önekini bir kaydırıp kontrol ediyoruz gibi görünüyor ve böylece aramada yine her seferinde W dizisini bir karakter kaydırıp basit arama algoritmasına döneceğiz gibi geliyor ama aslında bunu sadece örnek olarak verdim. İleride bu tabloyu aramadan önce sadece arama metnini kullanarak bir kereliğine oluşturabileceğimizi göreceğiz.

Örnek:

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

Burada ilk uyumsuzluk i = 6 konumunda oluşmuş. O zaman ana metinle aranan metin arasında i = 5 noktasına göre tam uyum vardır. O zaman aranan metnin o noktasına kadarki önekiyle ilgileneceğiz.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:            ABCDAB
i:            012345

Şimdi aranan metni birer kaydırdığımızda kendi önekiyle yine kendi soneki arasındaki uyumlara bakalım.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:             ABCDAB
i:            012345

i = 0 noktasında uyumsuzluk var. Yine kaydırmamız lazım.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:              ABCDAB
i:            012345

Uyumsuzluk devam ediyor. Yine kaydıracağız.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:               ABCDAB
i:            012345

Hala uyum bulunamadı. Kaydırmaya devam ediyoruz.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:                ABCDAB
i:            012345

Burada sonunda aranan W metninin iki karakterlik öneki ile yine W nin (tabii ki 6 karakterlik kısmı için, bu uzunluk en baştaki ilk uyumsuz nokta ile belirleniyor) iki karakterlik soneki arasında bir uyum bulundu. Demek ki tablomuzda ilk uyumsuzluk 6. konumda bulunursa 4. konuma kadar kaydırılmalı diye bir kayıt bulunmalı. Algoritma bu uyumsuzlukla karşılaştığında birer birer kaydırmak yerine hemen 4 karakter kaydırarak aradaki kontrolleri gönül rahatluğıyla atlayabilir.

Burada bir gözlemden daha bahsedeyim. Sağa doğru birer birer kaydırırken ilk uyumlu önnek, sonek çiftini bulduğumuzda kaydırmayı kesmemiz lazım. Yani en uyumlu olan en uzun önek, sonek çiftini arıyoruz. Bunun nedeni de aslında kolayca anlaşılabilir. Aranan metni kaydırdıkça bu metnin en son kısmı hep X ile gösterdiğimiz bölüme kayıyor, yani bu bölümde de uyumun devam etme hatta aranan metnin tamamının bulunma şansı var. Dolayısıyla bulunan ilk önek, sonek uyumunda durulmalı ki bu ihtimal gözden kaçırılmadan kontrol edilebilmeli.

Bir küçük nokta daha var ama onu zaten farketmişsinizdir. Önek ve soneklerin uyumuna bir kere kaydırdıktan sonra bakıyoruz. Kaydırmadan bakarsak her zaman uyumlu olurlar ve bu durumda algoritmamız kaydırmaya gerek yok diye saçma bir düşünceye kapılabilir.

Aşağıdaki linkten animasyon sayfasına girerek bu tablonun başta ana metne ihtiyaç duymadan nasıl hazırlandığını görebilirsiniz. Yani tabloyu arama algoritmasının en başında üretebiliriz ve sonra ana metinle beraber kolaylıkla kullanabiliriz. Bu kullanımı da başka bir yazı ve animasyonda göstereceğim.

Tablonun üzerindeki kısım önce indeks listesiyle başlıyor. İkinci satır ana metnin o ana kadar uyum sağlanmış kısmını gösteriyor. Bu farazi bir ana metin tabii ki, bütün işlemi aslında aranan metinde yapmama rağmen bu ana metin kısmını da göstermek istedim. Aranan metindeki uyumsuzluğun olduğu ilk nokta dolaylı olarak da ana metni o noktaya kadar belirlediği böylece daha kolay anlaşılır belki. Üçüncü satır aranan metnin tamamını gösteriyor. Son satır ise simulasyon sırasında kaydırılan kısmı gösteriyor. Yukarıdaki örneklerdeki W kısmı (ana metinle tam uyum sağlayan kısmı tabii ki) yani.

Tablonun başlık satırı indekslerden oluşuyor, yani yukarıdaki örneklerdeki i satırı. İkinci satır önek ve soneklerdeki en uzun uyumlu karakter dizisini gösteriyor. Son satır da algoritmanın indeks numaralı pozisyondaki uyumsuzluk için arama metnini kaç karakter kaydetmesi gerektiğini gösteriyor. Dikkat ederseniz index – maksimum uzunluk = kaydırma miktarı gibi bir eşitlik de var.

Simulasyon

Basit yazı arama algoritmsı

Uzunca bir metinde bir kelime aradığımız çok olmuştur. Bu aramalar için geliştirilmiş çok çeşitli algoritmalar var. Bu yazıda bu algoritmaların en basitinin simülasyonuyla ilgileneceğim.

Bu algoritmada metnin en başından başlanır ve harf harf kelime ve aranan kelime karşılaştırılır. Eğer karşılaştırılan harfler farklı ise aynı karşılaştırmaya metnin bir sonraki harfinden başlanır. Bu karşılaştırmalar ya metnin içinde bu kelime bulunana ya da metnin sonuna ulaşılana kadar devam edilir.

Simülasyon