Prefix top-k trie

Autocomplete has to answer "what are the best completions for app?" in a few microseconds. A trie (prefix tree) makes that cheap. Each path from the root spells out a string, so strings that share a prefix share a path. If each node also keeps its best completions, a lookup is just a walk down the prefix.

The big idea

Picture a phone book with a sticky note on each tab. The note for the AP tab lists the five most-called names that start with AP. To find suggestions, you open the tab and read the note. You never scan the whole book.

The picture breaks when the call counts change. The notes have to be rebuilt, which is why the lists are computed offline (see offline query aggregation).

Walking through it

Insert four scored strings. Each node on the path keeps the best three completions below it.

class Node:
    def __init__(self):
        self.children = {}
        self.top = []  # best (score, text) pairs, highest first

def build(scored, k=3):
    root = Node()
    for text, score in scored:
        node = root
        for ch in text:
            node = node.children.setdefault(ch, Node())
            node.top = sorted(node.top + [(score, text)], reverse=True)[:k]
    return root

def suggest(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return []
        node = node.children[ch]
    return [text for _, text in node.top]

root = build([("apple", 900), ("apps", 180), ("app store", 300), ("apply", 120)])
print(suggest(root, "app"))
print(suggest(root, "ap"))
print(suggest(root, "x"))

Output:

['apple', 'app store', 'apps']
['apple', 'app store', 'apps']
[]

For app, the node holds all four strings but keeps only the top three by score. apply (120) is dropped. The lookup for app costs three steps, one per character, whether the trie holds four strings or four hundred million.

This build sorts as it inserts, which is simple but slow on large data. Real builds merge child lists bottom-up in one pass.

Common mistakes

• Scanning all queries that start with the prefix. That is LIKE 'app%' at request time, and it scales with the number of matches.
• Confusing a node's list with the global top-k. Each node must hold the best completions under its prefix, not the best overall.
• Storing lists at every node without limits. Cap the depth, store lists only where traffic exists, and compress single-child chains.

Check yourself

1. In the example, apply gets a score of 1,000. Which suggestion drops out of the list for app?

Answer: apps (180) drops out, because the top three become apply, apple and app store.

2. Why does a prefix lookup cost the same whether the trie holds a thousand strings or a billion?

Answer: The walk takes one step per character of the prefix, and the answer is already stored at the node.

Key takeaways

• A trie shares prefixes, so each character is stored once along a path.
• Each node can hold its own top-k list, so a lookup reads one list.
• Build the lists ahead of time, not per keystroke.
• Keep each list at k items so every node stays small.

Further learning

Next, see how the scores are produced in offline query aggregation.