İzlandaca ad çekim kalıplarını 3.27kB trie ile sıkıştırma

 (alexharri.com)
2 puan yazan GN⁺ 2025-08-04 | 1 yorum | WhatsApp'ta paylaş
  • İzlandaca kişisel ad çekimi, bağlama göre 4 farklı biçime dönüşür
  • Girilen bir ada uygun gramatik durumu döndüren bir işlevi geliştirmek için veri odaklı bir JavaScript kütüphanesi oluşturuldu
  • Tüm adları doğrudan saklamak, boyut artışı ve veri kaybı sorunlarına yol açtığı için, trie yapısı ve sıkıştırma teknikleri kullanılarak bu sorunlar giderildi
  • Trie sıkıştırması sayesinde ortak desen tabanlı otomatik çıkarım mümkün oldu ve verinin %80’inden fazlasını kapsayan çok küçük bir veritabanı elde edildi
  • Yaygın durumlarda %74’ün üzerinde doğruluk sağlanırken, kamu sektörü ve yüksek doğruluk gereken senaryolar için ayrı bir strict sürümü sunuldu

Sorunun Arka Planı

  • İzlandaca arayüzlerde kişisel adlar gösterilirken, çekim (declension) nedeniyle zorluklar yaşanıyor
  • İzlandaca adlar nominatif, akuzatif, datif ve genitif gibi 4 gramatik duruma göre farklı şekiller alır
  • Veritabanlarına genelde adlar nominatif biçimde kaydedilir ve bağlama göre farklı bir duruma ihtiyaç olduğunda sorun oluşur
  • Doğru biçim kullanılmadığında, dilin yerelini gibi durmayan veya yapay bir izlenim ortaya çıkar

Veri Toplama ve Temizleme

  • İzlanda, Árnastofnun tarafından yönetilen DIM(Database of Icelandic Morphology) verisi açıldı
  • Ad çekim verisi, Kristín’s Format(K-format) CSV formatında işlenebilir
  • DIM veri kümesi 7 milyon satır olduğu için çok büyüktür; bunun yerine resmî olarak onaylı kişisel adlar (4.500 adet) arasından seçilerek 3.600 civarında ada ait çekim bilgisi elde edildi
  • Her ad için nominatif~genitif biçim dizisi oluşturulabilir

Kütüphane Temel Yapısı

  • İlk uygulama, ad~durum dönüşüm dizisinden uygun biçimi döndüren applyCase işlevi ile başladı
  • Ancak basit dizi yükleme yöntemiyle boyut 30kB gzipped olarak yüksek çıktı
  • Veri kümesine dahil olmayan adlar için karşılık verememe gibi bir sınırlılığı vardı

Örtüşmeleri Azaltma ve Kalıp Çıkarma

  • İsimlerin 4 biçimi arasındaki ortak önekler çıkarılarak, her biri için yalnızca sonek kümeleri (suffix encoding) saklandı
  • Aynı çekim kalıbını izleyen çok sayıda adın bulunduğu fark edildi

Desen Eşleştirme için Trie'nin Kullanımı

  • Benzer kalıpları paylaşan ad gruplarının değer eşlemelerini optimize etmek için trie yapısı (sonek temelli ters ekleme) kullanıldı
  • Ortak desenlerin (ad son ekleri) altında çekim bilgisi yalnızca bir kez saklanır ve yeni adlar için güçlü bir tahmin gücü sağlanır

Trie Sıkıştırma ve Optimizasyon Süreci

  • Alt ağacın tüm yaprak (leaf) değerleri aynıysa üst düğüme bu değer atanıp çocuk düğümler silinerek ağacı sıkıştırırız
  • Bu sayede düğüm sayısı %15.4’e kadar düşürüldü ve boyut 4.01kB’ye indirildi
  • Değerleri aynı olan kardeş yaprak düğümlerini tek bir düğümde birleştiren ikinci bir sıkıştırma ile 3.27kB’ye ulaşıldı

Trie Performansı ve Genelleştirme

  • Yeni bir ad girildiğinde benzer desen tabanlı otomatik çekim yapılabilir
  • Bilinmeyen adlarda %74 doğru çekim, %26 hata gözlendi; gerçek kullanıcılar için hata oranı yalnızca %0.34
  • Verinin düzenliliği (regularity) ve kapsayıcılığı (comprehensiveness) ne kadar yüksekse, sıkıştırma ve otomatik çıkarım doğruluğu o kadar artar

