Model completion as a trie you walk to a prefix node and then read from, so every query returns an exact ranked list you can assert against - no external index, no network. Every lesson is one concrete spec with exact trie shapes, completion lists, and ranked order: shared prefixes reusing nodes, a subtree collected in lexicographic order, top-K broken lexicographically on a weight tie, a cached node top equaling the brute-force scan after an insert, and a recorded selection lifting a term above a previously-higher neighbor.
Over 26 lessons you build a working autocomplete engine from scratch as a library you import: you add weighted terms, query a prefix to get a ranked list of completions, and record a selection so the engine learns. It is built on a trie (a prefix tree), which keeps every query exactly testable - you walk to the node that ends a prefix and read the completions in its subtree - with no external search index and no network, so the engine you write is the same in any language.
You start with the trie itself: a node keyed by rune with an end-of-word marker, inserting words so shared prefixes reuse nodes, and membership lookup. Then you add prefix traversal - walk to a prefix node and collect every completion beneath it by depth-first search in deterministic lexicographic order, handling the prefix-is-a-whole-word case, an empty prefix that returns everything, and a missing prefix that returns nothing. On top of that you attach a weight to each term and return the top-K completions ordered by weight with a lexicographic tie-break, then make queries fast by caching each node's best completions so a lookup is O(prefix length + K) instead of scanning the whole subtree. Finally the engine learns: recording a selection bumps a term's weight and re-ranks it, an unseen selection is added on the fly, matching folds case while preserving the display form, terms can be multi-word phrases, and an optional lesson tolerates a single typo in the prefix. The capstone loads a real weighted term list and serves exact ranked completions for several prefixes as you type, re-ranking after each recorded selection.
This is a teaching-grade autocomplete engine built around the classic trie plus cached-top-K design: it is in-memory, single-threaded, and returns exact ranked lists. It is honest about what it stops short of - it does not persist or distribute the index, it does not compress the trie into a finite-state transducer the way production completion suggesters do, its typo tolerance is limited to a single character substitution in the prefix rather than full edit-distance search, and it has no per-user personalization or context - which is exactly the honest core that systems like Elasticsearch's completion suggester and Google's search box extend with compression, sharding, and ranking signals.
Autocomplete needs a data structure that shares work across words with common prefixes. That structure is a trie - a tree where each edge is a character. Today you define its node and create an empty engine that knows it holds nothing yet.
Define a trie node keyed by character and create an empty trie that reports zero words.
A trie (pronounced “try”, from retrieval) is a tree that stores strings by
their characters: the root is the empty string, and following an edge labelled
c moves to the node for every word that has c at that position. Words that
share a prefix share the nodes for that prefix, which is exactly what makes a trie
the natural home for autocomplete - the completions of ca are everything in the
subtree hanging off the c-then-a node.
Today is deliberately tiny: one node type whose children map is keyed by the
next character, an end flag marking where a word finishes, and the Trie that
owns the root and a running word count. The weight field is along for the ride -
later lessons rank completions by it, so we reserve it now and leave it 0. Every
later lesson grows this same tree.
// one node per character position; children keyed by the next runetype node struct {children map[rune]*nodeend bool // true when a word ends exactly hereweight int // a term's rank score; unused until later, leave 0}type Trie struct {root *nodesize int}func NewTrie() *Trie { return &Trie{root: &node{children: map[rune]*node{}}} }func (t *Trie) Len() int { return t.size }
A genuinely working in-memory autocomplete engine - a trie of weighted terms, prefix completions collected in deterministic order, top-K ranking with a lexicographic tie-break, per-node cached top lists for O(prefix + K) reads with a full-scan fallback, learning from recorded selections, case-folding with a preserved display form, phrase terms, and a single-substitution typo fallback, all demoed by a small CLI - but it is single-process and single-threaded, keeps everything in memory (no persistence), has no delete or forget API, caps each node cache at a fixed size, and does not compress the trie the way production suggesters do.
The canonical treatment of R-way tries and ternary search tries - node structure, insert, prefix match, and collecting all keys under a subtree. The backbone of this project chapters one and two.
The Dr. Dobb's article and companion paper "Fast Algorithms for Sorting and Searching Strings" - a space-efficient alternative to the R-way trie that keeps the same prefix-and-completion operations you build here.
A concise reference on the prefix tree: shared prefixes, end-of-word markers, and the tradeoffs against hash tables and ternary search trees.
A system-design walkthrough of typeahead: a trie of weighted terms, caching each node's top suggestions for O(prefix + k) queries, and updating weights from usage - the exact shape this library builds in-process.
How a production search engine exposes prefix completion with per-term weights and top-K ranking - the same contract as this library, backed by a finite-state transducer instead of a plain trie.
The compression step this project deliberately skips: how Lucene stores a weighted term dictionary as an FST so completion stays fast at scale. Read it once the plain trie makes sense.