|corrections on a dfa's input strings? firstname.lastname@example.org (2008-04-11)|
|Re: corrections on a dfa's input strings? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-04-11)|
|Re: corrections on a dfa's input strings? email@example.com (Gene) (2008-04-15)|
|Re: corrections on a dfa's input strings? firstname.lastname@example.org (Stefan Monnier) (2008-05-20)|
|Date:||Tue, 15 Apr 2008 09:46:00 -0700 (PDT)|
|Keywords:||lex, errors, comment|
|Posted-Date:||15 Apr 2008 13:56:08 EDT|
On Apr 11, 7:50 am, vega_l...@yahoo.es wrote:
> I've implemented a dfa with a keyword tree, I'm already adding and
> removing keys from it, or even perfoming completion as readline does
> for us on a console.
> My question is if there's anybody who could tell me about algorithms,
> names (I'm not english), or resources I can look for when trying to do
> corrrections on input strings against those already registered within
> the dfa.
> The idea is quite similar to the "did you mean: ..." from google. I
> feed the dfa with a string for a lookup operation, and perhaps that
> operation returns unsuccesful as there's no key registered matching
> exactly the input string, then, an algorithm comes to aid doing some
> trial an error, till it deduces that either, the user made a typo, or
> that others keys sintactically similar could also match his/her
> Any comments really appreciated.
I'm surprised no one has mentioned the soundex algorithm, which is
older than the hills. See for example http://en.wikipedia.org/wiki/Soundex
. Knuth probably has the most famous implementation.There are modern
[Soundex is adequate for "sounds like" errors, but I'm not sure how useful
it would be for keyboard errors. There was a Lisp project many years ago
called DWIM for Do What I Mean that might have some useful ideas. -John]
Return to the
Search the comp.compilers archives again.