10
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Nick Jul 17 '12 at 6:12
  • $\begingroup$ Note this related question. $\endgroup$ – Raphael♦ Jul 22 '12 at 9:45
  • $\begingroup$ 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? $\endgroup$ – Raphael♦ Jul 22 '12 at 9:47
5
$\begingroup$

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.

Given the heuristics, you can use likelihood to get a score which would (hopefully) be higher for your sample data than for other text. In order to determine a reasonable threshold, you can perform cross-validation. Pick a set of sample phrases which are not city names. Divide the city names into two parts, a large (say 80%) part and a small (say 20%) part. Train your model on the large part (that is, collect statistics on the large part), and then evaluate your model on the small part and on the sample of bad phrases. Determine if there is a reasonable threshold that passes most city names, but only a small amount of bad phrases.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. I had started looking in to n-gram but didn't know if I was totally off-base so I'm glad you mentioned it. Word length sounds interesting too and something I had not thought of. $\endgroup$ – Andrew Jul 17 '12 at 14:50
  • $\begingroup$ You might want to add character frequency to this. In particular, that should get rid of all numbery stuff. One advantage is that such frequencies are vectors of numbers which can be trained/recognised in a number of statistical models. $\endgroup$ – Raphael♦ Jul 22 '12 at 9:48
  • 1
    $\begingroup$ @Raphael, character frequency is the same as $1$-gram analysis, and in general $n+1$-gram analysis is finer than $n$-gram analysis. $\endgroup$ – Yuval Filmus Jul 24 '12 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.