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 <souravs...@gmail.com> 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 <ashg...@gmail.com> 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 <souravs...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
