Bagaimana Saya Memilih Antara Tabel Hash dan Trie (Pohon Awalan)?

Jadi jika saya harus memilih antara tabel hash atau pohon awalan apa faktor pembeda yang akan membuat saya memilih satu dari yang lain. Dari sudut pandang naif saya sendiri, sepertinya menggunakan trie memiliki beberapa overhead tambahan karena tidak disimpan sebagai array tetapi dalam hal run time (dengan asumsi kunci terpanjang adalah kata bahasa Inggris terpanjang) pada dasarnya bisa O (1) (dalam kaitannya dengan batas atas). Mungkin kata bahasa Inggris terpanjang adalah 50 karakter?

Tabel hash segera dicari setelah Anda mendapatkan indeks . Namun, hasutan kunci untuk mendapatkan indeks tampaknya dapat dengan mudah mengambil hampir 50 langkah.

Bisakah seseorang memberi saya perspektif yang lebih berpengalaman tentang ini? Terima kasih!

Keuntungan mencoba:

Dasar:

• Waktu pencarian O (k) yang dapat diprediksi di mana k adalah ukuran kunci
• Pencarian dapat memakan waktu kurang dari k waktu jika tidak ada
• Mendukung traversal yang dipesan
• Tidak perlu fungsi hash
• Penghapusan sangat mudah

Operasi baru:

• Anda dapat dengan cepat mencari prefiks kunci, menghitung semua entri dengan prefiks tertentu, dll.

Keuntungan dari struktur yang terhubung:

• Jika ada banyak prefiks yang sama, ruang yang dibutuhkannya digunakan bersama.
• Percobaan yang tidak dapat diubah dapat berbagi struktur. Alih-alih memperbarui trie di tempat, Anda bisa membuat yang baru yang hanya berbeda di sepanjang satu cabang, di tempat lain menunjuk ke trie lama. Ini dapat berguna untuk konkurensi, beberapa versi tabel secara bersamaan, dll.
• Trie yang tidak dapat diubah dapat dikompres. Artinya, ia juga dapat berbagi struktur pada sufiks , dengan hash-consing.

Keuntungan dari hashtables:

• Semua orang tahu hashtables, bukan? Sistem Anda sudah memiliki implementasi yang dioptimalkan dengan baik, lebih cepat daripada mencoba untuk sebagian besar tujuan.
• Kunci Anda tidak perlu memiliki struktur khusus.
• Lebih hemat ruang daripada struktur trie tertaut yang jelas ( lihat komentar di bawah )

Itu semua tergantung pada masalah apa yang Anda coba selesaikan. Jika yang perlu Anda lakukan hanyalah penyisipan dan pencarian, gunakan tabel hash. Jika Anda perlu memecahkan masalah yang lebih kompleks seperti kueri terkait prefiks, percobaan mungkin merupakan solusi yang lebih baik.

Semua orang tahu tabel hash dan penggunaannya tetapi itu tidak persis waktu pencarian konstan, itu tergantung pada seberapa besar tabel hash, kompleksitas komputasi dari fungsi hash.

Membuat tabel hash yang besar untuk pencarian yang efisien bukanlah solusi yang elegan di sebagian besar skenario industri di mana latensi / skalabilitas kecil pun penting (misalnya: perdagangan frekuensi tinggi). Anda harus memperhatikan tentang struktur data agar dioptimalkan untuk ruang yang digunakan dalam memori juga untuk mengurangi kehilangan cache.

Contoh yang sangat bagus dimana trie lebih sesuai dengan kebutuhan adalah messaging middleware. Anda memiliki jutaan pelanggan dan penerbit pesan ke berbagai kategori (dalam istilah JMS - Topik atau pertukaran), dalam kasus seperti itu jika Anda ingin memfilter pesan berdasarkan topik (yang sebenarnya adalah string), Anda pasti tidak ingin membuat tabel hash untuk jutaan langganan dengan jutaan topik. Pendekatan yang lebih baik adalah menyimpan topik dalam tahap percobaan, jadi ketika pemfilteran dilakukan berdasarkan kecocokan topik, kerumitannya tidak bergantung pada jumlah topik / langganan / penerbit (hanya bergantung pada panjang string). Saya menyukainya karena Anda dapat berkreasi dengan struktur data ini untuk mengoptimalkan kebutuhan ruang dan karenanya kehilangan cache yang lebih rendah.

