@above : wrote in hurry..so ignore grammatical mistake. :P :P On Sun, Jan 29, 2012 at 12:27 PM, atul anand <[email protected]>wrote:
> one approach could be following :- > > i have check MS-word and found out that for a given incorrect > words....words suggested are of length = lenght(incorrect_word)+1 or to be > on a safer side take it as lenght(incorrect_word)+2. > > we are assuming that we user is not making mistake greater that > len(incorret_word)+2; > > for for input auw , suggested words are auk,aiwa,awe,awl,aduwa. > > so before running " levenshtein distance " ... check if the given word in > dictionary passes this test....so here we have narrowed down the sugessted > items. > > you can further refine it by the following ways:- > > and all passed strings from above approach , make one more check... > > check the similarity between incorrect string and suggested string... > > check if incorrectString[i...m]==suggestedString[i...n]; > here we are just checking ascii value of of both strings at position[i]; > this would take O(n).. > if the difference is not greater that suggested > strlen(incorrect_string)/2; > > obv there could be many string which would pass above test. > now run this levenshtein distance B/W incorrect_string and string which > has passed both of above test... and show only those string whose cost is > minimum. > > > On Sun, Jan 29, 2012 at 3:07 AM, Ravi Ranjan <[email protected]>wrote: > >> i wanna write the "spell check function" >> >> like when we put some word with spelling mistake then it tell the most >> suitable word matching to it( green error line of spelling in MS-Word) >> >> i used "levenshtein distance " algorithm to find the subset from the >> dictionary >> >> but it is a linear search... and takes much...... >> >> so is there any other data structure or approach to solve the problem to >> reduce complexity....... or "levenshtein distance " algorithm can be used >> in some other way >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
