Patricia Trie

In der Informatik ist ein Patricia-Trie (abgeleitet aus dem engl. reTrieval) eine Datenstruktur, genauer eine spezielle Art eines Tries zur gleichzeitigen Speicherung von mehreren Zeichenketten. Seinen Namen verdankt er dem Akronym PATRICIA, das für Practical Algorithm to Retrieve Information Coded in Alphanumeric steht. Er wurde 1968 von Donald R. Morrison veröffentlicht.

Der Patricia-Trie zeichnet sich im Gegensatz zum normalen Trie dadurch aus, dass die Daten komprimiert abgespeichert werden. Dazu werden Zeichen, bei denen keine Verzweigung im Baum entsteht, einfach übersprungen und die Anzahl der ausgelassenen Knoten vor dem nächsten auftretenden Zeichen gespeichert. Somit wird gewährleistet, dass ein Suchbegriff eindeutig zugeordnet werden kann.

Die Größe von Patricia-Tries hängt somit nicht von der Länge der gespeicherten Schlüsselwerte ab und jeder neue Eintrag kann durch Erstellen von nur einem neuen Knoten und einer neuen Kante eingefügt werden. Somit wachsen sie langsam, auch wenn eine große Anzahl neuer Elemente eingefügt wird.

Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Integern als Schlüsseln zu konstruieren.

Siehe auch: Suffixbaum

Weblinks

• Monash University: Algorithms and Data Structures Research & Reference Material: PATRICIA, von Lloyd Allison [en]
• Practical Algorithm to Retrieve Information Coded in Alphanumeric, Originalpapier im ACM Portal [en]
• NIST's Dictionary of Algorithms and Data Structures: Patricia Tree [en]
• Eine ausführlich kommentierte Dictionary Implementierung mit einem binären Patricia Tree (Radix Tree), von Herbert Glarner (in Linoleum, einem Cross-Platform Assembler) [en]