15.3 Patricia Tries
Trie-based search as described in Section 15.2 has two inconvenient flaws. First, the one-way branching leads to the creation of extra nodes in the trie, which seem unnecessary. Second, there are two different types of nodes in the trie, which leads to complications (see Exercise 15.22). In 1968, Morrison discovered a way to avoid both of these problems, in a method that he named patricia ("practical algorithm to retrieve information coded in alphanumeric"). Morrison developed his algorithm in the context of string-indexing applications of the type that we shall consider in Section 15.5, but it is equally effective as a symbol-table implementation. Like DSTs, patricia tries allow search for N keys in a tree with just N nodes; like tries, they require only about lg N bit comparisons and one full key comparison per search, and they support other ADT operations. Moreover, these performance characteristics are independent of key length, and the data structure is suitable for variable-length keys.
Program 15.5 Patricia trie symbol-table implementation
Nodes in patricia tries contain a field that indicates which bit position distinguishes keys on the right from keys on the left. We use a dummy node head at the top of the trie that is always the result of a search for the null (all 0s) key. The root of the trie is at head.l (the link head.r is unused).
class ST { private class Node { ITEM item; Node l, r; int bit; Node(ITEM x, int i) { item = x; bit = i; } } private Node head; ST(int maxN) { head = new Node(null, -1); head.l = head; } ITEM search(KEY key) // See Program 15.6 void insert(ITEM x) // See Program 15.7 public String toString() // See Program 15.8 } Starting with the standard trie data structure, we avoid one-way branching via a simple device: we put into each node the index of the bit to be tested to decide which path to take out of that node. Thus, we jump directly to the bit where a significant decision is to be made, bypassing the bit comparisons at nodes where all the keys in the subtree have the same bit value. Moreover, we avoid external nodes via another simple device: we store data in internal nodes and replace links to external nodes with links that point back upwards to the correct internal node in the trie. These two changes allow us to represent tries with binary trees comprising nodes with a key and two links (and an additional field for the index), which we call patricia tries. With patricia tries, we store keys in nodes as with DSTs, and we traverse the tree according to the bits of the search key; but we do not use the keys in the nodes on the way down the tree to control the search; we merely store them there for possible later reference, when the bottom of the tree is reached.
Program 15.6 Patricia-trie search
The recursive method searchR returns the unique node that could contain the record with key v. It travels down the trie, using the bits of the tree to control the search, but tests only 1 bit per node encountered the one indicated in the bit field. It terminates the search when it encounters an external link, one which points up the tree. The search method search calls searchR, then tests the key in that node to determine whether the search is a hit or a miss.
private ITEM searchR(Node h, KEY v, int i) { if (h.bit <= i) return h.item; if (bit(v, h.bit) == 0) return searchR(h.l, v, h.bit); else return searchR(h.r, v, h.bit); } ITEM search(KEY key) { ITEM t = searchR(head.l, key, -1); if (t == null) return null; if (equals(t.key(), key)) return t; return null; } As hinted in the previous paragraph, it is easier to follow the mechanics of the algorithm if we first take note that we can regard standard tries and patricia tries as different representations of the same abstract trie structure. For example, the tries in Figure 15.10 and at the top in Figure 15.11, which illustrate search and insertion for patricia tries, represent the same abstract structure as do the tries in Figure 15.6. The search and insertion algorithms for patricia tries use, build, and maintain a concrete representation of the abstract trie data structure different from the search and insertion algorithms discussed in Section 15.2, but the underlying trie abstraction is the same.
Figure 15.10. Patricia search
In a successful search for R = 10010 in this sample patricia trie (top), we move right (since bit 0 is 1), then left (since bit 4 is 0), which brings us to R (the only key in the tree that begins with 1***0). On the way down the tree, we check only the key bits indicated in the numbers over the nodes (and ignore the keys in the nodes). When we first reach a link that points up the tree, we compare the search key against the key in the node pointed to by the up link, since that is the only key in the tree that could be equal to the search key.
In an unsuccessful search for I = 01001, we move left at the root (since bit 0 of the key is 0), then take the right (up) link (since bit 1 is 1) and find that H (the only key in the trie that begins with 01) is not equal to I.
Figure 15.11. Patricia-trie insertion
To insert I into the sample patricia trie in Figure 15.10, we add a new node to check bit 4, since H = 01000 and I = 01001 differ in only that bit (top). On a subsequent search in the trie that comes to the new node, we want to check H (left link) if bit 4 of the search key is 0; if the bit is 1 (right link), the key to check is I.
To insert N = 01110 (bottom), we add a new node in between H and I to check bit 2, since that bit distinguishes N from H and I.
Program 15.6 is an implementation of the patricia-trie search algorithm. The method differs from trie search in three ways: there are no explicit null links, we test the indicated bit in the key instead of the next bit, and we end with a search key comparison at the point where we follow a link up the tree. It is easy to test whether a link points up, because the bit indices in the nodes (by definition) increase as we travel down the tree. To search, we start at the root and proceed down the tree, using the bit index in each node to tell us which bit to examine in the search key we go right if that bit is 1, left if it is 0. The keys in the nodes are not examined at all on the way down the tree. Eventually, an upward link is encountered: each upward link points to the unique key in the tree that has the bits that would cause a search to take that link. Thus, if the key at the node pointed to by the first upward link encountered is equal to the search key, then the search is successful; otherwise, it is unsuccessful.
Figure 15.10 illustrates search in a patricia trie. For a miss due to the search taking a null link in a trie, the corresponding patricia trie search will take a course somewhat different from that of standard trie search, because the bits that correspond to one-way branching are not tested at all on the way down the trie. For a search ending at a leaf in a trie, the patricia-trie search ends up comparing against the same key as the trie search but without examining the bits corresponding to one-way branching in the trie.
The implementation of insertion for patricia tries mirrors the two cases that arise in insertion for tries, as illustrated in Figure 15.11. As usual, we gain information on where a new key belongs from a search miss. For tries, the miss can occur either because of a null link or because of a key mismatch at a leaf. For patricia tries, we need to do more work to decide which type of insertion is needed, because we skipped the bits corresponding to one-way branching during the search. A patricia-trie search always ends with a key comparison, and this key carries the information that we need. We find the leftmost bit position where the search key and the key that terminated the search differ, then search through the trie again, comparing that bit position against the bit positions in the nodes on the search path. If we come to a node that specifies a bit position higher than the bit position that distinguishes the key sought and the key found, then we know that we skipped a bit in the patricia-trie search that would have led to a null link in the corresponding trie search, so we add a new node for testing that bit. If we never come to a node that specifies a bit position higher than the one that distinguishes the key sought and the key found, then the patricia-trie search corresponds to a trie search ending in a leaf, and we add a new node that distinguishes the search key from the key that terminated the search. We always add just one node, which references the leftmost bit that distinguishes the keys, where standard trie insertion might add multiple nodes with one-way branching before reaching that bit. That new node, besides providing the bit-discrimination that we need, will also be the node that we use to store the new item.
We use the convention that the leftmost link (the one corresponding to a key that is all 0 bits) does not point to any internal node. We need such a convention because the number of external links exceeds the number of internal nodes by precisely 1 in every binary tree. To make sure that no search ever follows that link, we further adopt the convention for class types that only the null key has all 0 bits. This convention is easy to enforce by implementing bit so as to always return 0 for the null key and to return 1 after exhausting the bits of any non-null key (see Exercise 15.34). Figure 15.12 shows the initial stages of the construction of a sample trie, which illustrate these conventions.
Figure 15.12. Patricia-trie construction
This sequence depicts the result of inserting the keys A S E R C H into an initially empty patricia trie. Figure 15.11 depicts the result of inserting I and then N into the tree at the bottom.
Program 15.7 is an implementation of the patricia-trie insertion algorithm. The code follows directly from the description in the previous paragraph, with the additional observation that we view links to nodes with bit indices that are not larger than the current bit index as links to external nodes. The insertion code merely tests this property of the links, but it does not have to move keys or links around at all. The upward links in patricia tries seem mysterious at first, but the decisions about which links to use when each node is inserted are surprisingly straightforward. The end result is that using one node type rather than two simplifies the code substantially.
Program 15.7 Patricia-trie insertion
To insert a key into a patricia trie, we begin with a search. The method searchR from Program 15.6 gets us to a unique key in the tree that must be distinguished from the key to be inserted. We determine the leftmost bit position at which this key and the search key differ, then use the recursive method insertR to travel down the tree and to insert a new node containing v at that point.
In insertR, there are two cases, corresponding to the two cases illustrated in Figure 15.11. The new node could replace an internal link (if the search key differs from the key found in a bit position that was skipped) or an external link (if the bit that distinguishes the search key from the found key was not needed to distinguish the found key from all the other keys in the trie).
This code assumes that KEY is a class type and depends upon bit being implemented so that null is the only key that is all 0s (see text).
private Node insertR(Node h, ITEM x, int i, Node p) { KEY v = x.key(); if ((h.bit >= i) || (h.bit <= p.bit)) { Node t = new Node(x, i); t.l = bit(v, t.bit) == 0 ? t : h; t.r = bit(v, t.bit) == 0 ? h : t; return t; } if (bit(v, h.bit) == 0) h.l = insertR(h.l, x, i, h); else h.r = insertR(h.r, x, i, h); return h; } void insert(ITEM x) { inti=0; KEY v = x.key(); ITEM t = searchR(head.l, v, -1); KEYw=(t==null) ? null : t.key(); if (v == w) return; while (bit(v, i) == bit(w, i)) i++; head.l = insertR(head.l, x, i, head); } Program 15.8 Patricia-trie sort
This recursive procedure shows the records in a patricia trie in order of their keys. We imagine the items to be in (virtual) external nodes, which we can identify by testing when the bit index on the current node is not larger than the bit index on its parent. Otherwise, this program is a standard inorder traversal.
private String toStringR(Node h, int i) { if (h == head) return ""; if (h.bit <= i) return h.item + "\n"; return toStringR(h.l, h.bit) + toStringR(h.r, h.bit); } public String toString() { return toStringR(head.l, -1); } By construction, all external nodes below a node with bit index k begin with the same k bits (otherwise, we would have created a node with bit index less than k to distinguish two of them). Therefore, we can convert a patricia trie to a standard trie by creating the appropriate internal nodes between nodes where bits are skipped and by replacing links that point up the tree with links to external nodes (see Exercise 15.52). However, Property 15.2 does not quite hold for patricia tries, because the assignment of keys to internal nodes does depend on the order in which the keys are inserted. The structure of the internal nodes is independent of the key-insertion order, but external links and the placement of the key values are not.
An important consequence of the fact that a patricia trie represents an underlying standard trie structure is that we can use a recursive inorder traversal to visit the nodes in order, as demonstrated in the implementation given in Program 15.8. We visit just the external nodes, which we identify by testing for nonincreasing bit indices.
Patricia is the quintessential radix search method: it manages to identify the bits that distinguish the search keys and to build them into a data structure (with no surplus nodes) that quickly leads from any search key to the only key in the data structure that could be equal to the search key. Figure 15.13 shows the patricia trie for the same keys used to build the trie of Figure 15.9 the patricia trie not only has 44 percent fewer nodes than the standard trie but also is nearly perfectly balanced.
Figure 15.13. Patricia-trie example
This patricia trie, built by insertion of about 200 random keys, is equivalent to the trie of Figure 15.9, with one-way branching removed. The resulting tree is nearly perfectly balanced.
Property 15.5
Insertion or search for a random key in a patricia trie built from N random bitstrings requires about lg N bit comparisons on the average, and about 2 lg N bit comparisons in the worst case. The number of bit comparisons is never more than the length of the key.
This fact is an immediate consequence of Property 15.3, since paths in patricia tries are no longer than paths in the corresponding trie. The precise average-case analysis of patricia is difficult; it turns out that patricia involves one fewer comparison, on the average, than does a standard trie (see reference section). 
Table 15.1 gives empirical data supporting the conclusion that DSTs, standard binary tries, and patricia tries have comparable performance (and that they provide search times comparable to or shorter than the balanced-tree methods of Chapter 13) when keys are integers, and certainly should be considered for symbol-table implementations even with keys that can be represented as short bitstrings, taking into account the various straightforward tradeoffs that we have noted.
Note that the search cost given in Property 15.5 does not grow with the key length. By contrast, the search cost in a standard trie typically does depend on the length of the keys the first bit position that differs in two given keys could be arbitrarily far into the key. All the comparison-based search methods that we have considered also depend on the key length if two keys differ in only their rightmost bit, then comparing them requires time proportional to their length. Furthermore, hashing methods always require time proportional to the key length for a search in order to compute the hash function. But patricia immediately takes us to the bits that matter and typically involves testing less than lg N of them. This effect makes patricia (or trie search with one-way branching removed) the search method of choice when the search keys are long.
| These relative timings for construction and search in symbol tables with random sequences of 32-bit integers confirm that digital methods are competitive with balanced-tree methods, even for keys that are random bits. Performance differences are more remarkable when keys are long and are not necessarily random (see Table 15.2), or when careful attention is paid to making the key-bit access code efficient (see Exercise 15.23). | ||||||||
| construction | search hits | |||||||
| N | R | D | T | P | R | D | T | P |
| 1250 | 25 | 14 | 14 | 16 | 5 | 3 | 4 | 3 |
| 2500 | 43 | 23 | 29 | 29 | 9 | 7 | 6 | 5 |
| 5000 | 70 | 43 | 43 | 60 | 19 | 15 | 12 | 11 |
| 12500 | 116 | 96 | 100 | 102 | 59 | 47 | 36 | 32 |
| 25000 | 298 | 204 | 251 | 305 | 147 | 115 | 87 | 80 |
| 50000 | 1120 | 464 | 476 | 604 | 356 | 290 | 198 | 180 |
| 100000 | 2476 | 1189 | 1172 | 1411 | 853 | 665 | 456 | 429 |
| 200000 | 3591 | 4487 | 2505 | 3240 | 1884 | 1579 | 1012 | 945 |
| Key: R Red black BST (Programs 12.15 and 13.6) D DST (Program 15.2) T Trie (Programs 15.3 and 15.4) P Patricia trie (Programs 15.6 and 15.7) | ||||||||
For example, suppose that we have a computer that can efficiently access 8-bit bytes of data, and we have to search among millions of 1000-bit keys. In this case, patricia would require accessing only about 20 bytes of the search key for the search, plus one 125-byte equality comparison; in contrast, hashing would require accessing all 125 bytes of the search key to compute the hash function (plus a few equality comparisons), and comparison-based methods would require 20 to 30 full key comparisons. It is true that key comparisons, particularly in the early stages of a search, require only a few byte comparisons, but later stages typically involve many more bytes. We shall consider comparative performance of various methods for searching with lengthy keys again in Section 15.5.
Indeed, there needs to be no limit at all on the length of search keys for patricia. Patricia is particularly effective in applications with variable-length keys that are potentially huge, such as the one discussed in Section 15.5. With patricia, we generally can expect that the number of bit inspections required for a search among N records, even with huge keys, will be roughly proportional to lg N.
Exercises
15.34 Modify the implementation of the two-parameter bit method in the text after Program 15.1 to return 1 if its second parameter is not less than bitsword and to always return 0 if its first parameter is null.
15.35 What happens when you use Program 15.7 to insert a record whose key is equal to some key already in the trie?
15.36 Draw the patricia trie that results when you insert the keys E A S Y Q U T I O N in that order into an initially empty trie.
15.39 Run empirical studies to compare the height and internal path length of a patricia trie built by insertion of N random 32-bit keys into an initially empty trie with the same measures of a standard binary search tree and a red black tree (Chapter 13) built from the same keys, for N = 103, 104, 105, and 106 (see Exercises 15.6 and 15.14).
15.40 Give a full characterization of the worst-case internal path length of a patricia trie with N distinct w-bit keys.
15.41 Implement a lazy count operation for the patricia-based symbol table implementation of Programs 15.5 through 15.7.
15.42 Add an integer field N to Node and modify the patricia code in Programs 15.5 through 15.7 to implement an eager count operation that takes constant time.
15.43 Implement the select operation for a patricia-based symbol table.
15.44 Implement the remove operation for a patricia-based symbol table.
15.48 Modify patricia search and insertion (Programs 15.6 and 15.7) to maintain a table of 2r tries, as described in Exercise 15.24.
15.49 Show that each key in a patricia trie is on its own search path and is therefore encountered on the way down the tree during a search operation as well as at the end.
15.50 Modify patricia search (Program 15.6) to compare keys on the way down the tree to improve search-hit performance. Run empirical studies to evaluate the effectiveness of this change (see Exercise 15.49).
15.51 Use a patricia trie to build a data structure that can support an existence table ADT for w-bit integers (see Exercise 15.33).
| Top |
EAN: 2147483647
Pages: 158