3 GB’lık SQLite veritabanını 10 MB’lık FST (sonlu durum dönüştürücüsü) ikili dosyasıyla değiştirmek

• Taskusanakirja, yazarken önek araması sunan bir Fince-İngilizce sözlük
• Fince çekim genişlemesiyle giriş sayısı 40 milyon~60 milyon aralığına çıktı ve trie sınırına dayandı
• Geçici SQLite FTS çözümü hızlıydı ama ilk seferde 3 GB indirme gerektiriyordu
• Rust tabanlı FST, SQLite verisini yaklaşık 10 MB’lık bir ikili dosyaya indirerek 300 kat tasarruf sağladı
• FST, öneklerle birlikte sonekleri de paylaşır; bu yüzden tekrar eden çekim kalıplarına çok uygundur

---

Taskusanakirja’nın arama yapısı ve ilk sınırlar

• Taskusanakirja, kısaca tsk, bir Fince-İngilizce sözlük ve yazarken kademeli arama özelliği sunuyor
• Bu özellik temelde bir önek araması problemi ve otomatik tamamlama için klasik çözüm bir trie uygulamasıydı
• İlk uygulama Go ile yazıldı; başlangıçtaki tasarım hedefi, tüm programı tek bir .exe, tek bir .app ya da tek bir statik bağlı ikili dosya olarak dağıtmaktı
• Orta 6 haneli kelime sayılarında, tek haneli yüzdelerin bir kısmına denk gelen tüm girişleri eşleştirmemek için yalnızca ilk 50 ya da 100 sonuç döndürülüyor ve 1, 2, 3 harfli kombinasyonlar memoize ediliyordu
• Bu yaklaşımla temel optimizasyonlar uygulanmış trie yaklaşık 60 MB alana sığdı ve bir yıl boyunca yoğun kişisel kullanımda bile hissedilir bir gecikme olmadı

Fince çekim verisinin yarattığı ölçek sorunu

• Fince bir bitişken dil; bu yüzden tek bir kök kelime, tüm kombinasyonlar hesaba katıldığında 100’den fazla ekli biçime sahip olabiliyor
• Kombinasyonlar düzenli değil; ayrıca son derece düzenli Fince yazım sistemi, gerçek konuşurların söylediği biçimleri yazıya doğrudan yansıttığı için kök kelimeler eklerle birleşirken uzuyor, yer değiştiriyor ve dönüşüyor
• Başlangıç düzeyindeki bir öğrenci, “Opiskelijassammekin on leijonan sydän” gibi bir cümlede belirli bir kelimede kolayca takılabilir; tsk de kelimeleri doğru sınırlardan ayırmaya yardımcı olacak bilgiler içermeyi amaçlıyordu
• Dilbilimsel olarak bu dönüşümler ünsüz derecelenmesi ve ünlü uyumu kapsamına giriyor; Fince ikisini aynı anda kullanıyor
• Örneğin katu, “street” anlamına geliyor ama ilgi hâli katun değil kadun; çünkü kapalı hece nedeniyle t, d’ye zayıflıyor
• Bu yapıyı 15 hâl, 2 çoğul, 6 iyelik eki ve belirsiz sayıda parçacıkla çarptığınızda, saf bir trie -ssa-mme-kin gibi binlerce kelimenin paylaştığı son parçaların maliyetini paylaşamıyor
• Yaklaşık 400 bin giriş trie ile yaklaşık 50 MB RAM içinde tutulabiliyordu ama aynı yaklaşım 40 milyon~60 milyon girişe ölçeklenemedi
• Geçici çözüm olarak çekimli biçimler ayrı bir SQLite FTS veritabanına konulup gerektiğinde aranıyordu; bu hissedilir gecikme olmadan çalıştı ama ilk kullanımda 3 GB indirme gerektiriyordu

Rust ve FST’ye geçince ortaya çıkan sonuç

