- Penanganan deklinasi nama orang bahasa Islandia berubah menjadi empat bentuk tergantung pada konteks
- Mengembangkan fitur dengan pustaka JavaScript berbasis data untuk mengembalikan kasus gramatikal yang tepat pada nama yang dimasukkan
- Menyimpan semua nama secara langsung menimbulkan peningkatan ukuran dan masalah kelangkaan data, sehingga diselesaikan dengan struktur trie dan teknik kompresi
- Berkat kompresi trie, inferensi otomatis berbasis pola umum memungkinkan cakupan lebih dari 80% data dengan basis data yang sangat kecil
- Pada skenario biasa mencapai akurasi di atas 74%, dan untuk sektor publik serta kasus yang menuntut ketelitian tinggi disediakan versi strict terpisah
Latar Belakang Masalah
- Pada antarmuka berbahasa Islandia, menampilkan nama orang menghadapi tantangan karena deklinasi
- Nama dalam bahasa Islandia memiliki bentuk berbeda berdasarkan empat kasus gramatikal: nominatif, akusatif, datif, dan genitif
- Basis data biasanya menyimpan nama dalam bentuk nominatif, sehingga saat konteks memerlukan kasus lain menjadi sulit
- Penggunaan bentuk yang tidak tepat membuat terlihat tidak natural bagi penutur asli
Pengumpulan dan Pembersihan Data
- Islandia membuka data DIM (Database of Icelandic Morphology) yang dikelola oleh Árnastofnun
- Data deklinasi nama dapat diproses menjadi CSV dengan Kristín’s Format (K-format)
- Meskipun seluruh data DIM berjumlah 7 juta baris dan sangat besar, setelah memfilter nama pribadi resmi yang disetujui (4.500 nama) data deklinasi dapat diperoleh untuk lebih dari 3.600 nama
- Untuk setiap nama dapat disusun array bentuk dari nominatif hingga genitif
Struktur Dasar Pustaka
- Implementasi awal dimulai dari fungsi applyCase yang mengembalikan bentuk tepat dari array nama~perubahan kasus
- Namun, pemuatan berbasis array sederhana menghasilkan ukuran besar (30kB gzip)
- Ada keterbatasan bahwa nama yang tidak termasuk dalam data tidak bisa ditangani
Penghapusan Duplikasi dan Ekstraksi Pola
- Mengekstrak awalan umum di antara empat bentuk nama lalu menyimpan hanya himpunan sufiks (suffix encoding) untuk meminimalkan duplikasi
- Ditemukan banyak nama yang mengikuti pola deklinasi yang sama
Penerapan Trie untuk Pencocokan Pola
- Melalui struktur trie (penyisipan terbalik berbasis sufiks), memetakan nilai untuk grup nama yang berbagi pola serupa menjadi lebih optimal
- Menyimpan informasi deklinasi satu kali di bawah pola bersama (akhiran nama) sehingga prediksi untuk nama baru tetap tinggi
Kompresi dan Optimisasi Trie
- Jika nilai pada setiap leaf subpohon sama, nilai tersebut dialokasikan ke node induk dan anak-anak dihapus untuk mengompresi pohon
- Hasilnya, jumlah node berkurang hingga 15,4% dan ukuran menyusut menjadi 4,01kB
- Leaf saudara yang memiliki nilai sama digabung menjadi satu node dalam kompresi tahap kedua, mencapai 3,27kB
Kinerja dan Generalisasi Trie
- Saat ada masukan nama baru, deklinasi otomatis berbasis pola serupa dimungkinkan
- Pada nama yang tidak dikenal, akurasi deklinasi mencapai 74% benar dan 26% salah, sementara tingkat kesalahan pada pengguna nyata hanya 0,34%
- Akurasi inferensi meningkat semakin tinggi keteraturan (regularity) dan kelengkapan (comprehensiveness) data
Penerapan dan Distribusi Pustaka Nyata
- Akhirnya, didistribusikan sebagai pustaka beygla yang menggunakan trie terkompresi
- Disediakan dalam ukuran minimum (4,46kB) dan modul strict yang lebih ketat dan lengkap (15kB)
- Versi strict dipilih untuk konteks yang memerlukan akurasi 100% seperti dokumen publik, sedangkan versi ringan cocok untuk web app umum
Kesimpulan dan Potensi Ekstensi
- Kompresi data pola deklinasi bahasa dengan trie berpotensi diterapkan untuk otomatisasi deklinasi nama, alamat, dan nomina lain pada bahasa-bahasa infleksional selain bahasa Islandia
- Kombinasi data dengan tingkat keteraturan tinggi dan kompresi trie menjadi solusi untuk memaksimalkan efisiensi data dan kinerja pada otomatisasi deklinasi isomorfik
Ucapan Terima Kasih
- Pengembangan beygla mencakup banyak umpan balik dari para ahli dan optimisasi
- Kompresi tambahan pada trie mengurangi ukuran dari 3,43kB menjadi 3,27kB
Ringkasan
- Kasus otomatisasi deklinasi nama bahasa Islandia yang dipresentasikan di sini menjadi lebih ringan dan otomatis melalui struktur trie berbasis pola
- Menjadi contoh strategis pengolahan data praktis dengan pertimbangan kompromi ukuran–akurasi yang tepat
1 komentar
Komentar Hacker News
Saat pertama kali belajar bahasa Spanyol di SMA, saya pernah memakai software Windows yang menampilkan infinitif dan kala secara beruntun, lalu saya harus mengisi konjugasi kata kerjanya. Latihan seperti ini membuat aturan tata bahasa tertanam dan saya jadi fasih. Namun ketika belajar bahasa Rusia, deklinasi kasus tiba-tiba terasa sulit, dan saya tidak pernah berhasil menemukan aplikasi yang bisa menjelaskan atau melatih pola serupa. Saya penasaran apakah ada yang tahu aplikasi untuk tujuan seperti ini (web atau macOS/iOS)
Di Anki ada dek flashcard yang memakai metode "KOFI (Konjugation First)". KOFI berarti mempelajari semua pola konjugasi terlebih dahulu sebelum mulai belajar bahasanya. Setelah belajar bahasa Prancis dan merasa kemampuan konjugasi saya kurang, saya mencoba metode ini belakangan; walau tetap bisa berkomunikasi sehari-hari meski tata bahasa saya salah, itu belum mencapai level yang saya inginkan. Tujuan metode ini adalah menguasai semua pola konjugasi dalam waktu singkat sebelum mempelajari bahasanya. Suatu hari saya ingin benar-benar menerapkannya pada bahasa baru. Minat saya pada bahasa Prancis sudah berkurang jadi saya berhenti di tengah jalan. Tautan dek Anki terkait
Saat belajar bahasa Rusia, saya pernah membuat skrip yang menggabungkan modul Python spaCy dengan modul besar untuk bahasa Rusia untuk melakukan lemmatisasi berbasis konteks dan ekstraksi tag tata bahasa. Namun saat kemampuan bahasa Rusia saya benar-benar meningkat, ternyata jauh lebih efektif untuk berhenti mencoba membongkar perubahan secara logis, lalu membangun perpustakaan pola di kepala saya—termasuk pengecualiannya—melalui pengalaman pemakaian dan pengulangan. Sebagai catatan, konteks yang dimaksud di sini adalah makna di dalam kalimat
Saat belajar bahasa Spanyol secara otodidak 25 tahun lalu, saya memakai kamus Spanyol/Inggris. Pada infinitif kata kerja ada indeks angka yang mengelompokkannya berdasarkan pola konjugasi yang sama. Di bagian depan kamus ada tabel konjugasi lengkap untuk kata kerja perwakilan dari tiap grup, untuk semua kala. Kata kerja tak beraturan punya indeks terpisah, dan tetap dikelompokkan dengan kata kerja tak beraturan yang mirip (misalnya: tener, detener). Semua kata kerja tertata rapi menjadi beberapa puluh pola unik. Saya pernah terpikir membuat software kuis yang memanfaatkan sistem ini, tetapi tidak pernah jadi. Saya penasaran apakah pola reverse-string trie yang disebut di artikel bisa dipakai juga untuk klasifikasi seperti ini
Untuk menguasai deklinasi kasus bahasa Rusia, saya pernah punya ide membuat flashcard berisi kombinasi preposisi + kata sifat + kata benda agar hafal lebih cepat. Saya sebelumnya pernah belajar Latin, dan untuk deklinasi kasus Latin saya tidak berharap bisa menghafalnya dengan cepat (kecuali mungkin kalau saya biarawan?), tetapi untuk bahasa Rusia saya ingin cepat menguasainya. Namun akhirnya ini tidak pernah berkembang menjadi proyek
Saya memakai ConjuGato di iOS untuk latihan konjugasi bahasa Spanyol. Dalam mode game, yang diberikan adalah infinitif/kala/orang dan kita harus memikirkan bentuk konjugasinya. Ada juga opsi berlatih hanya kata kerja tak beraturan, jadi efektif untuk mempelajari pengecualian
Untuk 800 nama yang informasi deklinasinya hilang di basis data, solusi paling langsung tampaknya adalah memberi bentuk kasusnya secara manual. Penutur asli mungkin bisa menyelesaikannya dalam beberapa jam, dan bahkan untuk nama yang benar-benar asing, setidaknya masih bisa menebak bentuk yang tidak terasa jelas janggal. Atau bisa juga menyuruh LLM melakukannya dengan sangat murah. Tetap saja, mengenkode hasilnya ke struktur trie seperti ini untuk didistribusikan masih ide yang bagus. Hanya saja, trie tidak perlu dipakai sampai menjadi penaksir deklinasi kasus
Menangani lebih banyak nama memang diinginkan—di DIM ini memang area yang perlu terus dilengkapi. Di Islandia, nama baru sering ditambahkan ke daftar nama yang diizinkan, jadi celah seperti ini memang akan selalu ada. Saya pribadi kurang yakin untuk menambahkan datanya sendiri, dan setiap kali meninjau hasil untuk 100 nama yang belum terverifikasi, cukup sering saya berpikir, “apa ini benar?” Saya juga beberapa kali mencari nama serupa di DIM dan merasa, “saya sendiri tidak akan mendeklinasikannya seperti itu.” Karena itu saya memakai data DIM sebagai ‘source of truth’ yang dipelihara ahli bahasa
Pengerjaan manual bagus, tetapi tetap ada batasnya untuk nama yang tidak ada di daftar resmi (misalnya nama asing). Saya juga tinggal di negara yang punya daftar nama terpusat, tetapi orang bisa mengajukan pengecualian, dan orang yang lahir sebelum daftar itu ada atau para imigran bisa saja punya nama yang tidak ada di daftar. Dalam berbagai situasi gabungan seperti ini, fitur ‘prediksi bentuk deklinasi yang kira-kira tepat’ tetap berguna
Saya belum menemukan alasan untuk menganggap LLM lebih baik daripada trie dalam memprediksi deklinasi kasus (kalau contoh nyatanya tidak ada di data pelatihan LLM, pencarian web mungkin akan lebih baik)
Ini membuat saya penasaran apakah LLM yang ada sekarang sebenarnya sudah mempelajari pola seperti ini
Saya tidak yakin Rails menangani masalah ini secara otomatis, tetapi dulu ia memang suka melakukan sihir seperti itu. Saya pernah melihat source code
pluralise, dan bahkan aturan jamak tak beraturan bahasa Wales pun sudah dienkode di sanaSalah satu ide optimasi adalah, alih-alih trie langsung memetakan ke string sufiks itu sendiri, buatlah array sufiks unik lalu dari trie cukup menunjuk ke indeks di array tersebut. Misalnya:
lalu mereferensikan indeks seperti ini:
Saya coba langsung dengan Claude Code, dan dalam keadaan gzip justru bertambah 100 byte (3456 -> 3556), sementara ukuran sebelum kompresi hanya turun 20%. Sepertinya karena gzip sendiri sudah sangat optimal terhadap pola yang berulang
Selangkah lebih jauh, mungkin saja sufiksnya sendiri dimasukkan ke trie, lalu subpohon yang identik dideteksi dan dideduplikasi. Kalau bisa memakai gzip, rasanya pasti ada cara optimasi cerdas dengan memanfaatkan array sufiks. Jika memakai format optimasi biner, mungkin bisa lebih baik lagi
Secara pribadi saya terus merasa pasti ada solusi ajaib yang bisa menangani ini dalam keadaan tidak terkompresi dengan ukuran <1kb. Mungkin membuat daftar regex yang diminimalkan untuk mengklasifikasikan nama dengan akurasi 100%? Bloom filter yang sangat besar? Atau pendekatan yang memakai fitur khusus alih-alih hash umum?
Ini terasa seperti soal interview dari mimpi buruk. Memakai trie secara terbalik (dalam urutan balik) adalah sesuatu yang mungkin cuma kepakai sekali seumur hidup, tetapi kalau kepakai sekali itu, Anda akan terlihat seperti penyihir
Daripada melakukan ini di JS, mungkin basis data saja yang mengembalikan semua kombinasi nama-kasus, lalu saat ditampilkan cukup dipilih yang dibutuhkan. Artinya, ini ditangani di lapisan lokalisasi. Saya penasaran bagaimana jadinya dalam situasi lintas bahasa. Jika UI Islandia menangani nama Prancis, sepertinya akan selalu memakai nominatif; dan jika UI Inggris menangani nama Islandia, mungkin juga sama. Pada akhirnya kebutuhan ini mungkin terutama besar dalam konteks saat menyebut/menyapa pengguna secara langsung atau di panel admin (“user x membalas user y”) dan semacamnya
Ada 88 nama dengan pola deklinasi tertentu yang berakhir dengan “idur”, “tur”, “ður”, tetapi sufiks yang sama tidak selalu mengikuti pola deklinasi yang sama. Masalahnya terlihat seperti aturan sederhana, padahal sebenarnya sangat menarik. Apakah pola sufiks ini berkaitan dengan pelafalan suku kata sebelumnya? Kalau ingin menangani nama yang tidak dikenal dengan lebih baik, saya jadi penasaran apakah alih-alih sekadar berbasis huruf, kita perlu mengekstrak representasi pelafalan nama dengan NLP lalu mencarinya lewat trie atau semacamnya
Hati-hati, kalau terlalu jauh memikirkan ini bisa-bisa terseret ke diskusi tentang Dependent Types
Ide yang tajam. Faktanya, bahkan nama dengan pelafalan yang sama pun kadang punya pola deklinasi berbeda. Misalnya:
Dalam situasi beygla/strict, perfect hashing mungkin layak dipertimbangkan sebagai alternatif
Saya terkejut deklinasi kasus nama dalam bahasa Islandia cukup sederhana dan cukup punya pola yang deterministik sehingga pendekatan seperti ini bisa bekerja baik. Bahasa biasanya jauh lebih rumit dari itu