Gerçek Kütüphane ve Uygulama

  • Sonuç olarak, sıkıştırılmış trie kullanan beygla kütüphanesi dağıtıldı
  • En küçük boyutlu sürüm (4.46kB) ve daha katı ve kusursuz eşleştirme sağlayan özelleştirilmiş bir strict modülü (15kB) sunuldu
  • Resmî belgeler gibi %100 doğruluk gereken yerlerde strict sürümü, genel web uygulamaları için hafif sürüm seçilebilir

Sonuç ve Genişletilebilirlik

  • Trie destekli dil çekim kalıbı verisi sıkıştırması, İzlandaca dışındaki birçok çekimli dildeki kişisel ad, adres ve diğer adların otomatikleştirilmesi için uygulanabilir
  • Düzenliliği yüksek veriler ile trie sıkıştırmasının birleşimi, morfolojik çekim işleme otomasyonunda hem veri hem de performans verimliliğini maksimize eden bir yaklaşım sunar

Teşekkür ve Kaynak

  • beygla geliştirme sürecinde farklı uzmanlardan gelen geri bildirimler ve optimizasyonlar alındı
  • Trie’ye ek sıkıştırmalar uygulanarak 3.43kB → 3.27kB’ye kadar boyut azaltıldı

Özet

  • İzlandaca ad çekimi otomasyonuna yönelik problemi, örüntü tabanlı bir trie veri yapısıyla küçültüp otomatikleştiren bir örnektir
  • Doğru boyut–doğruluk dengesini gözeten pratik bir veri işleme stratejisi için önemli bir örnektir

İlgili okumalar

