This has been an area of interest for me as part of working on Typesense[1]. If you are looking to implement spelling correction, you cannot but not stumble on

This has been an area of interest for me as part of working on Typesense[1]. If you are looking to implement spelling correction, you cannot but not stumble on this excellent post by Peter Norvig (most of it written on a bored flight journey!). While it's clever and concise, in terms of raw speed, indexing your vocabulary in a Trie, and then doing a traversal on it using a Levenshtein distance is way faster[2]. By using a trie, you eliminate lot of unwanted look-ups that Peter Norvig's brute-force approach takes. The other interesting thing for me personally about this problem is that there is a statistical angle as well. You will often find words that are of the same edit distance from a given target word -- you will need to rely on some form of "popularity metric" to rank those tied corrections. E.g. how many times did people type this word and then change it to another word - that's precisely the kind of data that Google has and which makes its search suggestions and spell checking so intuitive. [1]: https://typesense.org/ https://typesense.org/ [2]: http://stevehanov.ca/blog/index.php?id=114 http://stevehanov.ca/blog/index.php?id=114