|
The problem is that what you call the actual answer - DPRK - is subjective. By picking DPRK you need a more intelligent algorithm than fuzzy string matching because you are looking for the right answer in terms of semantic knowledge of countries, not blind character comparisons. Fundamentally, the fact that DPRK is the right answer is an accident of History and English, there really is no right answer and no algorithm can capture this insight without being told. By biasing in one direction you are sacrificing performance in some other unknown. The trick is in balancing the bias with general ability. As always. 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: ("dice", "South Africa", 0.125);
("dice", "Congo", 0.0);
("dice", "Republic of Korea", 0.44);
("dice", "Democratic People's Republic of Korea", 0.24)]
and by blind luck ("ort Korea"), longest common sub-sequence does even better: [("lcs", "South Africa", 6.0);
("lcs", "Congo", 2.0);
("lcs", "Republic of Korea", 7.0);
("lcs", "Democratic People's Republic of Korea", 9.0)]
http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_dis...http://en.wikipedia.org/wiki/Dice_coefficient |
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.