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çmeyen¹ 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.