Metin arama (text search), büyük bir metnin içinde bir karakter dizisinin aranması işlemidir. Klasik arama yönteminde anahtar kelime tam metinle sol taraftan aynı hizaya alınır. Eğer ilk harfler eşleşiyorsa sıradakilere bakılır. Eşleşme sağlanmadığında anahtar kelime bir sağa kaydırılarak tekrar kontrol edilir.
Örneğin, BABABANABAKSANA metninde AKSA anahtar kelimesi aranıyorsa algoritma aşağıdaki gibi çalışır:
İlk karakter eşleşmediği için anahtar kelime bir karakter sağa kaydırılır:
Bu adımda ilk karakter eşleşti. Bu durumda anahtar kelimenin ikinci karakteri ile metnin karşılık gelen karakteri karşılaştırılır:
İkinci karakter eşleşmediği için anahtar kelime yine bir karakter kadar sağa kaydırılır:
Arama işlemi yukarıdaki adımların devamı şeklinde anahtar kelime bulunana kadar veya tam metnin sonuna gelinene kadar devam eder. Özellikle büyük metinlerin (kitap, pdf, word dosyası gibi) içinde küçük karakter dizilerini aramak bu yöntemle oldukça fazla işlem yükü getirir. Bu nedenle metin araması için daha gelişmiş algoritmalar kullanılır. Bu algoritmalardan biri Boyer Moore Algoritmasıdır.
Boyer Moore Algoritması’nda anahtar kelime için bad match (eşleşmeme) tablosu oluşturulur. Tablo, anahtar kelimenin her harfi için bir sütun içerir fakat anahtar kelimede tekrarlanan karakterler için yeni bir sütun eklenmez.
bad match tablosunun yapısı
Bad match tablosu oluştururken aşağıdaki adımlar uygulanır:
- Her karakter için: değer = anahtar uzunluğu – indeks no – 1
- Son karakter önceden hesaplandıysa olduğu gibi bırak. Hesaplanmadıysa değer = anahtar uzunluğu
- Anahtar dışında kalan tüm karakterler (* sütunu) için değer = anahtar uzunluğu
- Aynı karakter tekrar geldiyse (son karakter hariç) tabloya yeni değeri ekleyerek güncelle.
Bad match tablosu oluşturulduktan sonra anahtar kelime tam metnin altına en soldan yerleştirilir ve anahtar kelimenin en sağdaki karakteri ile tam metnin ona karşılık gelen karakteri karşılaştırılır.
- Eşitlik varsa bir soldaki karakterler karşılaştırılır.
- Eşitlik yoksa tam metnin kontrol edilen karakterinin tablodaki değeri kadar anahtar kelime sağa kaydırılır.
Örneğin, BABABANABAKSANA metninde AKSA ifadesi aranıyor olsun. Anahtar kelimenin her karakterinin indeks numaraları:
Her karakter için tabloya yazılacak değerler:
Bad match tablosu:
İlk adımda anahtar kelime tam metnin altına en soldan yerleştirilir. Anahtar kelimenin en sağındaki karakter ile ona karşılık gelen tam metin karakteri karşılaştırılır:
İlk karşılaştırmada eşleşme var. Bu durumda sağdan ikinci karakterler karşılaştırılır:
İkinci karakterler eşleşmedi. Bu durumda bu adımda tam metnin ilk karşılaştırılan karakteri olan A karakteri bad match tablosunda aranır ve anahtar kelime bu karakterin tablodaki değeri kadar, yani 3 birim sağa kaydırılır:
Bu adımda sağdaki ilk karakterler eşleşmedi. Tam metnin eşleşmeyen karakteri olan N karakteri bad match tablosunda aranır. Bu karakter tabloda olmadığı için anahtar kelime diğer (*) sütunundaki kadar, yani 4 karakter sağa kaydırılır ve tekrar karşılaştırma yapılır:
Sağdaki karakterler eşleşmedi. Bu durumda anahtar, tam metinde eşleşmeyen K karakterinin bad match tablosundaki değeri kadar, yani 2 karakter sağa kaydırılır:
Anahtar kelimenin sağından sola doğru karakterler karşılaştırıldığında eşitlik tespit edildi. Anahtarın yeri bulundu. Açıkça görülüyor ki bu arama işlemi klasik yaklaşım ile yapılsaydı çok daha fazla sayıda işlem yapılacaktı.