This approach is far from been perfect. A simple recursive implementation of Levenshtein on a Trie representing the dictionary would produce better performance!
Can you elaborate? I don't see how you'd be able to come up with something 'simple' that still has a decent performance. Especially if the number of acceptable errors is configurable and 3 (or higher).
I think you mean a trie representing the dictionary plus edit-distance-2 (like the OP's algorithm does). There's no easy way to "skip" characters in a trie.
You can skip characters in a trie, at least towards the right-hand-end of a word, by recursing down every path. I've done so to good (and performant) effect, before.
Comments
This approach is far from been perfect. A simple recursive implementation of Levenshtein on a Trie representing the dictionary would produce better performance!
Can you elaborate? I don't see how you'd be able to come up with something 'simple' that still has a decent performance. Especially if the number of acceptable errors is configurable and 3 (or higher).
I think you mean a trie representing the dictionary plus edit-distance-2 (like the OP's algorithm does). There's no easy way to "skip" characters in a trie.
You can skip characters in a trie, at least towards the right-hand-end of a word, by recursing down every path. I've done so to good (and performant) effect, before.
You wouldn't have to. As described in the article, the dictionary maps from possible entry texts to the corrected terms.
In general a dynamic programming/DFA style approach would provide so much more win than what is discussed in this article.