Pertama, mari kita lihat kendala pada masalah. Anda ingin menyimpan daftar kata untuk permainan dalam struktur data yang secara efisien mendukung masalah "anagram". Artinya, jika diberikan sebuah "rak" yang terdiri dari n huruf, berapakah semua kata dengan n-atau lebih sedikit huruf dalam daftar kata yang dapat dibuat dari rak tersebut. daftar kata akan menjadi sekitar 400 ribu kata, dan mungkin sekitar satu hingga sepuluh MB data string saat tidak dikompresi.
Trie adalah struktur data klasik yang digunakan untuk memecahkan masalah ini karena menggabungkan efisiensi memori dengan efisiensi pencarian. Dengan daftar kata sekitar 400 ribu kata dengan panjang yang wajar, Anda harus dapat menyimpan trie dalam memori. (Berlawanan dengan solusi semacam b-tree di mana Anda menyimpan sebagian besar pohon di disk karena terlalu besar untuk muat di memori sekaligus.)
Trie pada dasarnya tidak lebih dari pohon 26-ary (dengan asumsi Anda menggunakan alfabet Romawi) di mana setiap simpul memiliki huruf dan satu bit tambahan pada setiap simpul yang mengatakan apakah itu adalah akhir kata.
Jadi mari kita buat sketsa struktur datanya:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Ini tentu saja hanya sketsa; Anda mungkin ingin membuat ini memiliki pengakses dan konstruktor properti yang tepat dan yang lainnya. Juga, mungkin daftar datar bukanlah struktur data terbaik; mungkin semacam kamus lebih baik. Saran saya adalah membuatnya bekerja terlebih dahulu, lalu mengukur kinerjanya, dan jika tidak dapat diterima, bereksperimenlah dengan membuat perubahan untuk meningkatkan kinerjanya.
Anda dapat memulai dengan percobaan kosong:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Artinya, ini adalah simpul trie "root" yang mewakili awal kata.
Bagaimana Anda menambahkan kata "AA", kata pertama dalam kamus Scrabble? Nah, pertama buat simpul untuk huruf pertama:
root.Children.Add('A', false, new List<TrieNode>());
Oke, percobaan kita sekarang
^
|
A
Sekarang tambahkan simpul untuk huruf kedua:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Percobaan kami sekarang
^
|
A
|
A$ -- we notate the end of word flag with $
Besar. Sekarang misalkan kita ingin menambahkan AB. Kami sudah memiliki simpul untuk "A", jadi tambahkan simpul "B$" ke dalamnya:
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
dan sekarang kami memiliki
^
|
A
/ \
A$ B$
Terus seperti itu. Tentu saja, daripada menulis "root.Children[0]..." Anda akan menulis loop yang mencari trie untuk melihat apakah node yang Anda inginkan ada, dan jika tidak, buatlah.
Untuk menyimpan trie Anda di disk -- sejujurnya, saya hanya akan menyimpan daftar kata sebagai file teks biasa dan membangun kembali trie saat Anda membutuhkannya. Seharusnya tidak lebih dari 30 detik atau lebih, dan kemudian Anda dapat menggunakan kembali trie di memori. Jika Anda ingin menyimpan trie dalam beberapa format yang lebih mirip trie, seharusnya tidak sulit untuk membuat format serialisasi.
Untuk mencari trie untuk mencocokkan rak, idenya adalah untuk menjelajahi setiap bagian dari trie, tetapi untuk memangkas area di mana rak tidak mungkin cocok. Jika Anda tidak memiliki "A" di rak, Anda tidak perlu menurunkan simpul "A". Saya membuat sketsa algoritma pencarian di pertanyaan Anda sebelumnya.
Saya memiliki implementasi dari trie persisten gaya fungsional yang telah lama saya maksudkan untuk blog tetapi tidak pernah berhasil. Jika akhirnya saya mempostingnya, saya akan memperbarui pertanyaan ini.
