Patricia-Trie
aus Wikipedia, der freien Enzyklopädie
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.
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.
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. Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Integern als Schlüsseln zu konstruieren.
Siehe auch: Suffixbaum
[Bearbeiten] 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]
