Patricia Trie
In computer science , a is Patricia trie (derived from the engl. Re trie val) a data structure , more specifically a special type of entries for the simultaneous storage of multiple character strings . It owes its name to the acronym PATRICIA , which stands for Practical Algorithm to Retrieve Information Coded in Alphanumeric . It was published in 1968 by Donald R. Morrison .
In contrast to the normal trie, the Patricia-Trie is characterized by the fact that the data is stored in compressed form. For this purpose, characters that do not branch in the tree are simply skipped and the number of nodes that are omitted before the next character that occurs is saved. This ensures that a search term can be clearly assigned.
The size of Patricia tries does not depend on the length of the stored key values and each new entry can be inserted by just creating a new node and a new edge. Thus, they grow slowly even when a large number of new elements are inserted.
Patricia tries can be used to construct associative arrays with strings as keys. This saves storage space for the keys.
See also
Web links
- Monash University: Algorithms and Data Structures Research & Reference Material: PATRICIA , by Lloyd Allison [en]
- Practical Algorithm to Retrieve Information Coded in Alphanumeric , original paper in the ACM Portal [en]
- NIST's Dictionary of Algorithms and Data Structures: Patricia Tree [en]
- Use of a binary reference chain method when building lists. Electronic computing systems 10 (1968), by Gernot Gwehenberger describes an identical search method and data structure that was developed independently around the same time [de]