Jaka jest różnica między strukturami danych trie i radix trie?

Czy struktury danych trie i radix trie to to samo?

Jeśli nie są takie same, jakie jest znaczenie radix trie (AKA Patricia trie)?

Drzewo radix to skompresowana wersja trie. W trie, na każdej krawędzi piszesz pojedynczą literę, podczas gdy w drzewie PATRICIA (lub drzewie radix) przechowujesz całe słowa.

Teraz załóżmy, że masz słowa hello, hati have. Aby przechowywać je w trie , wyglądałoby to tak:

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

Potrzebujesz dziewięciu węzłów. Umieściłem litery w węzłach, ale w rzeczywistości oznaczają one krawędzie.

W drzewie radix będziesz mieć:

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

i potrzebujesz tylko pięciu węzłów. Na powyższym obrazku węzły to gwiazdki.

Ogólnie rzecz biorąc, drzewo radix zajmuje mniej pamięci , ale jest trudniejsze do zaimplementowania. W przeciwnym razie przypadek użycia obu jest prawie taki sam.

Moje pytanie brzmi, czy struktura danych Trie i Radix Trie to to samo?

Krótko mówiąc, nie. Kategoria Radix Trie opisuje konkretną kategorię Trie , ale to nie znaczy, że wszystkie próby są próbami radix.

Jeśli są [nie] takie same, to jakie jest znaczenie Radix trie (aka Patricia Trie)?

Zakładam, że nie miałeś zamiaru pisać , więc moje pytanie.

Podobnie PATRICIA oznacza określony typ trie radix, ale nie wszystkie próby radix są próbami PATRICIA.

Co to jest trie?

„Trie” opisuje drzewiastą strukturę danych odpowiednią do wykorzystania jako tablica asocjacyjna, w której gałęzie lub krawędzie odpowiadają częściom klucza. Definicja części jest tutaj raczej niejasna, ponieważ różne implementacje prób używają różnych długości bitów, aby odpowiadać krawędziom. Na przykład trie binarne ma dwie krawędzie na węzeł, które odpowiadają 0 lub 1, podczas gdy trie 16-ścieżkowe ma szesnaście krawędzi na węzeł, które odpowiadają czterem bitom (lub cyfrze szesnastkowej: od 0x0 do 0xf).

Ten diagram, pobrany z Wikipedii, wydaje się przedstawiać próbę z wstawionymi (przynajmniej) kluczami „A”, „do”, „herbata”, „ted”, „dziesięć” i „karczma”:

Jeśli ta próba miałaby przechowywać elementy dla kluczy „t”, „te”, „i” lub „in”, w każdym węźle potrzebna byłaby dodatkowa informacja, aby rozróżnić węzły puste i węzły z rzeczywistymi wartościami.

Co to jest radix trie?

„Radix trie” wydaje się opisywać formę trie, która zagęszcza wspólne części przedrostków, jak opisał Ivaylo Strandjev w swojej odpowiedzi. Weź pod uwagę, że 256-kierunkowa próba indeksująca klucze „uśmiech”, „uśmiech”, „uśmiech” i „uśmiech” przy użyciu następujących przypisań statycznych:

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;

Każdy indeks dolny uzyskuje dostęp do wewnętrznego węzła. Oznacza to, że aby pobrać smile_item, musisz uzyskać dostęp do siedmiu węzłów. Osiem dostępów do węzłów odpowiada smiled_itemi smiles_item, a dziewięć do smiling_item. W przypadku tych czterech elementów jest łącznie czternaście węzłów. Wszystkie mają jednak pierwsze cztery bajty (odpowiadające pierwszym czterem węzłom). Poprzez skondensowanie tych czterech bajtów w celu utworzenia rootodpowiadającego im ['s']['m']['i']['l'], cztery dostępy do węzłów zostały zoptymalizowane. Oznacza to mniej pamięci i mniej dostępu do węzłów, co jest bardzo dobrym wskazaniem. Optymalizację można zastosować rekurencyjnie, aby zmniejszyć potrzebę dostępu do niepotrzebnych bajtów przyrostka. W końcu dojdziesz do punktu, w którym porównujesz tylko różnice między kluczem wyszukiwania a kluczami indeksowanymi w lokalizacjach indeksowanych przez tę próbę. To jest próba radix.

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

