Hello!

Hello Blogger!

Yorumlar

Yorum Gönder

Bu blogdaki popüler yayınlar

String Matching - Boyer-Moore Algorithm

Resim
Boyer-Moore Algorithm Bu algoritma Horspool algoritmasının geliştirilmiş halidir. Karşılaştırma yaptığımız pattern’in son karakterinin eşleştirilmesi başarısız olursa Horspool algoritmasındaki işlemin aynısı gerçekleştirilir. Fakat herhangi bir sayıda eşleşme olduktan sonra eşleşme başarısız olursa Horspool algoritmasından farklı davranır. Burada iki tablo ortaya çıkmaktadır. Horspool’dan gelen bad symbol shift ve farklı olarak gelen good-suffix shift. Boyer-Moore algoritması bu iki tabloyu değerlendirir ve bu tablolarda karşılık gelen değerlerden maksimum kaydırmayı sağlayacak olan durumu seçer. Bu seçim sayesinde Horspool algoritmasına göre daha büyük bir kayma sağlama şansı doğar. Bu algoritmalar farklı karmaşıklıklara, çalışma zamanına ve alan kullanımına sahiptir. Bu nedenle bu algoritmalar belirli durumlarda diğerlerine göre daha etkin olabilmektedir. String eşleştirme algoritmaları günümüzde birçok alanda kullanılmaktadır. Internet ve masaüstü uygulamala...
Devamı

İki Renkli Görüntülerde Karakter Ayrıştırma ve Tanıma

Resim
I. ÖZET Karakter tanıma işlemi, yazılı dökümanların sayısal forma dönüştürülmesi, otomatik plaka tanıma gibi alanlarda sıklıkla kullanılmaktadır. Bu işlemler iki adımda gerçekleştirilmektedir; karakterin bulunduğu görüntünün iştenilen biçimde bilgisayar ortamına aktarılması ve bu görüntüerdeki karakterlerin ayrıştırılarak tanınması işlemi. Bu çalışma sadece ikinci adımı içermektedir. Karakter tanıma işlemi sadece bilgisayar ortamında yaratılan görüntüler üzerinde uygulanmıştır. Çeşitli görüntü işleme yöntemleriyle görüntü karakterlerin ayrıştırılabileceği hale getirilmiş, karakterlerin ayrıştırılması için tasarlanan algoritma ile karakterler ayrıştırılmış ve bu karakterler LVQ algoritması kullanan Yapay Sinir Ağı(YSA) ile tanımlanmıştır. YSA, İngiliz alfabesindeki 26 harfi tanıyacak şekilde beslenmiştir. Uygulamanın doğruluk oranı testlerle kanıtlanmıştır. II. GİRİŞ Karakter tanıma, yazılı yani fiziksel dökümanların işlenmesiyle makine kodu halindeki metinlere çevrilmesi işlem...
Devamı

String Matching - Horspool's Algorithm

Resim
Horspool’s Algorithm Bu konuda brute force string matching algoritmasına alternatif olarak kullanabilecek daha etkin bir algoritma olan Horspool Algoritması açıklanmaktadır. Brute-Force’a benzer şekilde pattern’in son harfinden başlanarak soldan sağa doğru pattern ve text’te karşılıklı denk gelen harfler karşılaştırılır. Eğer pattern’deki tüm karakterlerin eşleşmesi sağlanırsa substring bulunmuş demektir. Bu durumda arama durdurulabilir veya başka eşleşme var mı diye aramaya devam edilebilir. Eşleşme olmazsa pattern’i sağa kaydırmamız gerekir. Bu durumda herhangi bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz en büyük olası kaydırmayı yapmak isteriz. Horspool algoritması burada pattern’in son karakterine karşılık gelen (c) karakterine bakarak kaydırma yapar. Burada dört olasılık söz konusudur. Bu durumlardan ilerideki sayfalarda bahsedilecek. BARBER pattern’ini bir text’te aradığımızı düşünelim. Pa...
Devamı