Kettle 里的字符串匹配算法

Kettle里有两个地方找到相似度算法：“Calculator”步骤和“Fuzzy match”步骤。这两个步骤里的相似度算法几乎一样，但是工作方式不一样；从字典表中查询出相似度在一定范围内的记录。我们在使用这些步骤和算法之前，最好能理解这些算法的概念和用途。打开“Fuzzy match”步骤，选择算法列表，可以看到有很多可用的算法，如“Damerau-Levenshtein”、“Jaro Winkler”、”Double Metaphone”。这些算法的共同点就是用来做字符串匹配。但是他们的工作方式不一样，所用不同算法适合做不同工作，如排重之类的工作。下面解释一下这些算法。

         编辑距离算法(Levenshtein)和最佳字符串匹配算法(Damerau-Levenshtein):编辑一个字符串到另一个字符串需要多少步骤，根据步骤数，来计算两个字符串之间的距离。第一个算法里的编辑步骤只包括插入字符、删除字符、更新字符，第二个算法里还包括调换字符位置的步骤。需要的最少步骤数就是最好的结果，例如，“CASTERS”和“CASTRO”这两个字符串的距离就是2（步骤1：删除字母E；步骤2：把字母S替换为O）。

         动态规划算法(Needleman-Wunsch):这个算法主要用户生物信息学领域，以差异扣分的方法算距离，上面的CASTERS和CASTRO的距离是-2.

         哈罗算法（Jaro）和哈罗温克勒算法(Jaro-Winkler)：计算两个字符串的相似度，结果是介于0（完全不一样）到1之间的小树。例如我们使用Levenshtein算法计算CASTERS和POOH相似度时，结果是7，而使用Jaro或Jaro-Winkler算法时，结果是0，因为这两个字符串之间没有任何向四方。而Levenshtein算法总会得到一个距离，因为一个字符串经过编辑总是可以变成另一个字符串。

         配对字母相似算法（Pair Letters similarity）：只有“Fuzzy match”步骤里有这个算法，这个算法吧两个字符串都分割成多个字符对，任何比较这些字符对。如CASTERS 和CASTRO这个例子，这个字符串被分割为{CA,AS,ST,TE,ER,RS}和{CA,AS,ST,TR,RO}。最后的相似度=（相等的字符对个数）乘以2/两个字符串的字符对总个数，这个例子就是（3*2）/11=0.545（这个结果是匹配度非常高的）。

         变音匹配算法（Metaphone）、双音位匹配算法（Double Metaphone）、同音匹配算法（Soundex）和精化前音匹配算法（RefinedSoundEx）:这些算法都是利用单词的发音来做匹配，也称为语音算法。这些语音算法的缺点是以英语为基础，所用基本不能用于法语、西班牙语、荷兰语等其他语种。

当然，最后的问题就是我们应该选择哪个算法，这取决你要解决的问题。对信息提取的需求，例如，提取亚马逊上所有的图书，找出和Pentaho相关的图书，并给出相似度数，这是就可以换使用字符对的模糊匹配算法。但使用该算法时要小心匹配不准确的情况，如“Jos van Dongen”和“Davidson”这两个人名的相似度是0.615，而“Jos van Dongen”和“Dongen,J van”这两个人名的相似度是0.604，从计算结果看前面一对人名相似度更高，但我们明显可以看出后面的一对人名实际是同一个人。