Jaka jest różnica między drzewami radix a próbami Patricii?

Uczę się o drzewach Radix (inaczej skompresowanych próbach) i Patricii, ale znajduję sprzeczne informacje na temat tego, czy faktycznie są one takie same. Drzewo radix można uzyskać z normalnej (nieskompresowanej) trie, łącząc węzły z ich rodzicami, gdy węzły są jedynym dzieckiem. Dotyczy to również prób Patricii. W jaki sposób dwie struktury danych są różne?

Na przykład NIST wymienia dwa jako takie same:

Drzewo Patricia

(struktura danych)

Definicja: Zwarta reprezentacja trie, w której dowolny węzeł będący jedynym dzieckiem jest łączony z jego rodzicem.

Znany również jako drzewo radix.

Wiele źródeł w sieci twierdzi, że tak samo. Jednak najwyraźniej próby Patricii są szczególnym przypadkiem drzew radix. Wpis w Wikipedii mówi:

Próby PATRICIA są próbami z radix z radix równym 2, co oznacza, że ​​każdy bit klucza jest porównywany indywidualnie, a każdy węzeł jest dwukierunkową (tj. Lewą i prawą) gałęzią.

Naprawdę tego nie rozumiem. Czy różnica polega tylko na sposobie dokonywania porównań podczas wyszukiwania? Jak każdy węzeł może być „gałęzią dwukierunkową”? Czy nie powinno być co najwyżej ALPHABET_SIZEmożliwych gałęzi dla danego węzła?

Czy ktoś może to wyjaśnić? Czy ze względów praktycznych próby Radix są zwykle wdrażane tak, jak próbuje Patricia (i dlatego często są uważane za takie same)? Czy nie można dokonać takich uogólnień?

Uważam ten post za bardzo pomocny.

Aby zobaczyć różnicę między próbami Patricii a drzewami radix, ważne jest, aby zrozumieć:

• Pojęcie radix , ponieważ próby Patricii są drzewami radix o radix równym 2.
• $r$$2^r$

Załóżmy, że mamy wstawić klawisze uśmiech , uśmiechnął się i uśmiechy (w tej kolejności) w trie Patricia. Binarna reprezentacja tych kluczy jest następująca:

Zauważ, że uśmiech jest prefiksem uśmiechu , a analizując reprezentację binarną, widzimy, że pierwszy bit, który różni się (od lewej do prawej), to 0 (podświetlony na czerwono w drugim rzędzie); Z tego powodu, uśmiechnął będzie lewa dziecko z uśmiechem . Podobnie uśmiechy będzie prawo dziecko z uśmiechnął ponieważ mają taki sam prefiks do kawałka, którego wartość 1 (zaznaczone na czerwono w trzecim rzędzie). Wynikowa trie Patricia po włożeniu trzech kluczy jest następująca:

Gdyby podstawa wynosiła na przykład 4, wówczas węzły wewnętrzne mogłyby mieć co najwyżej czworo dzieci (z krawędziami oznaczonymi odpowiednio 00, 01, 10 i 11). W takim przypadku klucze byłyby porównywane po 2 bitach, a nie 1 (jak w próbach Patricii).

W jaki sposób dwie struktury danych są różne?

Według mnie jedyną różnicą jest podstawa, która jest równa 2 w przypadku prób Patricii. Ta wartość może być dowolną potęgą 2 w zwykłych drzewach radix.

Czy różnica polega tylko na sposobie dokonywania porównań podczas wyszukiwania?

$\log_2{R}$$R$

Jak każdy węzeł może być „gałęzią dwukierunkową”? Czy nie powinno być co najwyżej ALPHABET_SIZEmożliwych gałęzi dla danego węzła?

Podstawa określa maksymalną liczbę dzieci, które mogą mieć węzły drzewa podstawnika. Na przykład, gdy podstawa = 2, każdy węzeł może mieć maksymalnie dwoje dzieci. Tak jest w przypadku prób Patricii (znanych również jako binarne drzewa radix).

Czy próby Radix są zwykle wdrażane tak, jak próbuje Patricia (i dlatego często są uważane za takie same)? Czy nie można dokonać takich uogólnień?

Szczerze mówiąc, nie mam odpowiedzi na to pytanie. Wygląda na to, że obie struktury danych zostały zaproponowane mniej więcej w tym samym czasie przez różnych autorów. Z przyczyn historycznych, których nie jestem świadomy, oba warunki obowiązują do dziś.

Patricia trie to binarna próbka wynikająca z zastosowania algorytmu PATRICIA do danych alfanumerycznych.

PATRICIA oznacza Praktyczny algorytm odzyskiwania informacji zakodowanych w alfanumeryce [ oryginalny artykuł Donalda R. Morrisona ]. Artykuł definiuje podstawowe słownictwo składające się z START, STOP, END, L-PHRASE, BRANCH, TWIN i CHAIN. Próby PATRICIA są próbami wynikającymi z zastosowania tego algorytmu - próby binarne, gdzie podstawa r wynosi 2 [ wikipedia ] (i wyżej); binarny wybór w każdym węźle podczas przechodzenia przez trie).

W praktyce jednak wydaje się, że termin Patricia jest używany z r> = 2 (tzn. Próbami podstawowymi), gdzie stosuje się podobny alogorytm przechowywania i wyszukiwania. Na przykład ten jest zatytułowany jako Patricia. Ethereum Patricia Merkle Trie inny przykład, w którym r oznacza 16 w niektórych węzłach.