Yazan : Şadi Evren ŞEKER

İçerik
Algoritmanın çalışması
Örnek çalışma
Tek harfli atlama tabloları
Gelişmiş atlama tabloları
Algoritma performansı

Bir metin veya hedef dizgi (string) içerisinde bir başka dizginin (string) aranması sırasında kullanılan algoritmalardan birisidir. KMP (Knuth Morris Prat) algoritması ile birlikte en çok kullanılan arama algoritmalarındandır.

Bu algoritmadaki amaç bütün harfleri teker teker kontrol eden doğrusal aramadan (linear search) daha iyi bir sonuç elde etmektir.

Algoritmanın çalışması

BM algoritması basitçe aranan metni hedef metin ile eşleştirir. Bulduğu sonuca göre de atlama gerçekleştirir. Ayrıca aranan metne göre de bir atlama tablosu (jump table) tutarak işlemi hızlandırır.

Bu atlama işlemini bir örnek üzerinden anlamak daha kolay olacaktır.

Örnek çalışma

Örneğin hedef metin olarak:

XXXBCDŞADEFABŞADI

Aranan kelime olarak da :

ŞADI

kelimesini ele alalım. İlk karşılaştırılma işlemi sonucunda şayet Ş,A,D,I harflerinden birisi hedef metinde yer almıyorsa ilk 4 harfin kontrol edilmesi tamamlanmış ve 4 harf kaydırılabilir demektir.

Yani aşağıdaki kaydırma ve kontrol adımlarının tamamından tek seferde kurulunabilir:

XXXBCDŞADEFABŞADI
ŞADI
XXXBCDŞADEFABŞADI
 ŞADI
XXXBCDŞADEFABŞADI
  ŞADI
XXXBCDŞADEFABŞADI
   ŞADI
XXXBCDŞADEFABŞADI
    ŞADI

Yukarıdaki işlemlerin tek seferde anlaşılması mümkündür çünkü ilk karşılaştırma işlemi sırasında aranan metin boyutu (örnekte 4 harfli ŞADI kelimesi alınmıştır) kadar karşılaştırma yapılmış ve hiç Ş harfi bulunmamıştır. Dolayısıyla hedef metin içerisinde aranan metnin bulunma ihtimali yoktur.

Örnek ilkel atlama tablosu

Yukarıdaki örnekten yola çıkarak aşağıdaki tek harfli atlama tablosu oluşturulabilir.

I 0
D 1
A 2
Ş 3
Diğer bütün karakterler için 4

Yukarıdaki tablodan da görüleceği üzere şayet karşılaştırma sonucunda yukarıdaki harflerden birisine rastlanırsa verilen karakter sayısı kadar kaydırma işlemi gerçekleştirilir. Örneğin aşağıdaki şekilde karşılaştırma yapıldığını varsayalım:

XXXBCDŞADEFABŞADI
  ŞADI

Yukarıda görüldüğü üzere D harfi aranan metin içerisinde tespit edilmiştir. bu durumda tek kaydırma işlemi yapılabilir ve aşağıdaki durum kontrol edilir

XXXBCDŞADEFABŞADI
  ŞADI

Benzer şekilde aşağıdaki durumda A harfine rastlandığı için 2 karakter kaydırma işlemi gerçekleştirilir.

XXXBCDŞADEFABŞADI
        ŞADI

Bu tablolama tek harf için çalışmaktadır ve örneklerden de anlaşılacağı üzere bir harfe konsantre olunduğunda zaman kazandırmakta ancak yine de gereksiz arama işlemiyle vakit kaybetmektedir. Örneğin yukarıdaki son örnekte A harflerini alt alta getirmek için aranan kelime 2 karakter kaydırılmıştır ancak burada aranan kelimenin olmadığı açıktır çünkü hedef metinde A harfinden hemen önce F harfi bulunmaktadır bu durum da aranan kelimenin olmasını engellemektedir.

Daha gelişmiş atlama tabloları

Yukarıdaki tek harfli atlama tablolarından anlaşılacağı üzere tek harfin kontrolü bazı durumlarda zaman kaybına sebep olmaktadır. Daha kesin bir çözüm alt kelime içeren tablolar hazırlanarak elde edilebilir.

Örneğin yukarıdaki örnek aranan metin için aşağıdaki tablo hazırlanabilir:

I 0
DI 1
ADI 2
ŞADI 3
Diğer bütün karakterler için 4