Aby pobrać elementy, każdy węzeł potrzebuje pozycji. Korzystając z klucza wyszukiwania „uśmiechy” i cyfry root.position4, uzyskujemy dostęp. Tak się root["smiles"[4]]składa root['e']. Przechowujemy to w zmiennej o nazwie current. current.positionto 5, czyli lokalizacja różnicy między "smiled"a "smiles", więc następny dostęp będzie root["smiles"[5]]. To prowadzi nas do smiles_itemkońca naszego łańcucha. Nasze wyszukiwanie zostało zakończone, a element został pobrany z zaledwie trzema dostępami do węzłów zamiast ośmiu.

Co to jest trie PATRICIA?

Trie PATRICIA jest wariantem prób radix, dla których powinny istnieć tylko nwęzły używane do przechowywania nelementów. W naszym grubsza wykazano radix trie Pseudokod powyżej, istnieje pięć węzłów w sumie: root(co jest sygnalnych węzła, zawiera żadnej konkretnej wartości), root['e'], root['e']['d'], root['e']['s']i root['i']. W próbie PATRICIA powinny być tylko cztery. Przyjrzyjmy się, jak te przedrostki mogą się różnić, patrząc na nie w systemie binarnym, ponieważ PATRICIA jest algorytmem binarnym.

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 ...

Rozważmy, że węzły są dodawane w kolejności przedstawionej powyżej. smile_itemjest korzeniem tego drzewa. Różnica, pogrubiona, aby nieco łatwiej ją zauważyć, znajduje się w ostatnim bajcie "smile"bitu 36. Do tego momentu wszystkie nasze węzły mają ten sam prefiks. smiled_nodenależy do smile_node[0]. Różnica między "smiled"i "smiles"występuje na bicie 43, gdzie "smiles"ma bit „1”, więc smiled_node[1]jest smiles_node.

Zamiast używać NULLjako gałęzi i / lub dodatkowych informacji wewnętrznych do oznaczania zakończenia wyszukiwania, gałęzie łączą się gdzieś w górę drzewa, więc wyszukiwanie kończy się, gdy przesunięcie testowe maleje, a nie rośnie. Oto prosty diagram takiego drzewa (chociaż PATRICIA jest bardziej wykresem cyklicznym niż drzewem, jak zobaczysz), który został zawarty w książce Sedgewicka wspomnianej poniżej:

Bardziej złożony algorytm PATRICIA z kluczami o różnej długości jest możliwy, chociaż niektóre właściwości techniczne PATRICIA są tracone w procesie (mianowicie, że każdy węzeł zawiera wspólny przedrostek z węzłem poprzedzającym):

Takie rozgałęzianie przynosi szereg korzyści: każdy węzeł zawiera wartość. Obejmuje to root. W rezultacie długość i złożoność kodu stają się znacznie krótsze i prawdopodobnie nieco szybsze w rzeczywistości. Co najmniej jedna gałąź i co najwyżej kgałęzie (gdzie kjest liczba bitów w kluczu wyszukiwania) są śledzone w celu zlokalizowania elementu. Węzły są małe , ponieważ przechowują tylko dwie gałęzie, co czyni je dość odpowiednimi do optymalizacji lokalizacji pamięci podręcznej. Te właściwości sprawiają, że PATRICIA jest moim ulubionym algorytmem do tej pory ...

Zamierzam skrócić ten opis tutaj, aby zmniejszyć nasilenie mojego zbliżającego się zapalenia stawów, ale jeśli chcesz dowiedzieć się więcej o PATRICIA, możesz zapoznać się z książkami, takimi jak „The Art of Computer Programming, Volume 3” autorstwa Donalda Knutha lub którykolwiek z „Algorytmów w {twój-ulubiony-język}, części 1-4” Sedgewicka.

