Apa perbedaan antara struktur data trie dan radix trie?

Apakah struktur data trie dan radix trie sama?

Jika sama, lalu apa yang dimaksud dengan radix trie (AKA Patricia trie)?

Pohon radix adalah versi terkompresi dari trie. Dalam trie, di setiap sisi Anda menulis satu huruf, sedangkan di pohon PATRICIA (atau pohon radix) Anda menyimpan seluruh kata.

Sekarang, anggaplah Anda memiliki kata-kata hello, hatdan have. Untuk menyimpannya dalam trie , akan terlihat seperti:

    e - l - l - o
  /
h - a - t
      \
       v - e

Dan Anda membutuhkan sembilan node. Saya telah menempatkan huruf-huruf di simpul, tetapi sebenarnya mereka memberi label pada tepinya.

Di pohon radix, Anda akan memiliki:

            *
           /
        (ello)
         /
* - h - * -(a) - * - (t) - *
                 \
                 (ve)
                   \
                    *

dan Anda hanya membutuhkan lima node. Pada gambar di atas node adalah tanda bintang.

Jadi, secara keseluruhan, pohon radix membutuhkan lebih sedikit memori , tetapi lebih sulit untuk diterapkan. Jika tidak, kasus penggunaan keduanya hampir sama.

Pertanyaan saya adalah apakah struktur data Trie dan Radix Trie adalah hal yang sama?

Singkatnya, tidak. Kategori Radix Trie menjelaskan kategori Trie tertentu , tetapi itu tidak berarti bahwa semua percobaan adalah percobaan radix.

