PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
Ein PATRICIA-Baum ist mit einem Trie verwandt.Wenn die Menge der Schlüssel spärlich ist, d. h. wenn die tatsächlichen Schlüssel eine kleine Teilmenge der Menge der potentiellen Schlüssel bilden, wie es sehr oft der Fall ist, haben viele (die meisten) der internen Knoten im Trie nur einen Nachkommen, was dazu führt, dass der Trie eine hohe Raumkomplexität hat.
Ein Trie verwendet jeden Teil (Bit, Zeichen, …) des Schlüssels, um zu bestimmen, welcher Teilbaum ausgewählt werden soll.Ein PATRICIA-Baum benennt stattdessen (durch Speicherung seiner Position im Knoten)welches Element des Schlüssels als nächstes verwendet wird, um die Verzweigung zu bestimmen.Dadurch entfällt die Notwendigkeit von Knoten mit nur einem Nachkommen:
Der Index von PATRICIA unterscheidet sich von der binären Trie-Struktur von Fredkin dadurch, dass der Index nur echte Verzweigungen aufzeichnet; wenn ein Satz nur eine richtige rechte Erweiterung hat, wird er nicht im Index aufgeführt.Diese Tatsache reduziert die Anzahl der Indexzeilen auf das Doppelte der Anzahl der Anfänge und macht ihn unabhängig von der Länge der gespeicherten Phrasen.
– Morrison 1968 pp520.
Am einfachsten ist es, einen PATRICIA-Baum für Schlüssel (Zeichenketten) über ein Alphabet der Größe zwei zu erstellen: {a,b}, oder {0,1}.Zeichenketten über ein Alphabet mit mehr als zwei Elementen, z.B. ascii, können als Zeichenketten über ein Alphabet von zwei Elementen behandelt werden, indem die Bits innerhalb jedes Zeichens des größeren Alphabets genommen werden.
Das folgende Beispiel zeigt das Wachstum eines PATRICIA-Baums unter einer Folge von Einfügungen:
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; Suche endet bei ababb~=ababa;1. Differenz ist an Position 5, also…
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; hat keine Position #5;kann Schlüsselpositionen überspringen, muss aber in der Reihenfolge testen, also…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; Suche endet bei ababb~=aaabba;kann Schlüsselpositionen überspringen, muss aber der Reihe nach getestet werden, also…
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; ab ist auch ein Präfix von ababa und ababb;muss die Möglichkeit haben, an einem Zwischenknoten zu enden, wie bei Tries.
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
Der Umgang mit einem Schlüssel wie „ab“, der das Präfix eines anderen Schlüssels ist, z.B. „ababa“, kann auf verschiedene Weise gehandhabt werden. Ein tatsächliches oder fiktives Abschlusszeichen, das oft als „$“ (oder „0“ in C und seinen Verwandten) bezeichnet wird, kann als drittes Zeichen im Alphabet betrachtet werden, das aber nur am Ende von Schlüsseln vorkommen darf.
Notizen
- D. R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968.
Ursprünglich wurde PATRICIA als Index zur Suche in markiertem Text vorgestellt. - G. H. Gonnet. Handbook of Algorithms and Data Structures.Addison-Wesley, International Computer Series, S. 109, 1984.
Enthält eine schöne, einfache Kodierung derPATRICIA-Algorithmen und vieler anderer.Dieses Buch ist eine großartige Quelle. - R. Sedgewick.Algorithms in C. Addison-Wesley, edn 1, pp253, 1990.
Speichert Elemente (oder Zeiger auf Elemente) in internen ‚fork‘ Knoten. - Siehe für Stringsuche usw..