the approach came just from the top of my head :) please check suffix trie @ http://www.allisons.org/ll/AlgDS/Tree/Suffix/
if you understand this as well as levensthien distance concept, you would understand how i thought of this solution Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, Jul 7, 2010 at 3:08 PM, souravsain <[email protected]> wrote: > @ashgoel > > Thanks for the reply. Any web link or book / chapter from which I can > read more about the nearest word finding approach using trie you > mentioned? > > Thanks in advance. > Sourav > > On Jul 4, 11:12 am, ashgoel <[email protected]> wrote: > > bloom filters are used for approx matches, however, if you want the > > nearest word finding, and a dictionary is available, may be a trie, > > then till there is a match move, into the trie down, however if there > > is a mismatch, calculate the levenstein distan with the rest of the > > characters in the pattern and the down strings within the trie and > > list down the lowst distance words > > > > On Jul 4, 8:40 am, souravsain <[email protected]> wrote: > > > > > > > > > Hi All > > > > > I am looking for an algorithm for approximate string matching problem. > > > This is a common known problem and I do have one from Steven S Skiena > > > in his book Algorithm Design Manual [Chapter 8]. Link / guide to any > > > other good algorithm will be of great help.[Please don't send results > > > of google search. Looking for some source where member has read and > > > used / liked it] > > > > > For those who are not familiar to this problem, it gives me a list of > > > possible words from known dictionary of words, if I type type a word > > > with some spelling mistake. Like I type "peple" and it should give me > > > "people","peble","purple" etc..... > > > > > Thanks, > > > Sourav- Hide quoted text - > > > > - Show quoted text - > > -- > 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]<algogeeks%[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.
