Mengganti database SQLite 3GB dengan biner FST (finite-state transducer) 10MB

• Taskusanakirja adalah kamus Finlandia-Inggris yang menyediakan pencarian prefiks saat pengguna mengetik
• Dengan perluasan bentuk infleksi bahasa Finlandia, jumlah entri membengkak hingga 40 juta~60 juta, sehingga trie mencapai batasnya
• Solusi sementara SQLite FTS cepat, tetapi memerlukan unduhan awal 3GB
• FST berbasis Rust memangkas data SQLite menjadi biner sekitar 10MB, hemat 300x
• FST berbagi sufiks sekaligus prefiks, sehingga sangat cocok untuk pola infleksi berulang

---

Struktur pencarian Taskusanakirja dan batas awalnya

• Taskusanakirja, disingkat tsk, adalah kamus Finlandia-Inggris yang menyediakan pencarian progresif saat pengguna mengetik
• Fitur ini pada dasarnya adalah masalah pencarian prefiks, dan solusi baku untuk pencarian prefiks autocomplete adalah implementasi trie
• Implementasi pertama ditulis dalam Go, dan tujuan desain awalnya adalah mendistribusikan seluruh program sebagai satu .exe, satu .app, atau satu biner static-link
• Pada skala jumlah kata menengah enam digit, agar tidak mencocokkan semua entri yang bisa mencapai persentase satu digit dari keseluruhan, sistem hanya mengembalikan sekitar 50 atau 100 hasil pertama dan melakukan memoization untuk kombinasi 1, 2, dan 3 huruf
• Dengan pendekatan ini, trie dengan optimasi dasar bisa dimuat dalam sekitar 60MB, dan setelah dipakai intensif secara pribadi selama setahun, tidak ada latensi yang terasa

Masalah skala yang disebabkan data infleksi bahasa Finlandia

• Bahasa Finlandia adalah bahasa aglutinatif, sehingga satu kata dasar bisa memiliki lebih dari 100 akhiran jika semua kombinasi diperhitungkan
• Kombinasinya tidak teratur, dan sistem ejaan Finlandia yang sangat teratur membuat bentuk yang benar-benar diucapkan penutur tercermin langsung dalam tulisan, sehingga kata dasar bertambah panjang, bergeser, dan berubah saat bergabung dengan akhiran
• Pembelajar pemula mudah tersendat pada kata tertentu dalam kalimat seperti “Opiskelijassammekin on leijonan sydän”, dan tsk juga berupaya memuat informasi untuk membantu memecah kata pada batas yang benar
• Secara linguistik, perubahan semacam ini mencakup gradasi konsonan dan harmoni vokal, dan bahasa Finlandia menggunakan keduanya sekaligus
• Misalnya, katu berarti “street”, tetapi bentuk genitifnya bukan katun, melainkan kadun, karena t melemah menjadi d akibat suku kata tertutup
• Jika struktur ini dikalikan dengan 15 kasus, 2 bentuk jamak, 6 sufiks posesif, dan jumlah enklitik yang tidak pasti, trie naif tidak bisa membagi biaya bagian akhir seperti -ssa-mme-kin yang dibagi oleh ribuan kata
• Sekitar 400 ribu entri masih bisa dipertahankan dalam trie dengan sekitar 50MB RAM, tetapi pendekatan yang sama tidak bisa diskalakan ke 40 juta~60 juta entri
• Sebagai solusi sementara, bentuk infleksi dimasukkan ke database SQLite FTS terpisah lalu dicari saat diperlukan; performanya tetap tanpa latensi yang terasa, tetapi memerlukan unduhan 3GB pada pertama kali

Hasil setelah beralih ke Rust dan FST

• Sembilan bulan kemudian, saat mencoba lagi dengan Rust, ditulis program Rust minimal yang mengekstrak data dari database SQLite 3GB lalu mengompresnya menjadi FST
• Pemicunya adalah tulisan BurntSushi aka Andrew Gallant berjudul Index 1,600,000,000 Keys with Automata and Rust, dengan gagasan inti bahwa mesin keadaan hingga dapat merepresentasikan himpunan atau map string yang terurut secara ringkas dan cepat
• Biner hasilnya menjadi sekitar 10MB, atau penghematan ruang sekitar 300x dibanding database SQLite 3GB
• Kegunaan ini juga sangat cocok dengan fst crate, karena masalahnya adalah memetakan kembali bentuk infleksi dan konjugasi dari bahasa yang sangat aglutinatif ke definisi asalnya
• Trie mengompresi prefiks, sedangkan FST mengompresi prefiks dan sufiks sekaligus
• Dalam korpus kamus Finlandia, hanya ada sedikit sufiks populer yang sangat sering berulang, sehingga pembagian sufiks memberi dampak besar
• Datanya adalah data statis yang tidak berubah saat runtime, sehingga kelemahan terbesar fst bisa dihindari

Mengapa FST menjadi lebih kecil daripada trie

• Kunci utama yang membuat FST jauh lebih kecil daripada trie pada data bahasa alami adalah pembagian sufiks
• Trie berbagi prefiks seperti kadun dan kaduille yang berbagi tiga node awal, tetapi jalur sufiks yang berbeda tetap disimpan terpisah
• Deterministic acyclic finite state automaton minimal menggabungkan dua subtree yang secara struktural identik
• Dalam korpus tempat 100 ribu kata berakhir dengan kira-kira 12 pola infleksi yang sama, penggabungan ini menghasilkan penghematan memori yang besar
• Heuristik inti dalam kasus ini adalah mengganti database generik rakitan cepat dengan struktur data khusus yang kecil dan statis, yang hanya melakukan tepat apa yang dibutuhkan, dan dari situ memperoleh penghematan memori 300x

Peran solusi sementara SQLite dan ukuran distribusi