TRIE:
Możemy mieć schemat wyszukiwania, w którym zamiast porównywać cały klucz wyszukiwania ze wszystkimi istniejącymi kluczami (takimi jak schemat skrótu), moglibyśmy również porównać każdy znak klucza wyszukiwania. Zgodnie z tym pomysłem możemy zbudować strukturę (jak pokazano poniżej), która ma trzy istniejące klucze - „ tata ”, „ dab ” i „ cab ”.

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

(cab)   (dab)     (dad)

Zasadniczo jest to drzewo M-ary z węzłem wewnętrznym, przedstawionym jako [*] i węzłem liścia, przedstawionym jako []. Ta struktura nazywa się trie . Decyzja rozgałęziająca w każdym węźle może być równa liczbie unikalnych symboli alfabetu, powiedzmy R. Dla alfabetów angielskich małych liter az, R = 26; dla rozszerzonych alfabetów ASCII R = 256, a dla cyfr / ciągów binarnych R = 2.

Zwarta TRIE:
Zazwyczaj węzeł w trie używa tablicy o rozmiarze = R, a zatem powoduje marnowanie pamięci, gdy każdy węzeł ma mniej krawędzi. Aby obejść problem pamięci, wysunięto różne propozycje. Na podstawie tych odmian trie są również nazywane „ trie kompaktowe ” i „ trie skompresowane ”. Chociaż spójna nomenklatura jest rzadkością, najczęstszą wersją zwartej trie jest grupowanie wszystkich krawędzi, gdy węzły mają jedną krawędź. Korzystając z tej koncepcji, powyższe (Rys.-I) próby z klawiszami „tato”, „dab” i „cab” mogą przybrać poniższą postać.

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

Należy zauważyć, że każdy z „c”, „a” i „b” jest jedyną krawędzią odpowiadającego jej węzła nadrzędnego i dlatego są one skupione w pojedynczej krawędzi „cab”. Podobnie „d” i a ”są połączone w jedną krawędź oznaczoną jako„ da ”.

Radix Trie:
Termin radix w matematyce oznacza podstawę systemu liczbowego i zasadniczo wskazuje liczbę unikalnych symboli potrzebnych do reprezentowania dowolnej liczby w tym systemie. Na przykład system dziesiętny to podstawa dziesięć, a system binarny to podstawa dwa. Korzystając z podobnej koncepcji, kiedy interesuje nas scharakteryzowanie struktury danych lub algorytmu za pomocą liczby unikalnych symboli podstawowego systemu reprezentacji, oznaczamy to pojęcie terminem „podstawa”. Na przykład „sortowanie radix” dla określonego algorytmu sortowania. Zgodnie z tą samą logiką, wszystkie warianty trie którego cechy (takie jak głębokość, zapotrzebowanie na pamięć, czas wykonania chybienia / trafienia itp.) Zależą od podstawy alfabetu, możemy je nazwać radix „trie”. Na przykład nieskompaktowane, jak również zagęszczone trie, gdy używa alfabetów az, możemy nazwać to radix 26 trie . Każdy trie który wykorzystuje tylko dwa symbole (tradycyjnie „0” i „1”) może być nazywany podstawa 2 trie . Jednak w jakiś sposób wiele literatur ograniczyło użycie terminu „Radix Trie” tylko do zwartych skompresowanej wersji .

Preludium do PATRICIA Tree / Trie:
Byłoby interesujące zauważyć, że nawet łańcuchy jako klucze mogą być reprezentowane za pomocą alfabetów binarnych. Jeśli przyjmiemy kodowanie ASCII, klucz „tato” można zapisać w formie binarnej, zapisując binarną reprezentację każdego znaku w sekwencji, powiedzmy jako „ 01100100 01100001 01100100 ”, zapisując binarne formy „d”, „a” i „d” sekwencyjnie. Korzystając z tej koncepcji, można utworzyć trie (z Radix Two). Poniżej przedstawiamy tę koncepcję, stosując uproszczone założenie, że litery „a”, „b”, „c” i „d” pochodzą z mniejszego alfabetu zamiast z ASCII.

