Designing a System that would detect typos and suggestions

Question

This was asked in an interview.

I think the answer can be done by constructing a trie of all valid words and then suggestions can be made based on a possible valid path which was otherwise given as incorrect.

Say if user types apfle, and system would detect that after ap a possible valid path was app, which would then satisfy apple.

Is there any better solution than this? Perhaps the one implemented by spell checkers.

score 2 · Accepted Answer · edited May 23 '17 at 12:01

2

See:

How does the Google "Did you mean?" Algorithm work?

How do I approximate "Did you mean?" without using Google?

How to write a spelling corrector

Youtube Video: Search 101

edited May 23 '17 at 12:01

Community

1
1

answered May 08 '11 at 17:56

magma

8,432
1
35
33

Not the answer I was hoping for, since this is an interview question and the expected answer should be quite short. I guess this is one of those open ended question where Interviewer was looking for design approach rather than whole answer. – Shamim Hafiz - MSFT May 13 '11 at 12:14

score 0 · Answer 2 · answered May 08 '11 at 18:04

0

Within typical search engines you will find a lot of Analyzer stuff, which directs to the same underlying problem. A very popular Analyzer would be the n-gram Analyzer.

Perhaps this helps.

answered May 08 '11 at 18:04

Omnaest

3,096
1
19
18

Designing a System that would detect typos and suggestions

2 Answers2