• Pilihan SQLite sembilan bulan sebelumnya adalah hasil dari memilih “sesuatu yang buruk tapi mudah” alih-alih “tidak bisa membuat yang bagus”, dan pada praktiknya itu berhasil
• Karena sudah memahami B-tree SQLite dan ekstensi Full Text Search, saat itu itulah solusi yang paling cepat untuk diuji
• Ekstensi FTS yang sama juga dipakai untuk beberapa fitur yang lebih jarang digunakan dan tidak ada di alpha tsk v2.0.0, tetapi jika merusak memory footprint saat ini, kemungkinan akan dihapus sepenuhnya
• Versi Pro v2 diperkirakan sekitar 20MB dengan semuanya disertakan, yang berarti 3x lebih kecil daripada versi gratis v1
• tsk awalnya dimulai sebagai program TUI Go, berkembang dari prototipe berbasis fzf sebelumnya bernama finstem, dan terhubung dengan the highest-ROI program I’ve written so far
• taskusanakirja berarti “pocket dictionary” dalam bahasa Finlandia, dan standar yang dipakai tetap bahwa jika tidak muat di laptop tua, itu bukan kamus saku melainkan lebih mirip kamus Oxford lama yang dikompilasi
• Ada pola berulang berupa “tidak apa-apa menyelesaikan masalah dua kali”; alih-alih berhenti karena rasa bersalah bahwa seharusnya mencari implementasi lama yang lebih baik, kadang membuat ulang beberapa roda sendiri justru membuat seseorang lebih cepat mencapai batas yang nyata
• Sudut pandang ini terhubung dengan “practice” dalam Caplanian view, dan Do Ten Times as Much diajukan sebagai nasihat yang tidak nyaman tetapi efektif

[GN⁺]

Opini di Lobste.rs

• Tulisannya sendiri menarik, dan menyenangkan melihat alat yang tepat diterapkan pada pekerjaan yang tepat hingga menghasilkan peningkatan skala satu digit, tetapi catatan kaki terakhir justru lebih membekas daripada isi utamanya
  Itu dengan tepat menangkap kegelisahan yang membuat kita berhenti: rasa bersalah karena alat yang sedang kita buat mungkin sudah pernah diimplementasikan lebih baik oleh orang lain 30~40 tahun lalu. Namun itu jebakan, dan gagasan bahwa kita perlu membuat ulang beberapa roda agar bisa mencapai batas pemahaman tentang cara membuat roda terasa sangat mengena. Di kebanyakan bidang, empat atau lima kali sudah cukup, dan bahkan di bidang yang ketat seperti matematika atau ilmu komputer, mungkin sekitar dua puluh tiga kali pun cukup; pertanyaannya adalah bahwa pertanyaan-pertanyaan yang muncul saat membangun ulang sendiri akan membawa kita ke garis depan yang sebenarnya jauh lebih cepat daripada sekadar belajar

  • Poin terkait penting di artikel utamanya adalah bahwa implementasi brute-force yang tidak efisien dengan SQLite DB juga tetap bernilai sebagai implementasi acuan
    Karena sudah ada implementasi referensi yang benar-benar berjalan, jadi lebih mudah membuat implementasi efisien untuk menggantikannya
  • Ini sangat pas dengan masalah yang sedang saya hadapi. Saya ingin membuat sesuatu yang dioptimalkan untuk ruang masalah saya, tetapi saya terhenti karena tahu bahwa masalah yang sudah digeneralisasi itu sebenarnya sudah terpecahkan
    Namun ketika melihat solusi yang ada, terasa ada banyak beban yang sebenarnya tidak saya butuhkan. Dari pengalaman saya tahu bahwa ada nilai dalam mendorong ide saya sendiri, tetapi saya terus berpikir jangan-jangan ada sesuatu yang terlewat; setelah membaca ini, saya memutuskan untuk mencobanya saja. Kalaupun gagal, tetap ada pelajaran dari prosesnya

• Sangat keren. Mengingatkan saya pada Compressing Icelandic name declension patterns into a 3.27 kB trie

• Saat mengimplementasikan bot Scrabble, saya jadi mengenal struktur data terkait bernama DAWG (Directed Acyclic Word Graph), dan tampaknya itu cukup umum untuk keperluan seperti ini
  Perbedaan utamanya dengan crate fst tampaknya adalah bahwa ia tidak memetakan setiap kata ke bilangan bulat unik. Ukurannya juga berkurang drastis dan performanya meningkat luar biasa. Bot Scrabble pada dasarnya harus memfilter seluruh kamus untuk mencari kata yang cocok dengan regex sederhana seperti ..cat.., tetapi pada praktiknya ia harus menangani semua regex sederhana yang mungkin dari papan saat ini. Pekerjaan yang dulu butuh menunggu sekitar 1 menit turun menjadi jeda yang nyaris tak terasa

  • Makalah DAWG karya Appel dan Jacobson dari 1988 sempat muncul lagi belum lama ini dan juga pernah dibagikan sebelumnya

• Tulisan yang ditautkan ini juga layak dibaca: https://burntsushi.net/transducers/

• fst pada akhirnya juga menjadi alat yang dipakai untuk dukungan bahasa Jerman di srgn, setelah direkomendasikan langsung oleh Andrew
  Ini adalah ruang masalah yang sama, yakni mengompresi prefiks dan sufiks yang sama, dan hasilnya bekerja sangat baik. Karena ini juga alat CLI, biaya startup yang minimal juga penting, dan crate fst mendukung zero-copy loading, jadi tidak ada overhead runtime. FST dibuat pada waktu kompilasi

• Benar-benar keren, dan andai ada yang seperti ini juga untuk bahasa Jerman dan Inggris. Kata majemuk bahasa Jerman masih sering membingungkan saya