Re:Getting the closest string match
by MtotheThird on Friday May 04, 2012 @09:22AM
(#3928231)
Oh, I'm under no illusions that it's a universally applicable string matcher. What it seems to be useful for is normalizing human input in situations where someone can pick the best match. It handles typical normalization transforms well (word fragments, transpositions) and is very easy to index.
In my example, DPRK is the objective best answer .. There's pretty clearly a correct match in the value domain, the challenge is to help the user find it as quickly as possible.
Knowing which algorithm to use for a problem is most important; sometimes padded hamming will do, other times minhash or bitap or dice's coefficient etc are good. Each algorithm is a kind of balance between a metric and priorities - deciding what is subjectively most important in this problem. Your method for example is not as robust as Damerau Levenshtein when it comes to analyzing DNA sequences. As far as the best default string comparison, I have found dice coefficient to be ideal (your method appears to be based on similar ideas but my hunch is it's less robust).
For your example Dice's Coefficient does as well as can be expected without a concept of countries:
and by blind luck ("ort Korea"), longest common sub-sequence does even better: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_dis...http://en.wikipedia.org/wiki/Dice_coefficient