techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

how is spell suggestion implemented?

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

Thursday, June 21, 2007
 
 
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.
K.Ashwin Kumar Send private email
Thursday, June 21, 2007
 
 
or try this from Peter Norvig (Google director of research):

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

Thursday, June 21, 2007
 
 
Ashwin, can you please tell more about k-gram technique?
logan Send private email
Saturday, July 14, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz