Edit distance measures how many single-character insertions, deletions, or substitutions are required to transform one string into another. It supports practical questions such as whether a misspelled word is close enough to a dictionary entry to suggest as a correction. section 6.4.1 section 6.4.2
For a trie-based search, compare the target word with the prefix represented by each visited node. Maintain an array whose i-th entry stores the smallest distance between that prefix and the first i characters of the target. Each child derives its row from its parent, so the search avoids recomputing every comparison from scratch. section 6.4.1
A spell-checker can use the distance as a search constraint:
- Set a maximum tolerated distance k and traverse dictionary words stored in a trie. section 6.4.1
- Prune a subtree when every distance in the current array exceeds k, because descendants cannot improve the result. section 6.4.1
- For key nodes, compare the distance for the complete target with the best result found so far and retain the closest key. section 6.4.1
Searching for “amt”
A trie may contain “an”, “and”, and “anti”, while the closest path spells “ant”. Because “ant” is not stored as a key, it cannot be returned; the three stored keys can instead be returned at distance 2. section 6.4.1
For two strings, direct Levenshtein computation is effective. Comparing one target with n corpus strings costs O(n * m * M), where m is the target length and M is the average corpus-string length. A trie changes repeated matching to O(m * N) after construction, where N is the total number of trie nodes; threshold pruning can reduce traversal further. section 6.4.2
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.
Trace the row update for each trie node while searching for “amt”, including why “ant” is excluded and which stored keys remain eligible. section 6.4.1
