Trie (Prefix Tree), in depth: building a ranked, typo-tolerant autocomplete with best-first top-k, Levenshtein pruning and snapshot builds

The shape of the system

An autocomplete service has two halves that meet at an immutable artefact. Offline, a job aggregates candidate strings (past queries, product names, titles), normalises and filters them, assigns each a score, builds the trie and freezes it into a versioned snapshot. Online, each request normalises the typed prefix with the same function, walks to the prefix node, extracts the top k completions, falls back to a fuzzy search when exact matches are scarce, and returns a merged, deduplicated list.

Keeping the online path read-only removes locking from the hot path entirely, and makes every response reproducible from a snapshot version.

Normalise once, in one function

The trie matches characters exactly, so whatever is equal for the user must be equal as bytes. Apply Unicode normalisation (NFKC folds compatibility forms such as full-width letters; NFC is the conservative choice), case folding, whitespace collapsing and, where the language allows, accent removal. Store the display form separately at the terminal node so the user sees "Café Noir" while the key is "cafe noir". Ship the normalisation function as a single shared library used by the build and the server; a one-character difference between the two, such as an apostrophe variant, produces prefixes that silently match nothing.

Ranking: store the best score in every subtree

Each key has a score: query frequency, click-through, recency-weighted counts or a model's estimate. The trick that makes top-k fast is to store at every node the highest score anywhere beneath it. Insertion updates that maximum along the path; deletion or score decreases require recomputing it upward from the children, which is one reason production systems rebuild rather than mutate.

import heapq

class Node:
    __slots__ = ("kids", "score", "word", "best")
    def __init__(self):
        self.kids = {}        # character -> Node
        self.score = None     # set when a stored key ends here
        self.word = None      # display form of that key
        self.best = 0.0       # highest score anywhere in this subtree

