Figure 1: A compressed trie of the terms
*ant*, *bat*, *bean*, *bear*, *bird*, *bug* and *cat*

Figure 2: A balanced compressed ternary search tree of the terms
*ant*, *bat*, *bean*, *bear*, *bird*, *bug* and *cat*

Autocomplete is a feature provided by many computer programs and web applications.
It helps the user with typing by suggesting terms that start with the prefix typed so far.
If the underlying set of terms is large and the terms are weighted somehow (e.g. by popularity)
so that only the `k` highest-weighted matching terms are suggested,
then this requires a data structure that efficiently supports the top-`k` queries.
The *suggest tree* described here is such a data structure.
An implementation in Java can be downloaded
here.

The suggest tree for a given set of weighted terms is a compressed trie of the terms where
each node holds a weight-ordered list of the `k` highest-weighted terms
that start with the prefix or prefixes corresponding to the node.
The precomputed suggestion lists may seem space-consuming at first,
but the average length of a list in the tree tends to be very small
as typically most of the nodes are at the bottom of the tree.
Note that the number of nodes in the tree cannot be greater than twice the number of terms,
since for each term inserted into the tree,
at most one new node is added and at most one existing node is split into two nodes.

Suggest trees allow you to insert a new term or to reweight or remove an existing term.
The suggestion lists along the path from the root to the terminal node of the term are updated if necessary.
The worst case occurs
when you remove a term that is listed in a list of length `k`,
or when you reduce the weight of a term that is or becomes the lowest-weighted element in a list of length `k`.
In both situations, the term may have to be replaced in the list with the highest-weighted unlisted term.
To find this top unlisted term,
the suggestion list of each child node is searched for the first term that is not listed in the parent's list.
This requires at most `k` simple address comparisons per child.

The trie structure of a suggest tree is implemented by a compressed ternary search tree.
This trie implementation variant, where the children of a trie node are arranged as a binary search tree,
usually offers a good trade-off between time and space costs. For example,
searching for a prefix of length `m` in a balanced ternary search tree of `n` terms
requires at most `m` + log_{2}(`n`) character comparisons.
One can build such a balanced ternary search tree from a sorted set of terms
by inserting first the middle term and then recursively the middle term of the left and right subset,
just as for a balanced binary search tree of the terms.
Note that the frequently visited nodes near the root tend to be in the cache
so that they can be accessed faster.
Note also that only the first character of a node is stored explicitly,
subsequent characters are read from one of the matching terms.

Last modified: 2014-07-21 nicolai.diethelm@gmail.com