RSS Feed

techInterview Discussion

A question from Google. Compute edit distance one by one to the words in the dictionary?

There are few efficient ways to do this

1) Tries can be used with similarity finding algorithm.
2) Phonetic Hashing can be done using "soundex algorithms", so that similar-sounding terms hash to the same value.
3) combination of K-gram indexing and edit distance.

or try this from Peter Norvig (Google director of research):

http://www.norvig.com/spell-correct.html

Ashwin, can you please tell more about k-gram technique?