1 yorum

 
GN⁺ 2025-08-04
Hacker News yorumu

  • Lisede ilk kez İspanyolca öğrenirken, Windows için bir yazılım kullanmıştım; mastar ve zamanlar peş peşe geliyordu, ben de buna uygun fiil çekimini girmek zorunda kalıyordum. Bu tür alıştırmalar sayesinde dilbilgisi kuralları içselleşti ve akıcı hâle geldi. Ama Rusça öğrenirken hâl değişimleri bir anda zorlaşmıştı ve benzer kalıpları açıklayan ya da çalıştıran bir uygulamayı ne kadar arasam da bulamamıştım. Bu amaç için kullanılabilecek bir (web ya da macOS/iOS) uygulama bilen var mı diye merak ediyorum

    • Anki'de "KOFI(Konjugation First)" adlı bir yöntem kullanan flashcard desteleri var. KOFI, dili öğrenmeden önce bütün çekim kalıplarını önce ezberleme yaklaşımı anlamına geliyor. Fransızca çalıştıktan sonra çekim konusunda zayıf kaldığım için bunu sonradan denemiştim; dilbilgisel olarak hatalı konuşsan da günlük iletişim için yeterli oluyor ama benim hedeflediğim seviye bu değildi. Bu yöntemin amacı, dili öğrenmeye başlamadan önce bütün çekim kalıplarını kısa sürede öğrenmek. Bir gün yeni bir dilde buna ciddi şekilde yaklaşmak isterim. Fransızcaya ilgim azaldığı için yarıda bırakmıştım. İlgili Anki destesi bağlantısı

    • Rusça öğrenirken spaCy Python modülü ile Rusça için büyük modülü birleştirip bağlama dayalı lemmatization ve dilbilgisel etiket çıkarımı yapan bir betik yazmıştım. Ama Rusçam gerçekten gelişmeye başladığında, çekimleri mantıksal olarak parçalama çabasını bırakıp kullanım deneyimi ve tekrar yoluyla zihnimde kalıplardan (istisnalar dâhil) oluşan bir kütüphane biriktirmenin çok daha etkili olduğunu gördüm. Bu arada burada bağlam derken cümle içindeki anlamı kastediyorum

    • 25 yıl önce İspanyolcayı kendi kendime öğrenirken bir İspanyolca/İngilizce sözlük kullanıyordum. Mastar fiillerin yanında sayısal bir indeks vardı; bu sayede aynı çekim kalıbına sahip gruplara ayrılıyorlardı. Sözlüğün başında da her grup için temsilci bir fiilin bütün zamanlardaki çekim tabloları bulunuyordu. Düzensiz fiiller ayrı bir indeks altındaydı ve onlar da yine benzer düzensiz fiillerle aynı gruplara konmuştu (ör. tener, detener). Bütün fiiller birkaç düzine benzersiz kalıba çok düzenli şekilde ayrılmıştı. Bu sistemi kullanan bir quiz yazılımı yapmayı da düşünmüştüm ama bir türlü yapamadım. Yazıda bahsedilen reverse-string trie kalıbının bu tür bir sınıflandırmada da işe yarayıp yaramayacağını merak ediyorum

    • Rusçadaki hâl değişimlerini öğrenmek için edat+sıfat+isim birleşimlerinden oluşan flashcard'lar hazırlayıp ezber hızını artırma fikrim vardı. Daha önce Latince öğrenmiştim; Latincede hâl çekimlerini hızlıca ezberlemek beklenen bir şey değil gibi geliyor (rahipseniz belki?) ama Rusçada bunu hızlı öğrenmek istiyordum. Sonuçta bu da bir projeye dönüşmedi

    • İspanyolca çekim pratiği için iOS'ta ConjuGato kullanıyorum. Oyun modunda mastar/zaman/kişi veriliyor ve sen çekimli biçimi hatırlıyorsun. Sadece düzensiz fiilleri ayrı çalışabilmek, istisnaları öğrenmede çok faydalı oluyor

  • Veritabanında hâl çekimi bilgisi eksik olan 800 isim için, elle tek tek çekim eklemek en doğrudan çözüm gibi görünüyor. Anadili konuşuru biri için bu birkaç saat içinde biter ve tamamen yabancı isimlerde bile en azından açıkça tuhaf durmayacak bir biçim tahmin edilebilir. Ya da bunu bir LLM'ye yaptırmak da çok ucuza mal olur. Sonucu böyle bir trie yapısına kodlayıp dağıtmak yine de iyi fikir. Sadece trie'yi çekim tahminleyicisi olarak da kullanmak şart değil

    • Daha fazla ismi ele almak kesinlikle tercih edilir—DIM tarafında sürekli tamamlanması gereken bir alan bu. İzlanda'da izin verilen isimler listesine sık sık yeni isimler eklendiği için her zaman boşluklar kalıyor. Ben kendi başıma veri eklemek konusunda yeterince emin hissetmiyorum; doğrulanmamış 100 isimlik sonuçları her gözden geçirdiğimde sık sık “Bu gerçekten doğru mu?” diye düşündüğüm oldu. Benzer isimleri DIM'de aratıp “Ben bunu böyle çekimlemezdim” dediğim de çok oldu. Bu yüzden DIM verisini dil uzmanlarının bakımını yaptığı bir "tek doğru kaynak" olarak görüyorum

    • El emeği yaklaşım iyi ama resmî listede olmayan isimler için (yabancı isimler gibi) hâlâ sınırları var. Ben de merkezi isim listesi olan bir ülkede yaşıyorum ama istisna başvurusu yapılabiliyor; ayrıca liste oluşturulmadan önce doğanlar ya da göçmenler gibi sebeplerle listede yer almayan isimler de olabiliyor. Bu tür birleşik durumlarda “kabaca uygun bir çekim biçimi tahmini” özelliği hâlâ faydalı

    • LLM'lerin trie'den daha iyi hâl çekimi tahmini yaptığını gösterecek bir kanıt bulamadım (eğer gerçek örnek LLM'nin eğitim verisinde yoksa, web araması daha iyi olabilir)

    • Mevcut LLM'lerin bu tür kalıpları zaten öğrenip öğrenmediğini merak etmeye başladım

  • Rails'in bunu otomatik çözdüğünden emin değilim ama eskiden bu tür sihirleri iyi yapardı. Yıllar önce pluralise kaynak koduna bakmıştım; Galcedeki düzensiz çoğul kuralları bile kodlanmıştı

    • Rails gerçekten harika; çoğu özellik için bir metot zaten hazır oluyor

  • Bir optimizasyon fikri olarak, trie'nin doğrudan sonek dizgelerine eşlenmesi yerine benzersiz soneklerden oluşan bir dizi oluşturulup trie'nin bu dizideki indekse işaret etmesi düşünülebilir. Örneğin:

    const suffixes = [",,,", "a,u,u,u", ",,i,s", ",,,s", "i,a,a,a", ...];

    ve sonra şöyle indeks referansı verilebilir:

    var serializedInput = "{e:{n:{ein:0_r: ..."

    • Bunu Claude Code ile bizzat denedim; gzip uygulanmış hâlde 100 bayt daha büyüdü (3456 -> 3556), sıkıştırma öncesi boyut ise yalnızca %20 küçüldü. Görünüşe göre gzip zaten tekrar eden kalıpları çok iyi optimize ediyor

    • Bir adım daha ileri gidip soneklerin kendisini de trie'ye koyup, aynı alt ağaçları tespit ederek tekilleştirmek mümkün olabilir. Gzip kullanabiliyorsanız, sonek dizisinden yararlanan akıllı bir optimizasyon yolu kesin vardır. İkili optimize bir format kullanılırsa daha da iyi olabilir

  • Kişisel olarak, sıkıştırılmamış durumda bunu <1kb içinde çözebilecek sihirli bir yaklaşım varmış gibi geliyor. İsimleri %100 doğru sınıflandıran minimize edilmiş regex listeleri yapmak mı? Devasa bir bloom filter mı? Yoksa genel amaçlı hash yerine özelleşmiş özellikler kullanan bir yaklaşım mı?

  • Tam bir kâbus mülakat sorusu gibi. Trie'yi ters kullanmak hayat boyu belki bir kez işe yarar ama o bir sefer kullanınca büyücü gibi görünürsün

    • Bunun trie'yi ters çevirmekten çok, isimleri tersten trie'ye yerleştirmek olduğunu söylemek daha doğru olur

  • Bunu JS içinde yapmak yerine, veritabanının bütün isim-hâl kombinasyonlarını döndürmesi ve gösterim anında sadece gerekenin seçilmesi de mümkün görünüyor. Yani bu iş yerelleştirme katmanında çözülebilir. Diller arası durumda ne olacağını merak ediyorum. İzlandaca bir arayüz Fransız isimleriyle uğraşırken muhtemelen her zaman yalın hâli kullanır; İngilizce arayüz de İzlandaca isimlerde muhtemelen aynısını yapar. Sonuçta buna asıl ihtiyaç, kullanıcıya doğrudan hitap edilen bağlamlarda ya da yönetici paneli gibi yerlerde (“user x, user y'ye yanıt verdi”) ortaya çıkıyor gibi

  • “idur”, “tur”, “ður” ile biten ve belirli bir hâl çekim kalıbını izleyen 88 isim var ama aynı sonek her zaman aynı çekim kalıbını izlemiyor. Sorun ilk bakışta basit bir kural gibi duruyor ama aslında oldukça ilgi çekici. Acaba sonek kalıbı, hemen önceki hecenin telaffuzuyla mı ilgili? Bilinmeyen isimleri daha iyi ele almak için sadece harf temelli değil de, ismin telaffuz temsilini NLP ile çıkarıp trie benzeri yapılarla sorgulamak gerekir mi diye merak ediyorum

    • Bu tür düşünceler insanı bir anda Dependent Types tartışmalarına sürükleyebilir, dikkatli olmak lazım

    • Çok keskin bir fikir. Gerçekten de aynı telaffuza sahip isimlerin bile farklı hâl çekim kalıpları olabiliyor. Örneğin:

      • Ástvaldur -> ur,,i,ar
      • Baldur -> ur,ur,ri,urs “aldur” ile biten bu iki isim aynı telaffuza sahip ama çekim kalıpları farklı. “Ástvaldur”un kalıbını “Baldur”a uygularsan son üç biçim gerçekten çok tuhaf geliyor (bunu İzlandalı partnerime de sordum). İzlandacada yazım ile telaffuz çoğunlukla oldukça yakındır, bu yüzden telaffuz tabanlı bir trie kullanılsa bile büyük fark yaratmayabilir

  • beygla/strict durumunda perfect hashing bir alternatif olarak düşünülebilir

    • Bütün değerlerin benzersiz olmadığı durumda, klasik perfect hashing'den daha da fazla sıkıştırma mümkün olabilir. Tek bir hash bucket içine birden fazla isim->sonek çifti sığdırılabilir. Ama bu durumda “işlenemeyen isim” tespiti özelliği kaybolur

  • İzlandaca isimlerdeki hâl dönüşümünün, bu tür bir yaklaşımın işe yarayacağı kadar belirgin ve deterministik kalıplara sahip olması bana şaşırtıcı geliyor. Sonuçta diller genelde oldukça karmaşıktır

    • İzlanda'nın nüfusunun az olması ve dilin devlet tarafından aktif biçimde yönetilmesi bunda etkili olmuş olabilir