Re: corrections on a dfa's input strings?

On Apr 11, 7:50 am, vega_l...@yahoo.es 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 http://en.wikipedia.org/wiki/Soundex
. Knuth probably has the most famous implementation.There are modern
improvements.
[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 comp.compilers page.
Search the comp.compilers archives again.