Skip to main content

Search Autocomplete

Every search box that finishes your sentence is running the same two-part trick: a trie that can answer "what starts with this prefix" fast, and a ranking step on top that decides which of those completions are worth showing first.

Requirements​

Functional

  • insert(word) adds a word to the index (or, for a query log, bumps its frequency if it's already there).
  • suggest(prefix, limit) returns up to limit completions of the prefix, ordered by descending frequency.
  • Recording that a suggestion was actually chosen should increase its rank for future queries with the same prefix.

Non-functional

  • suggest must not degrade to scanning every indexed word - it should only ever walk the subtree rooted at the prefix.
  • Frequency updates for one word must not require rewriting or re-inserting the word.

Design​

Trie stays a pure data structure: TrieNodes form the tree, and the only thing living at a terminal node is a frequency count. AutocompleteService sits on top and owns everything that isn't structural - what counts as "top," how ties break, whether a prefix is even long enough to bother suggesting for.

Search boxAutocompleteServiceTrieTrieNodesuggest("che", 5)1nodeAtPrefix("che")2children.get(ch)3collectWords(prefixNode)4topK(candidates, 5)5
  1. 1The UI only ever asks the service for suggestions - it never touches the trie.
  2. 2The service asks the trie to walk down to the node representing the prefix.
  3. 3One character at a time - if any character is missing, there are zero completions.
  4. 4From that node, every completion in the subtree is collected along with its frequency.
  5. 5Only the ranking step - a bounded heap by frequency - lives on the service, not the trie.

That split means the trie never has to change to support a new ranking rule; only the service does.

Class diagram​

AutocompleteService- trie: Trie- minPrefixLen: int+ record(word): void+ suggest(prefix, limit): List<String>Trie- root: TrieNode+ insert(word, freqDelta): void+ nodeAtPrefix(prefix): TrieNode+ collectWords(node): List<Entry>TrieNode- children: Map<char, TrieNode>- isEndOfWord: bool- frequency: int
Trie/TrieNode are pure structure. AutocompleteService owns ranking - a new ranking rule never touches the trie.

Code​

import java.util.*;
 
class TrieNode {
final Map<Character, TrieNode> children = new HashMap<>();
boolean isEndOfWord;
int frequency;
}
 
class Trie {
private final TrieNode root = new TrieNode();
 
void insert(String word, int freqDelta) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
node = node.children.computeIfAbsent(ch, c -> new TrieNode());
}
node.isEndOfWord = true;
node.frequency += freqDelta;
}
 
TrieNode nodeAtPrefix(String prefix) {
TrieNode node = root;
for (char ch : prefix.toCharArray()) {
node = node.children.get(ch);
if (node == null) return null;
}
return node;
}
 
List<Map.Entry<String, Integer>> collectWords(TrieNode start, String prefix) {
List<Map.Entry<String, Integer>> results = new ArrayList<>();
collect(start, new StringBuilder(prefix), results);
return results;
}
 
private void collect(TrieNode node, StringBuilder path, List<Map.Entry<String, Integer>> results) {
if (node.isEndOfWord) {
results.add(Map.entry(path.toString(), node.frequency));
}
for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {
path.append(e.getKey());
collect(e.getValue(), path, results);
path.deleteCharAt(path.length() - 1);
}
}
}
 
class AutocompleteService {
private final Trie trie = new Trie();
private final int minPrefixLen;
 
AutocompleteService(int minPrefixLen) {
this.minPrefixLen = minPrefixLen;
}
 
void record(String word) {
trie.insert(word, 1);
}
 
List<String> suggest(String prefix, int limit) {
if (prefix.length() < minPrefixLen) return List.of();
TrieNode prefixNode = trie.nodeAtPrefix(prefix);
if (prefixNode == null) return List.of();
 
PriorityQueue<Map.Entry<String, Integer>> heap =
new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
for (Map.Entry<String, Integer> candidate : trie.collectWords(prefixNode, prefix)) {
heap.offer(candidate);
if (heap.size() > limit) heap.poll();
}
 
List<String> result = new ArrayList<>();
while (!heap.isEmpty()) result.add(0, heap.poll().getKey());
return result;
}
}

Design decisions​

  • Frequency lives on the TrieNode at the end of a word, not in a separate map keyed by the word string. Bumping a word's rank after it's chosen is then a single tree walk to an existing node and an increment - no second data structure to keep in sync with the trie.
  • Ranking is a service-layer concern, not a trie method. Trie only knows how to collect every completion under a prefix node; AutocompleteService decides how many to keep and in what order. Swapping "most frequent" for "most recent" or "weighted by recency and frequency" is a change to one method on the service, never to Trie or TrieNode.
  • Collection uses a bounded min-heap of size limit instead of collecting every completion and sorting. For a common prefix with thousands of completions, sorting the whole set to return the top five wastes work proportional to the size of the whole subtree instead of the size of the answer.
  • What's missing for a real system: a trie with millions of words is memory-heavy node by node - production autocomplete usually compresses it into a DAWG (directed acyclic word graph) that shares suffixes - and live frequency increments on every keystroke create hot-node contention at scale, which is why real systems batch frequency updates from query logs offline instead of writing on the read path.
0%0 of 122 pages studied