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.
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.
Ö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.
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ı 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.
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…
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
teşekkür ederim.
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
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.
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 video çekerek nasıl olduğunu örnek üzerinden açıkladım:
https://youtu.be/c1LyW_8zPdA
Başarılar
Teşekkürler Hocam, size bir mail attım onu okursanız çok iyi olur. İyi çalışmalar..