• 9 ay sonra Rust ile yeniden denenirken, 3 GB’lık SQLite veritabanından veriyi alıp bir FST içine sıkıştıran minimal bir Rust programı yazıldı
• İlham kaynağı BurntSushi aka Andrew Gallant’ın Index 1,600,000,000 Keys with Automata and Rust yazısıydı; burada sonlu durum makinelerinin sıralı string kümelerini veya map’leri küçük ve hızlı şekilde temsil edebilmesi kritik noktaydı
• Ortaya çıkan ikili dosya yaklaşık 10 MB oldu; bu da 3 GB’lık SQLite veritabanına kıyasla yaklaşık 300 kat alan tasarrufu demek
• Bu kullanım senaryosu fst crate için de özellikle uygundu; çünkü mesele, yüksek derecede bitişken bir dilin çekimli ve kullanımlı biçimlerini özgün tanımlarına geri eşlemekti
• Trie önekleri sıkıştırır ama FST hem önekleri hem sonekleri sıkıştırır
• Fince sözlük derleminde çok sık tekrar eden az sayıda popüler sonek bulunduğu için, sonek paylaşımı büyük etki yaratıyor
• Veriler çalışma sırasında değişmeyen statik veriler olduğundan, fst’nin en büyük zayıflığı da böylece aşılmış oldu

FST neden trie’den daha küçük oldu?

• FST’yi doğal dil verisinde trie’den çok daha küçük yapan temel unsur sonek paylaşımı
• Trie, kadun ile kaduille örneğinde olduğu gibi ilk üç düğümü paylaşarak önekleri ortaklaştırır, ancak farklı sonek yollarını ayrı ayrı saklar
• Minimal acyclic deterministic finite automaton, yapısal olarak aynı olan iki alt ağacı birleştirir
• 100 bin kelimenin aynı yaklaşık 12 çekim kalıbıyla bittiği bir derlemde, bu birleştirme büyük bellek tasarrufu sağlar
• Bu örnekteki temel sezgisel yaklaşım, doğaçlama kurulmuş genel amaçlı bir veritabanını, tam olarak gereken işi yapan küçük, statik ve özel amaçlı bir veri yapısıyla değiştirip 300 kat bellek tasarrufu elde etmek

Geçici SQLite çözümünün kalan rolü ve dağıtım boyutu

• 9 ay önceki SQLite tercihi, “iyi olanı yapamamak” yerine “kötü ama kolay olanı” seçmenin sonucuydu ve gerçekten işe yaradı
• SQLite’ın B-tree yapısını ve Full Text Search extension’ı bildiği için, o dönemde hızlıca denenebilecek bir çözümdü
• Aynı FTS uzantısı, tsk v2.0.0 alpha’da yer almayan daha az kullanılan bazı özelliklerde de kullanıldı; ancak mevcut bellek ayak izine zarar veriyorsa tamamen kaldırılması mümkün
• v2’nin Pro sürümünün her şey dahil yaklaşık 20 MB olması hedefleniyor; bu da v1 ücretsiz sürümden 3 kat daha küçük
• tsk başlangıçta bir TUI Go programıydı; önceki fzf tabanlı prototip finstemden evrildi ve the highest-ROI program I’ve written so far yazısıyla bağlantılı
• taskusanakirja, Fince’de “pocket dictionary” anlamına geliyor; eski bir dizüstüne bile sığmıyorsa bunun artık cep sözlüğü değil, derlenmiş eski bir Oxford sözlüğüne daha yakın olduğu düşüncesi korunuyor
• “Bir problemi iki kez çözmekte sorun yoktur” şeklinde tekrar eden bir yaklaşım var; mevcut daha iyi bir uygulamayı bulma suçluluğuyla duraksamak yerine, birkaç tekerleği bizzat yeniden icat etmenin gerçek sınırlara daha hızlı ulaşmayı sağlayabileceği görüşü savunuluyor
• Bu bakış açısı, Caplanian view’daki “pratik” fikriyle bağlantılı ve Do Ten Times as Much rahatsız edici ama işe yarayan bir tavsiye olarak sunuluyor

[GN⁺]