Gunakan pohon:

1. Jika Anda membutuhkan fitur auto complete
2. Temukan semua kata yang diawali dengan 'a' atau 'ax' dan seterusnya.
3. Pohon sufiks adalah bentuk khusus dari pohon. Pohon sufiks memiliki seluruh daftar keuntungan yang tidak dapat dicakup oleh hash.

Ada sesuatu yang belum pernah saya lihat siapa pun menyebutkan secara eksplisit yang menurut saya penting untuk diingat. Baik tabel hash dan percobaan dari berbagai jenis biasanya akan memiliki O(k)operasi, di mana kpanjang string dalam bit (atau ekuivalen dalam karakter).

Ini dengan asumsi Anda memiliki fungsi hash yang baik. Jika Anda tidak ingin "peternakan" dan "hewan ternak" di-hash ke nilai yang sama, maka fungsi hash harus menggunakan semua bit kunci, sehingga mencirikan "hewan ternak" harus memakan waktu sekitar dua kali lebih lama "farm" (kecuali jika Anda berada dalam skenario hash bergulir, tetapi ada skenario penghematan operasi yang serupa dengan mencoba juga). Dan dengan vanilla trie, jelas mengapa memasukkan "hewan ternak" akan memakan waktu sekitar dua kali lebih lama daripada "peternakan" saja. Dalam jangka panjang, ini juga berlaku dengan percobaan terkompresi.

Penyisipan dan pencarian pada trie adalah linier dengan panjang string input O (s).

Hash akan memberi Anda O (1) untuk pencarian dan penyisipan, tetapi pertama-tama Anda harus menghitung hash berdasarkan string input yang lagi-lagi adalah O (s).

Kesimpulannya, kompleksitas waktu asimtotik adalah linier pada kedua kasus.

Trie ini memiliki lebih banyak overhead dari perspektif data, tetapi Anda dapat memilih trie terkompresi yang akan membuat Anda kembali, kurang lebih sama dengan tabel hash.

Untuk memutuskan hubungan, tanyakan pada diri Anda pertanyaan ini: Apakah saya hanya perlu mencari kata lengkap? Atau apakah saya perlu mengembalikan semua kata yang cocok dengan awalan? (Seperti dalam sistem input teks prediksi). Untuk kasus pertama, gunakan hash. Ini adalah kode yang lebih sederhana dan lebih bersih. Lebih mudah untuk menguji dan memelihara. Untuk kasus penggunaan yang lebih rumit di mana prefiks atau sufix penting, lakukan trie.

Dan jika Anda melakukannya hanya untuk bersenang-senang, menerapkan uji coba akan memanfaatkan hari Minggu sore dengan baik.

Implementasi HashTable lebih hemat ruang dibandingkan dengan implementasi Trie dasar . Tetapi dengan string, pengurutan diperlukan di sebagian besar aplikasi praktis. Tapi HashTable benar-benar mengganggu tatanan leksografis. Sekarang, jika aplikasi Anda melakukan operasi berdasarkan urutan leksografis (seperti pencarian parsial, semua string dengan awalan yang diberikan, semua kata dalam urutan yang diurutkan), Anda harus menggunakan Tries. Untuk pencarian saja, HashTable harus digunakan (karena bisa dibilang, ini memberikan waktu pencarian minimum).

PS: Selain itu, Ternary Search Trees (TSTs) akan menjadi pilihan yang sangat baik. Waktu pencariannya lebih dari HashTable, tetapi hemat waktu di semua operasi lainnya. Juga, lebih hemat ruang daripada mencoba.

Beberapa aplikasi (biasanya tertanam, real-time) mengharuskan waktu pemrosesan tidak bergantung pada data. Dalam hal ini, tabel hash dapat menjamin waktu eksekusi yang diketahui, sementara trie bervariasi berdasarkan data.