class Autocomplete:
    def __init__(self):
        self.root = Node()

    def add(self, word, score):
        node = self.root
        node.best = max(node.best, score)
        for ch in word:
            node = node.kids.setdefault(ch, Node())
            node.best = max(node.best, score)    # maintain the subtree maximum
        node.score, node.word = score, word

    def locate(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.kids.get(ch)
            if node is None:
                return None
        return node

Best-first top-k

With subtree maxima, extracting the k best completions is a best-first search. Put the prefix node on a max-heap keyed by its best score. Repeatedly pop the top entry: if it is a finished key, emit it; otherwise push its own key (if one ends there) and each child, keyed by their scores. Because a subtree's key is an upper bound on everything inside it, the first k keys emitted are exactly the top k, and subtrees whose best score is lower than the k-th result are never expanded. Priority queues and heaps covers the heap operations used here.

def top_k_from(start, k=5):
    """Best-first search below one node: pop subtrees by their best score."""
    out, tie = [], 0
    heap = [(-start.best, tie, start, False)]
    while heap and len(out) < k:
        neg, _, node, is_word = heapq.heappop(heap)
        if is_word:
            out.append((node.word, -neg))
            continue
        if node.score is not None:          # the key ending here, as its own item
            tie += 1
            heapq.heappush(heap, (-node.score, tie, node, True))
        for child in node.kids.values():
            tie += 1
            heapq.heappush(heap, (-child.best, tie, child, False))
    return out

ac = Autocomplete()
for w, s in [("car", 9), ("cat", 8), ("care", 7), ("catalog", 6),
             ("dog", 5), ("card", 4), ("cart", 2)]:
    ac.add(w, s)
print(top_k_from(ac.locate("ca"), 3))    # [('car', 9), ('cat', 8), ('care', 7)]

Worked trace for prefix "ca" with k = 3. The heap starts with node ca (best 9). Pop ca: push child r (best 9) and child t (best 8). Pop r, the node for "car": push the key car (9) and its children d (4), e (7) and t (2). Pop key car: emit it. Pop node "cat" (8): push key cat (8) and child a (6). Pop key cat: emit it. Pop node "care" (7): push key care (7). Pop key care: emit it, and stop. The catalog, card and cart entries were pushed or skipped but never expanded.

Each emitted key costs heap operations along its path, roughly k x depth x branching factor pushes in the worst case, independent of how many million keys share the prefix. If that is still too slow for very short prefixes, precompute the top-k list at shallow nodes (depth three or less, say), where subtrees are huge and lists are few, and use best-first search below.

Typo tolerance: Levenshtein along trie paths

Users type "cqr" for "car". Edit distance between two strings is computed by dynamic programming one row per character, and the key observation is that a trie path is a string built one character at a time, so the DP row for a node can be derived from its parent's row. Walking the trie depth-first, each node computes one row of length |query| + 1. If the last entry is within the edit budget, the node's path is a fuzzy match for the whole query; if the smallest entry in the row exceeds the budget, no extension of this path can come back within it, so the entire subtree is skipped. Shared prefixes share work, which is the same reason tries beat checking each dictionary word separately.

def fuzzy_nodes(root, query, max_edits=1):
    """Trie nodes whose path is within max_edits of query (Levenshtein)."""
    hits = []
    def walk(node, ch, prev):
        row = [prev[0] + 1]
        for i in range(1, len(query) + 1):
            row.append(min(row[i - 1] + 1,                        # insertion
                           prev[i] + 1,                           # deletion
                           prev[i - 1] + (query[i - 1] != ch)))   # match / substitution
        if row[-1] <= max_edits:
            hits.append((row[-1], node))
        if min(row) <= max_edits:              # otherwise no descendant can recover
            for c2, kid in node.kids.items():
                walk(kid, c2, row)
    first = list(range(len(query) + 1))         # DP row for the empty path
    for ch, kid in root.kids.items():
        walk(kid, ch, first)
    return hits

def suggest(root, query, k=5, max_edits=1, penalty=0.5):
    """Complete from every node within max_edits; scale scores down per edit."""
    best = {}
    for edits, node in fuzzy_nodes(root, query, max_edits):
        for word, score in top_k_from(node, k):
            s = score * (penalty ** edits)
            if s > best.get(word, -1.0):
                best[word] = s
    return sorted(best.items(), key=lambda kv: -kv[1])[:k]

print(suggest(ac.root, "cqr", 3))    # [('car', 4.5), ('care', 3.5), ('card', 2.0)]

Here "cqr" matches the node for "car" with one substitution; completions below it are scored at half their normal value, so an exact-prefix suggestion with a decent score still outranks a typo correction. Scaling the edit budget with query length is a common heuristic: no edits for one to three characters, one edit up to about seven, two beyond, because short prefixes with an edit match almost everything. Many systems also require the first character to match exactly, which shrinks the search dramatically and matches how people mistype.

Freezing the trie for serving

Pointer-and-dictionary nodes are convenient for building but costly to serve: in a managed language each node can cost over a hundred bytes. The serving snapshot flattens the trie into arrays in breadth-first order: for each node, the offset of its first child and its child count, the child edge labels in sorted order, the subtree best score and an index into a table of display strings. Child lookup is a binary search over a short contiguous label run, the arrays can be memory-mapped, and loading a new version is just mapping a new file. Radix compression (collapsing single-child chains) typically removes most nodes from a query-log trie, since long tails of characters rarely branch.

Build, swap and freshness

Rebuild the snapshot on a schedule, validate it (key count within expected bounds, a set of golden prefixes returning expected results, no blocked terms present), then publish it and switch a single reference in each server atomically. Old snapshots stay on disk for instant rollback. For freshness between builds, such as a breaking news term, keep a small mutable overlay trie that receives new keys, query both at request time and merge results; the overlay is discarded at the next full build. Apply blocklists in the build, not only at query time, so a blocked string cannot appear even if a query-time filter fails. A Bloom filter is a cheap pre-check if the blocklist is large and query-time checks are still required.

Operating it

Clients should debounce keystrokes (tens of milliseconds) and cancel in-flight requests when a newer prefix is typed, so the server never answers stale prefixes. Cache responses for the shortest prefixes, which dominate traffic and change only with the snapshot. Track p50 and p99 server latency, the empty-result rate per prefix length, the fuzzy-fallback rate, and outcome metrics such as suggestion acceptance and keystrokes saved. A rising empty-result rate after a deploy almost always means the build and the server disagree about normalisation.

Failure modes

Trade-offs

A sorted array of keys with binary search finds the prefix range compactly, but ranking within a large range needs extra structure, such as a range-maximum index; the trie's subtree maxima give that directly. A hash table keyed by every prefix answers instantly with precomputed lists but stores each key once per prefix, which is affordable only for short keys or shallow depths. Finite state transducers, which also share suffixes, are far more compact for static sets and are what several search engines use for completion; they are harder to build and inspect. A full-text engine handles mid-word and multi-token matches that a prefix trie cannot. For classic "type the start of a phrase" autocomplete over up to tens of millions of entries, a frozen, ranked trie is simple, fast and easy to reason about.