PATRICIA |
|
PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, D.R.Morrison (1968). A PATRICIA tree is related to a Trie. The problem with Tries is that when the set of keys is sparse, i.e. when the actual keys form a small subset of the set of potential keys, as is very often the case, many (most) of the internal nodes in the Trie have only one descendant. This causes the Trie to have a high space-complexity. A Trie uses every part (bit, character, ...) of the key, in turn, to determine which subtree to select. A PATRICIA tree instead nominates (by storing its position in the node) which element of the key will next be used to determine the branching. This removes the need for any nodes with just one descendant: PATRICIA's index differs from Fredkin's Binary Trie structure in that the index records only true [i.e. genuine] branches; where a phrase has only one proper right extension, it is not recorded in the index. This fact reduces the number of index rows to only twice the number of starts, amd makes it independent of the length of the stored phrases. It is easiest to create a PATRICIA tree for keys (strings) over an alphabet of size two: {a,b}, or {0,1}. However, strings over an alphabet of more than two elements, e.g. ascii, can be treated as strings over an alphabet of two by taking the bits within each character of the larger alphabet. The following example shows the growth of a PATRICIA tree under a sequence of insertions:
12345 -- number character positions insert ababb -- the key
Dealing with a key, such as `ab', which is the prefix of another key, e.g. `ababa', can be handled in various ways. An actual, or notional, terminating character, often denoted `$' (or `\0' in C and its relatives) can be considered to be a third character in the alphabet, but only allowed to occur at the ends of keys. This slight complication does not arise in the special case that all keys have the same length. Notes
|
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Sunday, 03-Dec-2023 08:39:40 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |