Kettle 里的字符串匹配算法

dong7mi 贡献于2014-11-14

作者 flower  创建于2014-11-14 01:15:00   修改者flower  修改于2014-11-14 03:15:00字数1420

文档摘要:Kettle里的字符串匹配算法Kettle里有两个地方找到相似度算法:“Calculator”步骤和“Fuzzymatch”步骤。这两个步骤里的相似度算法几乎一样,但是工作方式不一样;从字典表中查询出相似度在一定范围内的记录。我们在使用这些步骤和算法之前,最好能理解这些算法的概念和用途。打开“Fuzzymatch”步骤,选择算法列表,可以看到有很多可用的算法,如“Damerau-Levenshtein”、“JaroWinkler”、”DoubleMetaphone”。
关键词:

Kettle里的字符串匹配算法 Kettle里有两个地方找到相似度算法:“Calculator”步骤和“Fuzzy match”步骤。这两个步骤里的相似度算法几乎一样,但是工作方式不一样;从字典表中查询出相似度在一定范围内的记录。我们在使用这些步骤和算法之前,最好能理解这些算法的概念和用途。打开“Fuzzy match”步骤,选择算法列表,可以看到有很多可用的算法,如“Damerau-Levenshtein”、“Jaro Winkler”、”Double Metaphone”。这些算法的共同点就是用来做字符串匹配。但是他们的工作方式不一样,所用不同算法适合做不同工作,如排重之类的工作。下面解释一下这些算法。 n 编辑距离算法(Levenshtein)和最佳字符串匹配算法(Damerau-Levenshtein):编辑一个字符串到另一个字符串需要多少步骤,根据步骤数,来计算两个字符串之间的距离。第一个算法里的编辑步骤只包括插入字符、删除字符、更新字符,第二个算法里还包括调换字符位置的步骤。需要的最少步骤数就是最好的结果,例如,“CASTERS”和“CASTRO”这两个字符串的距离就是2(步骤1:删除字母E;步骤2:把字母S替换为O)。 n 动态规划算法(Needleman-Wunsch):这个算法主要用户生物信息学领域,以差异扣分的方法算距离,上面的CASTERS和CASTRO的距离是-2. n 哈罗算法(Jaro)和哈罗温克勒算法(Jaro-Winkler):计算两个字符串的相似度,结果是介于0(完全不一样)到1之间的小树。例如我们使用Levenshtein算法计算CASTERS和POOH相似度时,结果是7,而使用Jaro或Jaro-Winkler算法时,结果是0,因为这两个字符串之间没有任何向四方。而Levenshtein算法总会得到一个距离,因为一个字符串经过编辑总是可以变成另一个字符串。 n 配对字母相似算法(Pair Letters similarity):只有“Fuzzy match”步骤里有这个算法,这个算法吧两个字符串都分割成多个字符对,任何比较这些字符对。如CASTERS 和CASTRO这个例子,这个字符串被分割为{CA,AS,ST,TE,ER,RS}和{CA,AS,ST,TR,RO}。最后的相似度=(相等的字符对个数)乘以2/两个字符串的字符对总个数,这个例子就是(3*2)/11=0.545(这个结果是匹配度非常高的)。 n 变音匹配算法(Metaphone)、双音位匹配算法(Double Metaphone)、同音匹配算法(Soundex)和精化前音匹配算法(RefinedSoundEx):这些算法都是利用单词的发音来做匹配,也称为语音算法。这些语音算法的缺点是以英语为基础,所用基本不能用于法语、西班牙语、荷兰语等其他语种。 当然,最后的问题就是我们应该选择哪个算法,这取决你要解决的问题。对信息提取的需求,例如,提取亚马逊上所有的图书,找出和Pentaho相关的图书,并给出相似度数,这是就可以换使用字符对的模糊匹配算法。但使用该算法时要小心匹配不准确的情况,如“Jos van Dongen”和“Davidson”这两个人名的相似度是0.615,而“Jos van Dongen”和“Dongen,J van”这两个人名的相似度是0.604,从计算结果看前面一对人名相似度更高,但我们明显可以看出后面的一对人名实际是同一个人。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 2 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档