4 ms·
This approach is far from been perfect. A simple recursive implementation of Levenshtein on a Trie representing the dictionary would produce better performance!
by jlemoine 13y ago
This approach is far from been perfect. A simple recursive implementation of Levenshtein on a Trie representing the dictionary would produce better performance!
- deleted 13y ago[deleted]
- colanderman 13y agoI 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.
- ghusbands 13y agoYou 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.
- cbsmith 13y agoYou wouldn't have to. As described in the article, the dictionary maps from possible entry texts to the corrected terms.
- darklajid 13y agoCan 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).
- cbsmith 13y agoIn general a dynamic programming/DFA style approach would provide so much more win than what is discussed in this article.