Yazan: Şadi Evren ŞEKER
1. Algoritmanın başarısı
2. Algoritmanın çalışması ve bir örnek
3. Algoritmanın kodlanması
Bilgisayar bilimlerinde bir metnin içerisinde başka bir metnin aranması için kullanılan en ilkel ve dolayısıyla en düşük performanslı arama algoritmasıdır (search algorithm). Algoritma hedef metinde, aranan metni harf harf bulmaya çalışır. Bu yapısından dolayı diziler üzerinde kullanılan doğrusal arama (linear search) algoritmasına oldukça benzer ve literatürde doğrusal metin araması (linear text search) ismi de verilmektedir.
Kaba kuvvet algoritması, isminden de anlaşılacağı üzere çok zeki olmayan ve başarısını bilgisayarın yüksek hızda çalışmasından alan bir algoritmadır. Algoritma basitçe metinin tamamını çok zeki olmayan bir şekilde dolaşır ve aranan kelimenin ilk harfini bulana kadar bu işleme devam eder. Bulduğu anda geri kalan harfleri eşleştirmeye çalışır. Şayet harflerden birisini eşleştiremezse, kelimenin ilk harfini bulduğu yere geri dönerek arama işlemine devam eder. Gerçi çok zeki olmadığı için kelimenin tamamını eşleştirse bile yine de ilk harfi bulduğu yere geri dönerek arama işlemine devam eder.
2 Algoritmanın çalışması ve bir örnek
Kaba kuvvet metin arama algoritmasının (bruteforce text search algorithm) çalışmasını aşağıdaki örnek üzerinden anlamaya çalışalım.
Aranan kelimemiz : bilgi
Aranan metin: wwwbilgisayarkavramlaricom
Olarak veriliyor olsun. Bu durumda algoritma ilk harften başlayarak “bilgi” kelimesini aranan metin içerisinde bulmaya çalışacaktır.
wwwbilgisayarkavramlaricom
b....
Öncelikle ilk harften başlanarak harfler karşılaştırılıyor. Aranan kelimenin ilk harfi “b” olduğu için bu harf bulunana kadar arama işlemi devam ediyor:
wwwbilgisayarkavramlaricom
b....
wwwbilgisayarkavramlaricom
b....
wwwbilgisayarkavramlaricom
BILGI
“b” harfi ile başlayan bir yer bulundu. Artık diğer harfler karşılaştırılabilir. Sırasıyla “I”,”L”.. harfleri karşılaştırılıyor ve harfler tuttuğu sürece karşılaştırma işlemi devam ediyor. Şayet harflerden birisi beklenen sırada gelmezse karşılaştırma işlemi kesilip kalınan yerden devam ediliyor.
wwwBILGIsayarkavramlaricom
b....
Aslında bu harflere bakılmış olmasına rağmen yine de aranıyor. Malum kaba kuvvet arama algoritması akıllı bir algoritma değildir ve bütün ihtimalleri dener. Dolayısıyla aslında bakmış olduğumu ve bakılmasının bir anlamı olmayan bu harflere de bu algoritma kapsamında bakılıyor.
wwwBILGIsayarkavramlaricom
b....
Arama işlemi aşağıdaki şekilde geri kalan harflerin kontrolü ile devam ediyor:
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
wwwBILGIsayarkavramlaricom
b....
Yukarıdaki arama işlemi sonucunda büyük harfle gösterilen kısımda aranan kelime bulunmuştur. Toplam 26 harflik bir metin içerisinde 5 harflik “bilgi” kelimesi aranmıştır ve 22 adımda bulunmuştur.
Artın aranan kelimenin sığmayacağı son harflere bakılmamıştır. Örneğin aranan metnin son 4 harfi olan “icom” alt metni (sub string) üzerinde arama işlemi anlamsızdır çükü buraya “bilgi” kelimesi sığamaz.
Algoritmanın C, C++, JAVA veya C# gibi diller için kodlaması aşağıdaki iki iç içe döngü (nested loop) şeklinde yapılabilir:
Yukarıdaki kodda, n boyutundaki y hedef dizgisi (string) içerisinde m boyutunda x dizgisinin arandığı kabul edilmiştir. Döngü basitçe n-m kere dönmektedir (yukarıdaki örnekte 22 kere dönemsi gibi) ve şayet aranan kelimenin ilk harfi bulunursa, 8. Satırdaki iç döngü dönmeye başlar. Harfler tutuştukça dönme işlemi devam ettirilir. Nihayetinde 11. Satırdaki koşul gerçekleşince, yani tutuşan harflerin sayısı, aranan kelimenin boyutunu geçince, yani aradığımız kelimedeki harf kadar harf, birbirini tutunca sonuç gösterilir. Bu işlem metnin sonuna kadar tekrarlanır.
Açıkcası kolayı zorlaştırmışsınız. Ancak yine de anlatımınız için teşekkürler.
burda açıklanan arama algoritmalarının tam kodu var mı ?
merhabalar hocam
girilen iki kelimenin anagram olup olmadığını kaba kuvvet yöntemiyle yazdıran bir program yazmak istiyorum.eğer anagram ise true değilse false döndürsün istiyorum.yardımcı olursanız sevinirim .