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 <ravi.cool2...@gmail.com>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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
