A spell-checker accepts words and reports whether they are valid dictionary entries. A practical live implementation must respond at each word or separator, use little CPU and memory, and allow users to add words. section 6.1
Choose the underlying dictionary structure according to the required operations:
- Use a Bloom filter for compact membership checks when controlled false positives are acceptable; missed spelling errors can result. section 4.7.5 section 6.1.1
- Use a hash table for fast lookup on a static set, or a balanced search tree when the dictionary must remain open and dynamic. section 6.1.1
- Use a trie for efficient string searches, insertion, removal, user-added words, and typo detection without false positives. section 4.7.5 section 6.1.1
The basic design wraps a dictionary: the spelling operation calls contains, and a miss triggers visual feedback such as a red wavy underline. To build it with a trie, insert every dictionary word, then search each input word. section 6.1.1 section 6.4.1
Suggestions by edit distance
For a checked word w with m characters and tolerance k, traverse the trie while maintaining edit-distance values for prefixes. Prune a subtree when every value exceeds k; otherwise retain the closest stored key. For “amt,” “ant” may be the closest path but cannot be returned unless it is stored as a key, so “an,” “and,” or “anti” may be returned instead. section 6.4.1
Figure 6.22 Searching spell suggestions for the word s=”amt” using a trie. Notice that for each node, we only compute the last row of each table, based on the previous row (from the node’s parent). While the path with the closest distance to “amt” would spell “ant”, in this trie the corresponding node is not a key node, so “ant” is not stored in the trie and can’t be returned as a result! Instead, there are three keys at distance 2: “an”, “and”, “anti”. They can all be returned.
Use the figure to follow prefix traversal, row reuse, pruning, and the distinction between a trie path and a stored dictionary key. section 6.4.1
