The question this module answers: what if you have many strings and keep asking questions about their beginnings? A hash
set answers "is this exact word present?" in O(L), but it can't answer "which words start with inf?" without looking at every
word. A trie (from retrieval, also called a prefix tree) stores strings so that every prefix is a node: the question
"what starts with inf?" becomes "walk three edges and look below".
ML context.
- Tokenizers: greedy longest-match subword tokenizers walk a trie of the vocabulary from each position (Section 4), and byte-pair encoding builds its vocabulary by merging frequent pairs (lessons 13.6 and 15.12).
- Autocomplete and query suggestion: the top completions for a typed prefix (lesson 13.5).
- Constrained decoding: forcing a language model to produce only valid labels or entity names by masking every token that doesn't continue a path in a trie of the allowed outputs.
- Lookups by prefix: feature names, file paths, URL routing, IP prefix tables.
1. The running problem: count words with a prefix
Task: given N words, answer Q queries of the form "how many words start with prefix p?"
With N = 10⁶ words and Q = 10⁵ queries (an autocomplete box as people type), that's 10¹¹ character comparisons. Every query re-reads words that can't possibly match.