2.1 Hata Toleranslı Kelime Arama
Bu kısmı okumadan önce
www.sabanciuniv.edu/fens/people/oflazer/pubs.html
adresinden Kemal Oflazer'in
"Error-tolerant Finite State Recognition with Applications
to Morphological Analysis and Spelling Correction
"
konulu makalesini okumanızı öneririm. Makaleyi buradan da indirebilirsiniz.
Bir DFA'den kelimenin doğru olup olmadığını öğrenmek kolaydır fakat
kelime hatalı girilmişse, aday doğru alternatifleri bulmak biraz daha karmaşıktır.
Kılavuz'da çalışan algoritma, düzenleme uzaklığı (edit distance) ve kestirme
uzaklık
(cut-off distance) olarak tanımlayabileceğimiz iki ölçütü baz alarak çalışır.
Bu iki ölçüt, yukarıdaki adreste verilen Kemal Oflazer'in makalesinde çok
güzel
bir şekilde anlatılmıştır.
Algoritma Nasıl Çalışır ?
Algoritma, doğru olmayan bir kelimenin alternatiflerini aramaya başlangıç
nodundan
başlar. Başlangıç nodundan başlayıp kestirme uzaklığını geçmeyen1
bütün nodlara uğrar.
Bu nodlara uğrarken test ettiği her aday kelimeden, düzenleme uzaklığını
geçmeyen ve
sonlu nodda olan tüm kelimeleri sonuç olarak çıkarır.