soundex? http://en.wikipedia.org/wiki/Soundex
On 3/28/07, Kevin <[EMAIL PROTECTED]> wrote: > > > This is from an interview question, see how do you guys think of it: > > Given a Enlgish word, how to find these words that pronounce similar > to it? > > You can have some reasonable assumptions, such as: you have an > dictionary which tells you how each word pronounce (such as its > phonetic symbols), there is an existing function that can give you the > similarity of two words' pronunciation (for example, double d = > checkSimilarity(WordA, WordB), where d is between 0.0 to 1.0). You are > allowed to have other assumptions, if you think it is reasonable and > will help. > > A straight way is to compare the given word with all the words in the > dictionary, and order the d values, then return the top ranking ones. > This will take N comparisons for each given word. Plus the time to > sort the result (N*logN). > > Since this supposed to be a data structure and algorithm question, any > better ideas? > > I am thinking we can precompute a NxN similarity matrix, but even with > that, it is still N*logN for each word since we need to sort/rank it. > > Another method, of course, is to use the above method to precompute > and pre-ranking for every word --- but this sounds not an interesting > idea as for an interview question. :-) > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