Lobste.rs görüşleri

• Yazının kendisi de ilgi çekiciydi; doğru aracı doğru işe uygulayıp tek haneli ölçeklerde iyileşme elde etmeleri hoşuma gitti, ama asıl metinden çok sondaki dipnot daha etkileyiciydi
  Şu anda yaptığınız aracın 30-40 yıl önce bir başkası tarafından zaten daha iyi biçimde yapılmış olabileceği suçluluğu yüzünden duraksama hâlini tam isabetle anlatıyor. Ama bunun bir tuzak olduğunu, tekerlek yapmanın sınırına yaklaşmak için birkaç tekerleği yeniden yapmanız gerektiğini söylemesi çok yerinde. Çoğu alanda dört beş tane yeterli olur; matematik ya da bilgisayar bilimi gibi daha katı alanlarda bile yirmi küsur tane yeterli olabilir; ayrıca böyle şeyleri bizzat yeniden yaparken sorduğunuz soruların, sıradan çalışmaya kıyasla sizi gerçek ön cepheye çok daha hızlı taşıdığı savunuluyor

  • Metindeki önemli ilgili nokta, SQLite DB ile yapılmış verimsiz kaba kuvvet uygulamasının bile bir referans uygulama olarak değer taşımasıydı
    En azından çalışan bir referans uygulama vardı; bu sayede onun yerine geçecek verimli bir uygulama geliştirmek daha kolay oldu
  • Şu an yaşadığım sorunla birebir örtüşüyor. Problem alanıma optimize edilmiş bir şey yapmak istiyorum ama genelleştirilmiş problemin zaten çözülmüş olduğunu bildiğim için durup kalmıştım
    Ama mevcut çözümlere bakınca benim ihtiyaç duymadığım çok fazla yük taşıdıklarını görüyorum. Deneyimlerime göre fikrimi zorlamaya değer olduğunu bilsem de bir şeyi gözden kaçırıyor olabilir miyim diye sürekli düşünüyordum; bunu okuyunca doğrudan denemeye karar verdim. Başarısız olsam bile süreçte öğreneceğim şeyler var

• Çok havalı. Compressing Icelandic name declension patterns into a 3.27 kB trie yazısını hatırlattı

• Bir Scrabble botu geliştirirken ilgili bir veri yapısı olan DAWG(Directed Acyclic Word Graph) ile tanıştım; bu kullanım için epey yaygın görünüyor
  fst crate'iyle temel farkı, her kelimeyi benzersiz bir tamsayıya eşlememesi gibi görünüyor. Benzer şekilde boyut çok küçüldü ve performans da inanılmaz arttı. Scrabble botunun temelde ..cat.. gibi basit regex'lerle eşleşen kelimeler için tüm sözlüğü filtrelemesi gerekiyor; ama pratikte mevcut tahtadan üretilebilecek tüm basit regex'leri ele alması lazım. Yaklaşık 1 dakika bekleten bir iş, hissedilemeyecek kadar düşük bir gecikmeye indi

  • Appel ve Jacobson'ın 1988 tarihli DAWG makalesi yakın zamanda da paylaşılmıştı ve daha önce de gönderilmişti

• Bağlantısı verilen şu yazı da okunmaya değer: https://burntsushi.net/transducers/

• fst, sonunda srgn'in Almanca desteğinde de kullandığım araç oldu; üstelik Andrew bunu bizzat önermişti
  Ortak önekleri ve sonekleri sıkıştırma açısından aynı problem alanı söz konusu ve gerçekten çok iyi çalışıyor. Ayrıca bir CLI aracı olduğu için başlangıç maliyetinin en aza indirilmesi de gerekiyordu; fst crate'i zero-copy yüklemeyi desteklediğinden çalışma zamanı ek yükü oluşmuyor. FST derleme zamanında oluşturuluyor

• Gerçekten harika; keşke Almanca ve İngilizce için de böyle bir şey olsa. Almanca birleşik kelimeler hâlâ sık sık kafamı karıştırıyor