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.
831 views
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.