Apa perbedaan antara pohon radix dan percobaan Patricia?

Saya belajar tentang pohon radix (alias percobaan terkompresi) dan Patricia mencoba, tetapi saya menemukan informasi yang bertentangan tentang apakah mereka sebenarnya sama atau tidak. Pohon radix dapat diperoleh dari trie normal (tidak terkompresi) dengan menggabungkan node dengan orang tua mereka ketika node adalah satu-satunya anak. Ini juga berlaku untuk percobaan Patricia. Dalam hal apa kedua struktur data itu berbeda?

Misalnya, NIST mencantumkan keduanya sebagai sama:

Pohon patricia

(struktur data)

Definisi: Representasi ringkas dari trie di mana setiap simpul yang merupakan anak tunggal digabungkan dengan induknya.

Juga dikenal sebagai pohon radix.

Banyak sumber di web mengklaim hal yang sama. Namun, percobaan Patricia tampaknya adalah kasus khusus pohon radix. Entri Wikipedia mengatakan:

PATRICIA mencoba adalah percobaan radix dengan radix sama dengan 2, yang berarti bahwa setiap bit kunci dibandingkan secara individual dan setiap node adalah cabang dua arah (yaitu, kiri versus kanan).

Saya tidak begitu mengerti hal ini. Apakah perbedaannya hanya pada perbandingan yang dibuat saat melakukan pencarian? Bagaimana setiap simpul bisa menjadi "cabang dua arah"? Bukankah seharusnya ada ALPHABET_SIZEcabang paling mungkin untuk node yang diberikan?

Adakah yang bisa menjelaskan hal ini? Untuk tujuan praktis, apakah percobaan radix biasanya dilaksanakan ketika Patricia mencoba (dan, karenanya, sering dianggap sama)? Atau tidak dapat dibuat generalisasi seperti itu?

Saya menemukan posting ini sangat membantu.

Untuk melihat perbedaan antara percobaan Patricia dan pohon radix, penting untuk dipahami:

• Gagasan radix , karena Patricia mencoba adalah pohon radix dengan radix sama dengan 2.
• $r$$2^r$

Misalkan kita memasukkan kunci tersenyum , tersenyum , dan tersenyum (dalam urutan ini) dalam sebuah trio Patricia. Representasi biner dari kunci-kunci ini adalah sebagai berikut:

Perhatikan bahwa senyum adalah awalan dari senyum , dan, menganalisis representasi biner, kita dapat melihat bahwa bit pertama yang berbeda (dari kiri ke kanan) adalah 0 (disorot dengan warna merah di baris kedua); untuk alasan ini, senyum akan menjadi anak kiri dari senyum . Demikian pula, senyum akan menjadi anak yang tepat untuk tersenyum karena mereka berbagi awalan yang sama hingga sedikit yang nilainya 1 (disorot dengan warna merah di baris ketiga). Trie Patricia yang dihasilkan setelah memasukkan tiga kunci adalah sebagai berikut:

Jika radix adalah, misalnya, 4, maka node internal dapat memiliki, paling banyak, empat anak (dengan tepi mereka masing-masing diberi label 00, 01, 10, dan 11). Dalam hal ini, kunci akan dibandingkan dengan potongan 2 bit, dan bukan 1 (seperti dalam Patricia mencoba).

Dalam hal apa kedua struktur data itu berbeda?

Untuk pemahaman saya, satu-satunya perbedaan adalah radix, yang sama dengan 2 dalam kasus Patricia mencoba. Nilai ini dapat berupa kekuatan 2 pada pohon radix biasa.

Apakah perbedaannya hanya pada perbandingan yang dibuat saat melakukan pencarian?

$\log_2{R}$$R$

Bagaimana setiap simpul bisa menjadi "cabang dua arah"? Bukankah seharusnya ada ALPHABET_SIZEcabang paling mungkin untuk node yang diberikan?

Radix menetapkan jumlah maksimum anak-anak yang dapat dimiliki simpul-simpul pohon radix. Misalnya, ketika radix = 2, setiap node dapat memiliki paling banyak dua anak. Ini adalah kasus percobaan Patricia (juga dikenal sebagai pohon radix biner).

Apakah radix mencoba biasanya diterapkan sebagai Patricia mencoba (dan, karenanya, sering dianggap sama)? Atau tidak dapat dibuat generalisasi seperti itu?

Sejujurnya, saya tidak punya jawaban untuk pertanyaan ini. Tampaknya kedua struktur data diusulkan sekitar waktu yang sama oleh penulis yang berbeda. Karena alasan historis yang saya tidak sadari, kedua istilah ini masih hidup sampai sekarang.

Trie Patricia adalah trix radial biner yang dihasilkan dari penerapan algoritma PATRICIA ke data alfanumerik.

PATRICIA adalah singkatan dari Algoritma Praktis Untuk Mengambil Informasi yang Dikodekan dalam Alfanumerik [ makalah asli oleh Donald R. Morrison ]. Makalah ini mendefinisikan kosakata dasar yang terdiri dari MULAI, BERHENTI, AKHIR, L-PHRASE, CABANG, TWIN, dan RANTAI. Percobaan PATRICIA adalah percobaan yang dihasilkan dari penerapan algoritma ini - percobaan radiary biner di mana radix, r, adalah 2 [ wikipedia ] (dan di atas); pilihan biner di setiap node ketika melintasi trie).

Namun, dalam praktiknya, istilah Patricia tampaknya digunakan dengan r> = 2 (yaitu radix mencoba), di mana alogoritma penyimpanan dan pencarian yang sama digunakan. Misalnya ini diberi judul patricia. The Ethereum Patricia Merkle Trie adalah contoh lain, di mana r adalah 16 pada node tertentu.