Implementasi Trie yang efisien untuk string unicode

Saya telah mencari implementasi String trie yang efisien. Sebagian besar saya telah menemukan kode seperti ini:

Implementasi referensial di Jawa (per wikipedia)

Saya tidak menyukai implementasi ini karena sebagian besar dua alasan:

1. Mereka hanya mendukung 256 karakter ASCII. Saya perlu membahas hal-hal seperti cyrillic.
2. Mereka sangat tidak efisien memori.

Setiap node berisi array 256 referensi, yaitu 4096 byte pada mesin 64 bit di Jawa. Masing-masing node dapat memiliki hingga 256 subnode dengan masing-masing 4096 byte referensi. Jadi Trie lengkap untuk setiap string karakter ASCII 2 akan membutuhkan sedikit lebih dari 1MB. Tiga string karakter? 256MB hanya untuk array dalam node. Dan seterusnya.

Tentu saja saya tidak berniat untuk memiliki semua 16 juta tiga karakter string dalam Trie saya, jadi banyak ruang yang terbuang sia-sia. Sebagian besar array ini hanyalah referensi nol karena kapasitasnya jauh melebihi jumlah sebenarnya dari kunci yang dimasukkan. Dan jika saya menambahkan unicode, array menjadi lebih besar (char memiliki nilai 64k bukannya 256 di Java).

Apakah ada harapan membuat trie yang efisien untuk string? Saya telah mempertimbangkan beberapa peningkatan atas jenis implementasi ini:

• Alih-alih menggunakan array referensi, saya bisa menggunakan array tipe integer primitif, yang mengindeks menjadi array referensi ke node yang ukurannya dekat dengan jumlah node aktual.
• Saya dapat memecah string menjadi 4 bagian bit yang akan memungkinkan untuk array node ukuran 16 dengan biaya pohon yang lebih dalam.

Untuk apa Anda menggunakan trie ini? Berapa jumlah total kata yang ingin Anda pegang, dan seberapa jarang karakter pendukungnya? Dan yang paling penting, adakah trie yang sesuai (versus peta awalan sederhana untuk daftar kata)?

Gagasan Anda tentang tabel perantara dan penggantian pointer dengan indeks akan berhasil, asalkan Anda memiliki serangkaian kata pendek yang relatif kecil dan rangkaian karakter yang jarang. Kalau tidak, Anda berisiko kehabisan ruang di tabel perantara Anda. Dan kecuali Anda melihat sekumpulan kata yang sangat kecil, Anda tidak akan benar-benar menghemat banyak ruang: 2 byte untuk yang pendek versus 4 byte untuk referensi pada mesin 32-bit. Jika Anda menggunakan JVM 64-bit, penghematan akan lebih banyak.

Gagasan Anda tentang memecah karakter menjadi potongan-potongan 4-bit mungkin tidak akan menyelamatkan Anda banyak, kecuali semua karakter yang Anda harapkan berada dalam kisaran yang sangat terbatas (mungkin OK untuk kata-kata yang terbatas pada huruf besar US-ASCII, tidak mungkin dengan corpus Unicode umum ).

Jika Anda memiliki set karakter yang jarang, maka HashMap<Character,Map<...>>mungkin implementasi terbaik Anda. Ya, setiap entri akan jauh lebih besar, tetapi jika Anda tidak memiliki banyak entri, Anda akan mendapatkan kemenangan secara keseluruhan. (sebagai catatan: saya selalu berpikir itu lucu bahwa artikel Wikipedia tentang Tries menunjukkan - mungkin masih - contoh berdasarkan struktur data hash, benar-benar mengabaikan pengorbanan ruang / waktu dari pilihan itu)

Akhirnya, Anda mungkin ingin menghindari trie sama sekali. Jika Anda melihat kumpulan kata-kata normal dalam bahasa manusia (10.000 kata digunakan secara aktif, dengan kata-kata panjangnya 4-8 karakter), Anda mungkin akan jauh lebih baik dengan a HashMap<String,List<String>, di mana kuncinya adalah seluruh awalan.

jika Anda menyandikan string ke UTF8 Anda dapat menggunakan trie bercabang 256 standar dan masih kompatibel dengan unicode

Anda juga harus mencatat bahwa hanya sekitar 70 karakter dari kemungkinan 128 karakter ascii (yang semuanya dikodekan ke 1 byte dalam UTF8) akan ditemukan paling banyak yang dapat Anda optimalkan untuk itu (seperti menyertakan digraf umum di tempat karakter kontrol yang tidak digunakan) )