Bu yazı ve algoritma dizisinde de metin arama algoritmalarından Boyer-Moore algoritmasını öğrenmeye çalışacağım. Diğer bazı metin arama algoritmalarında olduğu gibi bu algortimada da aranan metin her adımda tek adım kaydırılmıyor, aksine aranan metnin özelliğine göre kaydırma miktarları optimize ediliyor. Boyer-Moore algoritmasının şimdiye kadar öğrendiğim algoritmalara göre iki farklı özelliği var. Birincisi, aranan metin ve ana metin karşılaştırması sağdan sola doğru yapılıyor. İkincisi de kaydırma miktarını bulmak için iki değişik alt algoritma kullanılıyor. Bu yazıda bu iki algoritmadan biri olan Bad Character algoritmasını anlamaya çalışacağım.
Bu algoritma için aşağıdaki animasyonu programlamaya çalıştım.
Bu animasyon başlatıldığında henüz hazırlanmamış bir tablo ve tablonun üzerinde seçilmiş bir aranan metin gösteriliyor. Tabloda normalde bir metinde olabilecek bütün karakterler olmalı (küçük harfler, büyük harfler, rakamlar vb.) ama sadece fikri gösterebilmek için tabloyu küçük tuttum. Animasyonda ana metni kullanmadım çünkü bu algoritma için ana metin değil aranan metne herhangi bir konumda uymayan bir karakter önemli. Bunu da aranan metnin üzerinde hesaplanacak konumda gösterilen bir karakterle göstermeye çalıştım.
Animasyonda aranan metin olarak
NNAAMAN
dizisini kullandım. Her tablo seçilen aranan metne göre ayrı oluşturulması gerekiyor. Tabloyu şöyle düşünmeye çalıştım. Aranan metinde ana metni sağdan sola doğru karşılaştırdığımızda ana metindeki ilk uyumsuz karakteri en soldaki sütundan buluyoruz. Ardından bu uyumsuzluğun aranan metindeki hangi pozisyonda olduğunu da birinci satırdan okuyoruz. Algoritma bittiğinde bu tablo bize o karakter ve o konum için aranan metni sağa doğru kaç karakter kaydırabileceğimizi söyleyecek.
Bu tabloyu hazırlamak aslında çok kolay ama bu şekliyle tablo oldukça fazla yer tutmakta, çünkü olası her karakter için tabloda yer harcanıyor ama bu ilk versiyon için bu basit yöntemi anlamak yeterliydi benim için. Literatürde bu sorunla ilgili çeşitli çözümler var ve ileride onlara da bakabilirim.
Tablodan sırayla her satırdaki harf için olası her pozisyonu alıyorum ve bu harfi aranan metnin üzerinde o pozisyonda gösteriyorum. Eğer seçtiğim harfler aranan metindeki harf aynı ise tabloda bu noktaya “-” işareti koyuyorum, çünkü bu algoritma sadece uyumsuzluk varken kullanılıyor. Eğer uyumsuzluk varsa aranan metinde sola doğru harfleri tek tek kontrol ediyorum. Seçilen harfle aynı harfi ilk bulduğum konuma kadar aranan metni sağa doğru kaydırabilirim, çünkü aradaki her durumda bir uyumsuzluğun çıkacağı kesin. Eğer bir harfi uyumsuzluğun çıktığı konumdan sonra bir daha bulamazsam da aranan metni uyumsuzluktan bir sonraki konuma kadar kaydırabilirim. Bu şekilde her karakter ve konum için aranan metni ne kadar kaydırmam gerektiğini tabloya işliyorum. Bu şekilde bu basit algoritma da tabloyu oluşturmuş oluyor.