PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Drzewo PATRICIA jest spokrewnione z Trie.Problem z Trie polega na tym,że gdy zbiór kluczy jest nieliczny,tzn.tzn. gdy rzeczywiste klucze tworzą mały podzbiór zbioru potencjalnych kluczy, jak to się bardzo często zdarza, wiele (większość) wewnętrznych węzłów w Trie ma tylko jednego potomka.Powoduje to, że Trie ma dużą złożoność przestrzenną.
Trie używa każdej części (bitu, znaku, …) klucza po kolei, aby określić, które poddrzewo wybrać.Drzewo PATRICIA zamiast tego nominuje (przez przechowywanie jego pozycji w węźle), który element klucza zostanie następnie użyty do określenia rozgałęzienia.Usuwa to potrzebę istnienia węzłów z tylko jednym potomkiem:
Indeks PATRICIA różni się od struktury Binary Trie Fredkina tym, że indeks rejestruje tylko prawdziwe gałęzie; gdy fraza ma tylko jedno właściwe rozszerzenie w prawo, nie jest ono rejestrowane w indeksie.Fakt ten redukuje liczbę wierszy indeksu do zaledwie dwukrotności liczby początków i uniezależnia go od długości przechowywanych wyrażeń.
– Morrison 1968 pp520.
Najłatwiej jest utworzyć drzewo PATRICIA dla kluczy (ciągów) nad alfabetem o rozmiarze dwóch: {a,b}, lub {0,1}.Jednak ciągi nad alfabetem o więcej niż dwóch elementach, np. ascii, mogą być traktowane jako ciągi nad alfabetem dwójkowym, biorąc bity wewnątrz każdego znaku większego alfabetu.
Następujący przykład pokazuje wzrost drzewa PATRICIA pod ciągiem wstawek:
C
o
m
p
u
t
e
r
–
S
c
i
e
n
c
e
empty -- initial state
12345 -- number character positionsinsert ababb -- the key
----> ababb
insert ababa; wyszukiwanie kończy się na ababb~=ababa; pierwsza różnica jest na pozycji 5, więc…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; nie ma pozycji #5; może pominąć kluczowe pozycje, ale musi testować w kolejności, więc…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; wyszukiwanie kończy się na ababb~=aaabba;może pominąć kluczowe pozycje, ale musi testować w kolejności, więc…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab jest również przedrostkiem ababa i ababb; musi mieć możliwość zakończenia w węźle pośrednim, tak jak w Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Zajmowanie się kluczem, takim jak `ab’, który jest prefiksem innego klucza, np. `ababa’, może być traktowane na różne sposoby. Rzeczywisty, lub fikcyjny, znak kończący, często oznaczany `$’ (lub `0′ w C i jego krewnych) może być uważany za trzeci znak w alfabecie, ale tylko dopuszczony do występowania na końcach kluczy.Ta niewielka komplikacja nie powstaje w specjalnym przypadku, gdy wszystkie klucze mają tę samą długość.
Notatki
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Oryginalnie przedstawił PATRICIA jako indeks do wyszukiwania w oznaczonym tekście. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, pp 109, 1984.
Zawiera ładne proste kodowanie algorytmówPATRICIA, a także wielu innych.Ta książka jest świetnym źródłem. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Zatrzymuje elementy (lub wskaźniki do elementów) wewnątrz wewnętrznych węzłów `fork’. - Zobacz do wyszukiwania ciągów znaków itp.
.