Yukarıdaki tabloda yeni olan sondan bakılan harf sayısıdır. Bu sayılar metnin karşılaştırılması sırasında çeşitli durumlarda ne kadar atlanacağını vermektedir.

Algoritma performansı

Algoritma performansı doğrusal aramada aranan kelime uzunluğu (a) ile hedef kelime uzunluğu (h) çarpımıdır: ha

Ancak BM algoritaması burada devreye girerek aranan kelimenin bütün harflerinin kontrolünü her seferinde engellemektedir. Bu yüzden algoritma başarısı h olarak indirgenebilir. dolayısıyla doğrusal hıza sahip olunur ve O(n) ile ifade edilebilir.

Yorumlar

  1. Ömer

    Merhaba;
    1-linear search
    2-boyer-moore search
    3-knut morris prat alg..
    4-bruteforce search

    acaba bu algoritmalar arasında hangisi en etkin algoritmadır?(string içinde kelime aramak için)
    ve 3. algoritmanın örnek kodu varsa ve paylaşırsanız sevinirim.
    kolay gelsin.teşekkürler...

  2. Şadi Evren ŞEKER Article Author

    Algoritmaların hepsi sitede anlatılmış durumda.

    Sizin de tahmin edeceğiniz üzere doğrusal arama (linear search) ve kaba kuvvet araması (bruteforce search) kmp ve bm algoritmalarına göre çok daha kötü çalışırlar.

    Kullanıldıkları ortama göre kmp algoritması ile bm algoritması farklı durumlarda avantajlı olabilir. Karşılaştırabilmeniz için kmp algoritmasının bağlantısını aşağıda veriyorum.

    http://www.bilgisayarkavramlari.com/2009/04/11/knuth-morris-prat-algoritmasi-kmp-algorithm/

    başarılar

  3. veli

    bu algoritma anlatımı hic degil sahsen hicbirşey anlamadım..örnek net birşey ifade etmiyor

    mesala aşagıya ekledigim kısımda kayma yok d icin 1 birim kayılmamış..ben birşey anlamadım şahsen

    XXXBCDŞADEFABŞADI
    ŞADI
    Yukarıda görüldüğü üzere D harfi aranan metin içerisinde tespit edilmiştir. bu durumda tek kaydırma işlemi yapılabilir ve aşağıdaki durum kontrol edilir

    XXXBCDŞADEFABŞADI
    ŞADI

  4. Şadi Evren ŞEKER Article Author

    Yukarıdaki örnekler, algoritmanın çalışması için verilmemiştir. Algoritmanın en önemli kısmı olan atlama işlemlerine verilen örneklerdir. Yani boyer moore algoritması aslında bir dizgiyi hedef bir dizgi üzerinde ararken, soldan başlayarak sağa doğru kaydırmaktadır. Bu kaydırma sırasında bazı durumlarda tek karakter bazı durumlarda da daha fazla atlayabilir.

    Yukarıdaki anlık durumlar, algoritmanın çalışması sırasında karşılaşılabilecek ve dolayısıyla birden fazla atlanmasını sağlayabilecek durumlardır. Ki zaten bu örneklerin atlamaya verilen örnekler olduğu açıkça yazılmış.

    Sizin alıntıladığınız örnekte ise dikkat edilirse karşılaştırılan kelimeler (alt alta gelen harfler)

    xbcd ile şadi kelimeleridir. Yani ş ile x , b ile a , c ile d ve i ile d harfleri alt alta gelmiştir. Bu durumda kaydırma tablosundaki d harfi aranan metinde bulunmuştur (xbcd içerisinde bir adet d harfi var) ve kaydırma tablomuzdaki yazdığı şekliyle 1 kere kaydırma yapılır.

    Ayrıca biraz daha saygılı mesaj yazarsanız sevinirim, bazı konuları anlayamıyor olabilirsiniz ama bunu öğrenmenin yolu anlatımı suçlamak olmamalı, uygun bir şekilde anlamadığınız kısmını sorarsanız zaten vaktim ölçüsünde elimden geldiğince açıklama yapmaya çalışıyorum.

  5. ismail

    Merhaba,

    Öncelikle bildiklerinizi paylaştığınız için çok teşekkür ederim. Boyer Moore algoritmasının good suffix tablosu nasıl hazırlanıyor açıklayabilir misiniz?

    İyi çalışmalar..

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


5 × üç =