Uwaga do rysunku III: Jak wspomniano, aby ułatwić przedstawienie, załóżmy, że alfabet ma tylko 4 litery {a, b, c, d} i odpowiadające im reprezentacje binarne to „00”, „01”, „10” i „11” odpowiednio. Dzięki temu nasze klawisze ciągów „tata”, „dab” i „cab” zmieniają się odpowiednio na „110011”, „110001” i „100001”. Próba będzie taka, jak pokazano poniżej na fig. III (bity są odczytywane od lewej do prawej, tak jak ciągi są odczytywane od lewej do prawej).

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

PATRICIA Trie / Tree:
Jeśli skompaktujemy powyższą binarną trie (Fig-III) przy użyciu zagęszczania z jedną krawędzią, będzie miała znacznie mniej węzłów niż pokazano powyżej, a mimo to węzłów będzie nadal więcej niż 3, liczba kluczy, które zawiera . Donald R. Morrison znalazł (w 1968 r.) Innowacyjny sposób wykorzystania binarnego trie do zobrazowania N kluczy przy użyciu tylko N węzłów i nazwał tę strukturę danych PATRICIA. Jego struktura trie zasadniczo pozbyła się pojedynczych krawędzi (rozgałęzienie jednokierunkowe); Robiąc to, pozbył się również pojęcia dwóch rodzajów węzłów - węzłów wewnętrznych (które nie przedstawiają żadnego klucza) i węzłów-liści (które przedstawiają klucze). W przeciwieństwie do opisanej powyżej logiki zagęszczania, jego trie wykorzystuje inną koncepcję, w której każdy węzeł zawiera wskazanie, ile bitów klucza należy pominąć w celu podjęcia decyzji o rozgałęzieniu. Kolejną cechą jego trie PATRICIA jest to, że nie przechowuje kluczy - co oznacza, że ​​taka struktura danych nie będzie odpowiednia do odpowiadania na pytania, takie jak lista wszystkich kluczy pasujących do danego prefiksu , ale jest dobra do znalezienia, czy klucz istnieje lub nie w drodze. Niemniej jednak, termin Patricia Tree lub Patricia Trie był od tego czasu używany w wielu różnych, ale podobnych znaczeniach, takich jak wskazanie zwartej trie [NIST] lub wskazanie radix trie z radixem dwa [jak wskazano w subtelnym sposób w WIKI] i tak dalej.

Próba, która może nie być Radix Trie:
Ternary Search Trie (aka Ternary Search Tree) często w skrócie TST to struktura danych (zaproponowana przez J. Bentleya i R. Sedgewicka ), która wygląda bardzo podobnie do trie z trójdrożnymi rozgałęzieniami. W przypadku takiego drzewa każdy węzeł ma charakterystyczny alfabet „x”, tak więc decyzja o rozgałęzieniu jest uzależniona od tego, czy znak klucza jest mniejszy, równy lub większy niż „x”. Ze względu na tę ustaloną funkcję trójdrożnego rozgałęziania zapewnia wydajną pamięć alternatywę dla trie, zwłaszcza gdy R (radix) jest bardzo duży, na przykład dla alfabetów Unicode. Co ciekawe, TST, w przeciwieństwie do (R-way) trie , nie ma swoich właściwości pod wpływem R. Na przykład brak wyszukiwania dla TST to ln (N)w przeciwieństwie do log _R (N) dla R-way Trie. Wymagania pamięciowe TST, w przeciwieństwie do R-way trie jest NIE funkcją R, jak również. Dlatego powinniśmy uważać, aby nazwać TST radix-trie. Osobiście uważam, że nie powinniśmy nazywać tego radix-trie, ponieważ na żadną (o ile wiem) jego właściwości nie ma wpływu podstawa, R, leżących u jej podstaw alfabetów.