Re: corrections on a dfa's input strings?

Gene <>
Tue, 15 Apr 2008 09:46:00 -0700 (PDT)

          From comp.compilers

Related articles
corrections on a dfa's input strings? (2008-04-11)
Re: corrections on a dfa's input strings? (Hans-Peter Diettrich) (2008-04-11)
Re: corrections on a dfa's input strings? (Gene) (2008-04-15)
Re: corrections on a dfa's input strings? (Stefan Monnier) (2008-05-20)
| List of all articles for this month |

From: Gene <>
Newsgroups: comp.compilers
Date: Tue, 15 Apr 2008 09:46:00 -0700 (PDT)
Organization: Compilers Central
References: 08-04-036
Keywords: lex, errors, comment
Posted-Date: 15 Apr 2008 13:56:08 EDT

On Apr 11, 7:50 am, wrote:
> Hello,
> 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
> request.
> Any comments really appreciated.
> Regards,

I'm surprised no one has mentioned the soundex algorithm, which is
older than the hills. See for example
. 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]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.