# Determining how similar a given string is to a collection of strings

I'm not sure if this question belongs here and I apologize if not. What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" in a bag of strings. For example, if I have bag of 10,000 US city names, and then I have the string "Philadelphia", I would like some quantitative measure of how likely 'Philadelphia' is a US city name based on the US city names I already know. While I know I won't be able to separate real city names from fake city names in this context, I would at least expect to have strings such as "123.75" and "The quick red fox jumped over the lazy brown dogs" excluded given some threshold.

To get started, I've looked at Levenshtein Distance and poked around a bit on how that's been applied to problems at least somewhat similar to the one I'm trying to solve. One interesting application I found was plagiarism detection, with one paper describing how Levenshtein distance was used with a modified Smith-Waterman algorithm to score papers based on how likely they were a plagarized version of a given base paper. My question is if anyone could point me in the right direction with other established algorithms or methodologies that might help me. I get the feeling that this may be a problem someone in the past has tried to solve but so far my Google-fu has failed me.

• If you have positive and negative examples available, then you could try to train a classifier. For features, to start I'd try pulling some simple statistics such as those suggested by Yuval Filmus.
– Nick
Jul 17 '12 at 6:12
• – Raphael
Jul 22 '12 at 9:45
• City names seem to be a bad example; they are all over the place, especially in the US. Here, table lookup seems to be the most effective way. Is your problem more general?
– Raphael
Jul 22 '12 at 9:47

Some better statistics to think of are word length and $n$-gram analysis. For word length, you can collect statistics of the distribution of word length of city names, and compare it to the length of what you get. $n$-gram analysis looks at the distribution of sequences of $n$ letters in your sample text (say $n=2$). Both approaches can be combined.
• @Raphael, character frequency is the same as $1$-gram analysis, and in general $n+1$-gram analysis is finer than $n$-gram analysis. Jul 24 '12 at 19:55