Kalau [n't] sama, lalu apa arti Radix trie (alias Patricia Trie)?

Saya berasumsi bahwa Anda bermaksud menulis tidak dalam pertanyaan Anda, maka dari itu koreksi saya.

Demikian pula, PATRICIA menunjukkan jenis radix trie tertentu, tetapi tidak semua percobaan radix adalah percobaan PATRICIA.

Apa itu trie?

"Trie" mendeskripsikan struktur data pohon yang cocok untuk digunakan sebagai larik asosiatif, di mana cabang atau tepi berhubungan dengan bagian - bagian kunci. Definisi bagian agak kabur, di sini, karena implementasi percobaan yang berbeda menggunakan panjang bit yang berbeda untuk menyesuaikan dengan tepi. Misalnya, trie biner memiliki dua sisi per node yang sesuai dengan 0 atau 1, sedangkan trie 16 arah memiliki enam belas sisi per node yang sesuai dengan empat bit (atau digit heksadesimal: 0x0 hingga 0xf).

Diagram ini, diambil dari Wikipedia, tampaknya menggambarkan trie dengan (setidaknya) kunci 'A', 'to', 'tea', 'ted', 'ten' dan 'inn' disisipkan:

Jika trie ini menyimpan item untuk kunci 't', 'te', 'i' atau 'in' maka perlu ada informasi tambahan yang ada di setiap node untuk membedakan antara node nullary dan node dengan nilai aktual.

Apa itu radix trie?

"Radix trie" sepertinya menggambarkan bentuk trie yang memadatkan bagian awalan umum, seperti yang dijelaskan Ivaylo Strandjev dalam jawabannya. Pertimbangkan bahwa trie 256-cara yang mengindeks kunci "senyum", "tersenyum", "tersenyum" dan "tersenyum" menggunakan tugas statis berikut:

root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;

Setiap subskrip mengakses node internal. Artinya untuk mengambilnya smile_item, Anda harus mengakses tujuh node. Delapan akses node sesuai dengan smiled_itemdan smiles_item, dan sembilan untuk smiling_item. Untuk keempat item ini, ada total empat belas node. Mereka semua memiliki empat byte pertama (sesuai dengan empat node pertama) yang sama. Dengan memadatkan empat byte tersebut untuk membuat rootyang sesuai ['s']['m']['i']['l'], empat akses node telah dioptimalkan. Itu berarti lebih sedikit memori dan lebih sedikit akses node, yang merupakan indikasi yang sangat baik. Pengoptimalan dapat diterapkan secara rekursif untuk mengurangi kebutuhan untuk mengakses byte sufiks yang tidak perlu. Akhirnya, Anda sampai pada titik di mana Anda hanya membandingkan perbedaan antara kunci pencarian dan kunci yang diindeks di lokasi yang diindeks oleh trie.. Ini adalah trie radix.

root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;

Untuk mengambil item, setiap node membutuhkan posisi. Dengan kunci pencarian "tersenyum" dan root.position4, kami mengakses root["smiles"[4]], yang kebetulan root['e']. Kami menyimpan ini dalam variabel yang disebut current. current.positionadalah 5, yang merupakan lokasi perbedaan antara "smiled"dan "smiles", jadi akses berikutnya adalah root["smiles"[5]]. Ini membawa kita ke smiles_item, dan akhir dari string kita. Pencarian kami telah dihentikan, dan item telah diambil, hanya dengan tiga akses node, bukan delapan.

Apa itu PATRICIA trie?

Trie PATRICIA adalah varian dari percobaan radix yang seharusnya hanya ada nnode yang digunakan untuk memuat nitem. Di kasar menunjukkan radix trie pseudocode kita di atas, ada lima node total: root(yang merupakan simpul nullary; tidak mengandung nilai aktual), root['e'], root['e']['d'], root['e']['s']dan root['i']. Dalam percobaan PATRICIA seharusnya hanya ada empat. Mari kita lihat bagaimana prefiks ini mungkin berbeda dengan melihatnya dalam biner, karena PATRICIA adalah algoritma biner.

smile:   0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0000 0000  0000 0000
smiled:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0110 0100  0000 0000
smiles:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0111 0011  0000 0000
smiling: 0111 0011  0110 1101  0110 1001  0110 1100  0110 1001  0110 1110  0110 0111 ...

Mari kita pertimbangkan bahwa node ditambahkan sesuai urutan yang disajikan di atas. smile_itemadalah akar dari pohon ini. Perbedaannya, dicetak tebal untuk membuatnya sedikit lebih mudah dikenali, adalah pada byte terakhir "smile", pada bit 36. Sampai titik ini, semua node kita memiliki awalan yang sama . smiled_nodemilik di smile_node[0]. Perbedaan antara "smiled"dan "smiles"terjadi pada bit 43, di mana "smiles"memiliki bit '1', begitu smiled_node[1]juga smiles_node.

Daripada menggunakan NULLsebagai cabang dan / atau informasi tambahan internal yang untuk menunjukkan ketika Menghentikan pencarian, cabang-cabang link kembali sampai di suatu tempat pohon, sehingga Menghentikan pencarian ketika offset untuk menguji berkurang daripada meningkatkan. Berikut diagram sederhana dari pohon semacam itu (meskipun PATRICIA sebenarnya lebih merupakan grafik siklik, daripada pohon, seperti yang akan Anda lihat), yang disertakan dalam buku Sedgewick yang disebutkan di bawah ini:

Algoritme PATRICIA yang lebih kompleks yang melibatkan kunci dengan panjang varian dimungkinkan, meskipun beberapa properti teknis PATRICIA hilang dalam proses (yaitu setiap node berisi awalan yang sama dengan node sebelumnya):

Dengan bercabang seperti ini, ada sejumlah keuntungan: Setiap node mengandung nilai. Itu termasuk akarnya. Akibatnya, panjang dan kompleksitas kode menjadi jauh lebih pendek dan mungkin sedikit lebih cepat pada kenyataannya. Setidaknya satu cabang dan paling banyak kcabang (di mana kjumlah bit di kunci pencarian) diikuti untuk mencari item. Node berukuran kecil , karena masing-masing hanya menyimpan dua cabang, yang membuatnya cukup cocok untuk pengoptimalan lokalitas cache. Properti ini menjadikan PATRICIA algoritme favorit saya sejauh ini ...

Saya akan mempersingkat uraian ini di sini, untuk mengurangi keparahan arthritis saya yang akan datang, tetapi jika Anda ingin tahu lebih banyak tentang PATRICIA, Anda dapat membaca buku-buku seperti "The Art of Computer Programming, Volume 3" oleh Donald Knuth , atau salah satu "Algoritma dalam {bahasa-favorit Anda}, bagian 1-4" oleh Sedgewick.

TRIE:
Kita dapat memiliki skema pencarian di mana selain membandingkan seluruh kunci pencarian dengan semua kunci yang ada (seperti skema hash), kita juga dapat membandingkan setiap karakter dari kunci pencarian. Mengikuti ide ini, kita dapat membangun sebuah struktur (seperti yang ditunjukkan di bawah) yang memiliki tiga kunci yang sudah ada - “ dad ”, “ dab ”, dan “ cab ”.

         [root]
     ...// | \\...
           |  \
           c   d
           |    \
          [*]    [*]
      ...//|\.  ./|\\...        Fig-I
        a       a
       /       /
     [*]      [*]
 ...//|\..  ../|\\...
    /        /   \
   B        b     d
  /        /       \
 []       []       []

(cab)   (dab)     (dad)

Ini pada dasarnya adalah pohon M-ary dengan simpul internal, direpresentasikan sebagai [*] dan simpul daun, direpresentasikan sebagai []. Struktur ini disebut trie . Keputusan percabangan di setiap node dapat dipertahankan sama dengan jumlah simbol unik dari alfabet, katakanlah R. Untuk huruf kecil huruf Inggris az, R = 26; untuk abjad ASCII yang diperluas, R = 256 dan untuk digit / string biner R = 2.

Compact TRIE:
Biasanya, node dalam trie menggunakan array dengan size = R dan dengan demikian menyebabkan pemborosan memori ketika setiap node memiliki lebih sedikit edge. Untuk menghindari masalah ingatan, berbagai proposal dibuat. Berdasarkan variasi tersebut, trie juga dinamai sebagai “ trie kompak ” dan “ trie terkompresi ”. Meskipun nomenklatur yang konsisten jarang terjadi, versi compact trie yang paling umum dibentuk dengan mengelompokkan semua edge saat node memiliki satu sisi. Dengan menggunakan konsep ini, trie (Gbr-I) di atas dengan tombol “dad”, “dab”, dan “cab” dapat mengambil bentuk di bawah ini.

         [root]
     ...// | \\...
           |  \
          cab  da
           |    \
          [ ]   [*]                Fig-II
               ./|\\...
                 |  \
                 b   d
                 |    \
                []    []

Perhatikan bahwa masing-masing 'c', 'a', dan 'b' adalah satu-satunya edge untuk node induk yang sesuai dan oleh karena itu, mereka digabungkan menjadi satu edge “cab”. Demikian pula, 'd' dan a 'digabungkan menjadi satu sisi yang diberi label sebagai "da".

Radix Trie:
Istilah radix , dalam Matematika, berarti basis dari sistem bilangan, dan pada dasarnya menunjukkan jumlah simbol unik yang diperlukan untuk mewakili bilangan apa pun dalam sistem itu. Misalnya, sistem desimal adalah radix sepuluh, dan sistem biner adalah radix dua. Menggunakan konsep serupa, ketika kami tertarik untuk mengkarakterisasi struktur data atau algoritme dengan jumlah simbol unik dari sistem representasi yang mendasarinya, kami menandai konsep tersebut dengan istilah "radix". Misalnya, "urutan radix" untuk algoritme pengurutan tertentu. Dalam garis logika yang sama, semua varian trieyang karakteristiknya (seperti kedalaman, kebutuhan memori, runtime pencarian / hit runtime, dll.) bergantung pada radix dari alfabet yang mendasarinya, kita dapat menyebutnya radix "trie's". Misalnya, trie yang tidak dipadatkan maupun yang dipadatkan saat menggunakan alfabet az, kita dapat menyebutnya sebagai radix 26 trie . Trie apa pun yang hanya menggunakan dua simbol (biasanya '0' dan '1') dapat disebut trie radix 2 . Namun, entah bagaimana banyak literatur membatasi penggunaan istilah "Radix Trie" hanya untuk trie yang dipadatkan .

Awal PATRICIA Tree / Trie:
Menarik untuk memperhatikan bahwa string genap sebagai kunci dapat direpresentasikan menggunakan binary-alphabets. Jika kita mengasumsikan pengkodean ASCII, maka kunci “ayah” dapat ditulis dalam bentuk biner dengan menuliskan representasi biner dari setiap karakter secara berurutan, katakanlah sebagai “ 01100100 01100001 01100100 ” dengan menuliskan bentuk biner dari 'd', 'a', dan 'd' secara berurutan. Menggunakan konsep ini, trie (dengan Radix Two) dapat dibentuk. Di bawah ini kami menggambarkan konsep ini menggunakan asumsi yang disederhanakan bahwa huruf 'a', 'b', 'c', dan'd 'berasal dari alfabet yang lebih kecil, bukan ASCII.

Catatan untuk Gambar-III: Seperti yang disebutkan, untuk mempermudah penggambaran, mari kita asumsikan alfabet dengan hanya 4 huruf {a, b, c, d} dan representasi biner yang sesuai adalah "00", "01", "10" dan "11" masing-masing. Dengan ini, kunci string kita "dad", "dab", dan "cab" masing-masing menjadi "110011", "110001", dan "100001". Trie untuk ini akan seperti yang ditunjukkan di bawah ini pada Gambar-III (bit dibaca dari kiri ke kanan seperti string dibaca dari kiri ke kanan).

          [root]
             \1               
              \
              [*]
             0/ \1               
             /   \
           [*]   [*]         
           0/     /               
           /     /0
         [*]    [*]      
        0/      /               
        /      /0
      [*]    [*]
     0/     0/ \1                Fig-III
     /      /   \
    [*]   [*]   [*]
     \1     \1    \1
      \      \     \
      []     []    []
    (cab)   (dab) (dad)

PATRICIA Trie / Tree:
Jika kita memadatkan biner trie di atas (Gbr-III) menggunakan pemadatan tepi tunggal, node tersebut akan jauh lebih sedikit daripada yang ditunjukkan di atas, namun, node akan tetap lebih dari 3, jumlah kunci yang dikandungnya . Donald R. Morrison menemukan (pada tahun 1968) cara inovatif untuk menggunakan biner trie untuk menggambarkan kunci N hanya dengan menggunakan N node dan dia menamai struktur data ini PATRICIA. Struktur trie-nya pada dasarnya menyingkirkan satu sisi (percabangan satu arah); dan dalam melakukannya, dia juga menyingkirkan gagasan tentang dua jenis simpul - simpul dalam (yang tidak menggambarkan kunci apa pun) dan simpul daun (yang menggambarkan kunci). Berbeda dengan logika pemadatan yang dijelaskan di atas, trie-nya menggunakan konsep berbeda di mana setiap node menyertakan indikasi berapa banyak bit kunci yang akan dilewati untuk membuat keputusan percabangan. Namun karakteristik lain dari percobaan PATRICIA-nya adalah tidak menyimpan kunci - yang berarti struktur data seperti itu tidak akan cocok untuk menjawab pertanyaan seperti, daftar semua kunci yang cocok dengan awalan yang diberikan , tetapi bagus untuk menemukan apakah ada kunci atau tidak di trie. Meskipun demikian, istilah Patricia Tree atau Patricia Trie, sejak saat itu, telah digunakan dalam banyak pengertian yang berbeda tetapi serupa, seperti, untuk mengindikasikan sebuah compact trie [NIST], atau untuk mengindikasikan sebuah radix trie dengan radix dua [seperti yang ditunjukkan dalam subtle trie jalan di WIKI] dan sebagainya.

Trie yang mungkin bukan Radix Trie:
Ternary Search Trie (alias Pohon Pencarian Ternary) sering disingkat TST adalah struktur data (dikemukakan oleh J. Bentley dan R. Sedgewick ) yang terlihat sangat mirip dengan trie dengan percabangan tiga arah. Untuk pohon seperti itu, setiap node memiliki alfabet karakteristik 'x' sehingga keputusan percabangan ditentukan oleh apakah karakter kunci kurang dari, sama dengan atau lebih besar dari 'x'. Karena fitur percabangan 3 arah tetap ini, ini menyediakan alternatif hemat memori untuk trie, terutama ketika R (radix) sangat besar seperti untuk alfabet Unicode. Menariknya, TST, tidak seperti (R-way) trie , tidak memiliki karakteristik yang dipengaruhi oleh R. Sebagai contoh, search miss untuk TST adalah ln (N)sebagai lawan log _R (N) untuk R-way Trie. Persyaratan memori dari TST, tidak seperti R-cara trie adalah TIDAK fungsi dari R juga. Jadi kita harus berhati-hati untuk menyebut TST sebagai radix-trie. Secara pribadi, saya tidak berpikir kita harus menyebutnya radix-trie karena tidak ada (sejauh yang saya tahu) dari karakteristiknya yang dipengaruhi oleh radix, R, dari alfabet yang mendasarinya.