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.
radix-treeraczej niżradix-trie? Co więcej, jest nim sporo otagowanych pytań.