Partial-Match Searching
We turn next to the more subtle problem of "partial-match" or "crossword puzzle" searching: A query string may contain both regular letters and the "don't care" character ".". Searching the dictionary for the pattern ".u.u.u" matches the single word auhuhu, while the pattern ".a.a.a" matches 94 words, including banana, casaba, and pajama. (That pattern does not match abracadabra, though. The entire word must match the pattern; we do not look for patterns in the middle of longer words.)
This venerable problem has been studied in many papers, such as in "The World's Fastest Scrabble Program," by A.W. Appel and G.J. Jacobson (Communications of the ACM, May 1988). In "Partial-Match Retrieval Algorithms," (SIAM Journal on Computing, 5, 1976), R.L. Rivest presents an algorithm for partial-match searching in digital tries: Take the single given branch if a letter is specified, for a don't-care character, recursively search all branches. Function pmsearch implements Rivest's method in ternary search trees. The function puts pointers to matching words in srcharr[0..srchtop-1]. It is called, for instance, by:
srchtop = 0; pmsearch(root, ".a.a.a");
The following is the complete search code:
void pmsearch(Tptr p, char *s)
{ if (!p) return;
nodecnt++;
if (*s == '.' || *s < p->splitchar)
pmsearch(p->lokid, s);
if (*s == '.' || *s == p->splitchar)
if (p->splitchar && *s)
pmsearch(p->eqkid, s+1);
if (*s == 0 && p->splitchar == 0)
srcharr[srchtop++] =
(char *) p->eqkid;
if (*s == '.' || *s > p->splitchar)
pmsearch(p->hikid, s);
}
Function pmsearch has five if statements. The second and fifth if statements are symmetric; they recursively search the lokid (or hikid) when the search character is the don't care "." or when the search string is less (or greater) than the splitchar. The third if statement recursively searches the eqkid if both the splitchar and string are nonnull. The fourth if statement detects a match to the query and adds the pointer to the complete word (stored in eqkid by our sleazy hack).
Rivest states that partial-match search in a trie requires "time about O(n(k-s)/k) to respond to a query word with s letters specified, given a file of n k-letter words." Ternary search trees can be viewed as an implementation of his tries (with binary trees implementing multiway branching), so we expected his results to apply immediately to our program. Our experiments, however, led to a surprise: Unspecified positions at the front of the query word are dramatically more costly than unspecified characters at the end of the word. (Rivest suggested shuffling the characters in a word to avoid such problems.) iTable 3i gives the flavor of our experiments. The first line says that the search visited 18 nodes to find the single match to the pattern "banana." The tree contains a total of 1,026,033 nodes; searches with some of the first letters specified visit just a tiny fraction of those nodes.
Table 3: Partial-match searching.
Near-Neighbor Searching
We finally examine the problem of "near-neighbor searching" in a set of strings: We are to find all words in the dictionary that are within a given Hamming distance of a query word. For instance, a search for all words within distance two of Dobbs finds Debby, hobby, and 14 other words.
Function nearsearch performs a near-neighbor search in a ternary search tree. Its three arguments are a tree node, string, and distance. The first if statement returns if the node is null or the distance is negative. The second and fourth if statements are symmetric: They search the appropriate child if the distance is positive or if the query character is on the appropriate side of splitchar. The third if statement either checks for a match or recursively searches the middle child.
void nearsearch(Tptr p, char *s, int d)
{ if (!p || d < 0) return;
if (d > 0 || *s < p->splitchar)
nearsearch(p->lokid, s, d);
if (p->splitchar == 0) {
if ((int) strlen(s) <= d)
srcharr[srchtop++] = (char *) p->eqkid;
} else
nearsearch(p->eqkid, *s ? s+1:s,
(*s == p->splitchar) ? d:d-1);
if (d > 0 || *s > p->splitchar)
nearsearch(p->hikid, s, d);
}
Our web site contains data on the performance of this search algorithm. It is quite efficient when searching for near neighbors, but searching for distant neighbors grows more expensive. A simple probabilistic model accurately predicts its run time on real data.
Conclusion
The primary challenge in implementing digital search tries is to avoid using excessive memory for trie nodes that are nearly empty. Ternary search trees may be viewed as a trie implementation that gracefully adapts to handle this case, at the cost of slightly more work for full nodes. Ternary search trees combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.
Ternary search trees have been used for several years to represent English dictionaries in a commercial optical character recognition (OCR) system built at Bell Labs. The trees were faster than hashing for the task, and they gracefully handle the 34,000-character set of the Unicode Standard. The designers have also experimented with using partial-match for word lookup: Replace letters with low probability of recognition with the "don't care" character.
Ternary search trees are efficient and easy to implement. They offer substantial advantages over both binary search trees and digital search tries. We feel that they are superior to hashing in many applications for the following reasons:
- Ternary trees do not incur extra overhead for insertion or successful searches.
- Ternary trees are usually substantially faster than hashing for unsuccessful searches.
- Ternary trees gracefully grow and shrink; hash tables need to be rebuilt after large size changes.
- Ternary trees support advanced searches, such as partial-match and near-neighbor search.
- Ternary trees support many other operations, such as traversal to report items in sorted order.
Jon is a Member of Technical Staff at Bell Labs. Bob is the William O. Baker Professor of Computer Science at Princeton University. They can be reached at [email protected] and [email protected], respectively.
