Zemberek nasıl çalışır? 2.Ağaç Performansı ve Kök Seçiciler

Bu yazıda Kök ağacı ile ilgili performans verilerinden bahsedip Zemberek kök seçicilerinin yapısını kısaca anlatacağım.

Daha önceki yazımda zemberek kök ağacının yapısından bahsetmiştim. Yazıda kök ağacının oluşum zamanı ve düğüm sayıları ile ilgili bir şey yazmadığımı fark ettim, önce onları özetlersek:

Sistem: AthlonXP 2.2Ghz, Pardus 2007.1, Java 6, JVM client modu

Sözlüğün okunup ağacın oluşturulma süresi: 0.5s.
ikinci ve üçüncü okuyuşlar: 0.2s.
Toplam düğüm sayısı: 46634
Kök taşıyan düğüm sayısı: 33414
Alt düğümü olan düğüm sayısı:21729
Alt düğümü olmayan (yaprak) düğüm sayısı: 24905

Alt  düğüm dökümü:
1 alt düğümü olanlar: 10979  Yüzde: %50,527
2 alt düğümü olanlar: 6419   Yüzde: %29,541
3 alt düğümü olanlar: 1820   Yüzde: %8,376
4 alt düğümü olanlar: 846    Yüzde: %3,893
5 alt düğümü olanlar: 475    Yüzde: %2,186
...

Herhangi bir kelime için aday köklerin seçilmesini sağlayan basit yapılara kök seçici ismini verdik. Yazım denetimi gibi işlemlerin yapılabilmesi için gerekli olan Morfolojik analiz için verilen bir kelimenin önce kök adaylarının bulunması gerektiğini önceki yazıda ifade etmiştim. Bu işlem için "Kesin kök adayı bulucu" kullanılır. Yapısına bakacak olursak:
Zemberek ağaç üzerinde kelimenin harflerini izleyerek ilerler ve yolda rastladığı tüm kökleri toplar, yani "elmaslarının" kelimesi için aday kök olarak "el", "elma" ve "elmas" kelimeleri seçilir. Daha sonra Çözümleme işlemine geçilir ve bu adaylar tek tek denenir. Genelde en uzun olan kök adayı uygun seçim olacağından denemelere uzun olan kökten (seçilenlerin en sonuncusundan) başlanır.

Zemberek'in yazım denetimi sırasında hatalı kelimeler için öneri de verdiğini biliyoruz. Öneri işlemi nispeten karmaşık bir kök seçici ve özel bir çözümleyici kullanır. Bu özel seçici ağaç üzerinde ilerlerken belli bir hata toleransını da hesaba katar.

Örneğin "elxalarının" hatalı kelimesi için ağaç üzerinde ilerlerken sadece "ela, elma ve elmas" değil "ela" kökü de seçilir. Zemberek te bu kelime için "elmaslarının ve elalarının" önerilerini üretir. Ağaç üzerinde ilerleme hata toleransı ile sınırlıdır, yani algoritma "Hata toleransı belli bir değeri aşıncaya kadar ağaçta ilerle ve rastladığın kökleri seç" ifadesi ile özetlenebilir. . Zemberek kelimelerin birbirlerine ne kadar benzediğini bulmak için şimdilik sadece Damerau-Levenshtein düzeltme mesafesi algoritmasını kullanıyor, ancak denemek isteyen biri farklı kelime benzerlik algoritmalarını kullanan bir seçici yazabilir, Örneğin Zemberek içerisinde gerçeklemesi bulunan Jaro-Winkler benzerlik algoritması uygun olabilir.

Son olarak ta Türkçe klavyesi olmayan veya (nedense) Türkçe harfleri tercih etmeyen kişilerin yazdıkları kelimelerin Türkçe'deki karşılıklarını bulmaya yarayan Ascii->Türkçe dönüşümünde kullandığımız Ascii Toleranslı Kök seçici'nin yapısı da şu şekildedir:

Bu seçici de nispeten toleranslı kök seçiciye benzer, ancak bu sefer kelime benzerlik algoritmaları kullanmak yerine kelime için ağacı tararken u,i,s,o,g,c harfleri için ve Türkçe'deki karşılıkları olabilecek ü,i,ş,ö,ğ,ç düğümlerinde de ilerler. Yani yazar "durumunun" demişse sadece "dur", "duru" ve "durum" değil "dür" ve "dürüm" kökleri de aday olarak seçilir.

Peki seçicilerin performansı nasıl? Değerleri yaklaşık olarak veriyorum, sanırım toleranslı seçici performansı üzerinde biraz daha çalışmamız gerekiyor :) tabi burada önemli bir nokta var, yaptığım testte türkçe bir metni toleranslı seçici kullanarak taradım, yani hatalı kelimeler yerine doğru kelimeler için toleranslı seçim yapıldı, bu da ağaç üzerinde gezinilen düğüm sayısını çok arttırıyor, yani performans bozuk bir metinde çok daha yüksek olacaktır.

Yine aynı sistemde (AthlonXP 2.2Ghz, Pardus 2007.1, Java 6 -client)
Kesin kök seçici: 600.000 kelime/s
ASCII toleranslı seçici: 100.000 kelime/s
Toleranslı seçici: 300 kelime/s

Kök seçicilerinin bize getirisi bu üç farklı işlem için de aynı veri yapısının (ağaç) kullanılması ve kodlarının çok basit olmasıdır. Merak edenler aşağıdaki adresten kök ağacı ve seçicilerle ilgili kodlara erişebilirler:
http://zemberek.googlecode.com/svn/trunk/zemberek2/src/cekirdek/net/zemberek/bilgi/kokler/