Giriş
Web sitelerinde bulunan arama fonksiyonlarının yanlış yazılmış kelimelere karşı tolere edilmesi gerektiği.
Levenshtein mesafesinin bu tür durumlar için kullanılabileceği.
Algoritma #1: Basit Yöntem
Levenshtein fonksiyonu iki kelime arasındaki mesafeyi hesaplar ve O(N*M) karmaşıklığına sahiptir.
Her bir kelime için bir N x M tablosunun doldurulması gerektiği.
Zaman Kısım Düşüklüğü
İlk yöntemi kullanarak gerçekleştirilen kelime aramanın süresi örneği.
Zaman verimliliğini artırmak için ek açıklama yapıldığında çalıştırma süresinin uzunluğu.
Algoritma #2: Trie Veri Yapısı ile İyileştirme
Trie veri yapısının kullanılması ile kelimelerin paylaşılan prefixlerinin işlenmesi.
İkinci algoritmanın, ilkinden 300 kat daha hızlı çalıştığı belirtiliyor.
RhymeBrain Uygulaması
RhymeBrain'deki kelime havuzunun 260,000'den 2.6 milyon kelimeye genişlemesi.
Yeni algoritmanın, düşük gecikme süreleri ile kelime sorgulama performansını artırması.
Alternatif Yöntemler
Peter Norvig'in kelime düzelticisi yazma yaklaşımının farklı olduğuna dair bilgiler.
Farklı veri yapılarını ve yöntemleri kullanarak performansı artırmanın yolları.
Install Browsy