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.