Maximum edit distance is the largest permitted Levenshtein difference between a search string and a candidate. In a trie-based spell-checker, a threshold k accepts suggestions whose distance is at most k. section 6.4.1
During traversal, maintain distances between the current trie path and every prefix of the search string. Prune a subtree when every distance exceeds the maximum tolerance, because later distances cannot improve. Otherwise, compare the distance for the complete search string with the best result found so far. section 6.4.1
Searching for “amt”
With “amt” as the target, the closest path may spell “ant”, but it is not returned when “ant” is not a stored key. At distance 2, the stored keys “an”, “and”, and “anti” can 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.
The figure traces prefix-distance rows for “amt” and shows how the trie search retains only stored keys within the permitted distance. section 6.4.1
