Tries for prefix lookups: autocomplete and longest-prefix matching

What it is

The NIST dictionary defines a trie as a tree for storing strings with one node for every common prefix. Each edge carries one symbol (a byte, character or bit), and a terminal marker or leaf identifies stored keys. Looking up a key walks one edge per symbol, so the cost depends on the key's length, not on the number of stored keys. All keys sharing a prefix live in the subtree below that prefix's node. A radix tree (Patricia or compact trie) merges chains of single-child nodes into one labelled edge to save memory. The Linux kernel's IPv4 routing table is an LC-trie whose lookup, as its documentation describes, backtracks through the trie to find the longest matching prefix for a destination address.

Why it matters

Two operations are awkward with hash tables: "every key starting with X" and "the longest stored key that is a prefix of X". Tries make the first a subtree walk and the second a single descent that remembers the last terminal node passed. Autocomplete, HTTP path routers, IP longest-prefix match, tokenisers and blocklists all reduce to one of the two.

How to apply

• Fix the alphabet first: bytes are simplest; for text, normalise (Unicode NFC, case folding) identically on insert and lookup and decide whether nodes are code points or UTF-8 bytes.
• Choose the node layout by alphabet density: an array of children for small dense alphabets, a small sorted array or hash map for sparse ones, radix compression when keys share long runs.
• Autocomplete: descend to the prefix node, then traverse with a result limit; store per-node counts or a cached top-k to answer "most frequent completions" without walking the whole subtree.
• Longest-prefix match: walk the query, record the deepest terminal node seen, return it when the walk ends or fails.
• Before building one, try a sorted array: bisect_left on the prefix followed by a scan while entries still start with it handles autocomplete over static data with far less memory. A trie pays off with frequent updates, longest-prefix queries or very long shared prefixes.

Pitfalls

Naive nodes with 256 pointers cost kilobytes each; memory, not speed, is the usual failure. Deletion must prune non-terminal nodes left without children. Normalisation mismatches make keys invisible. Recursive traversal over long keys hits stack limits. Tries do not answer infix, suffix or fuzzy queries; those need other indexes.