A spell-checker needs to test many words against a dictionary. A trie, also called a prefix tree, organizes the dictionary by character rather than storing each word as a separate string. Words with the same beginning share a path, making string search and prefix queries natural operations. section 6.4.1 section 6.2
Each edge represents one character. The root represents the empty string; following edges spells a prefix or word. A node’s key marker distinguishes a stored word from a prefix that merely leads to longer words. One implementation gives each node a Boolean marker and character-to-child links, with a non-key root. section 6.2
Figure 6.2 The structure of a trie. Words are encoded in the tree using edges, each edge corresponds to a single character, and each node n is associated with a single word, the one obtained by joining the characters associated with the edges in the path from the root to n. The root node corresponds to the empty string (because no edge is traversed), the leftmost leaf corresponds to “aa”, and so on. Not all the paths make meaningful words, and not all the nodes store the word associated with them. Only filled, black nodes (called “key nodes”) mark words stored in the trie, while hollow nodes, aka “intermediate nodes,” correspond to prefixes of words stored in the trie. Notice that all leaves should be key nodes.
Follow a path from the root to read its characters, then check whether its endpoint is marked as a stored key. An unmarked endpoint is only an intermediate prefix. section 6.2
The same paths support two useful queries:
- Exact search: starting at the root, follow the edge for each successive character. A missing edge means failure; after the last character, return the current node’s key marker. Reaching a node is not enough if it represents only a prefix. section 6.2.2
- Keys with a prefix: first follow the prefix to its endpoint. If that path exists, traverse its subtree and collect only marked keys, carrying the characters accumulated along each path. section 6.2.6
From typo detection to suggestions
Insert dictionary words into a trie. An exact-search miss can flag a typo. To suggest corrections, traverse candidate paths while updating edit distances; prune a subtree when every tracked distance exceeds the allowed tolerance. Suggestions must end at key nodes: a close-matching path that represents only a prefix is not a dictionary word. section 6.4.1
For a query of length m, exact search takes O(m); insertion and removal are also listed as O(m). Collecting keys beneath a prefix takes O(m + j) in the worst case when j trie nodes may be visited. Memory savings depend on shared prefixes: nodes and child links have costs of their own, and a trie with little prefix sharing can lose that advantage. A radix trie addresses space by compressing paths. section 6.2.7 section 6.2.6 section 6.2.1 section 6.5
