匹配算法JaroWinkler.docx

常用数据匹配算法简介系类--Jaro–Winkler distance 算法数据是组织最具价值的资产之一。企业的数据质量与业务绩效之间存在着直接联系，高质量的数据可以使公司保持竞争力并在经济动荡时期立于不败之地。本文介绍在数据匹配算法 Jaro–Winkler distancewanghetommy@163.com2011-6-8目 录About this document4Jaro- Winkler Distance41)Introduction42)Definition4a)The Jaro distance算法最后得分公式:4b)Match Window(匹配窗口)计算公式4c)解释上面两组公式5d)Jaro–Winkler distance算法公式53)引用资源5教程版本说明作者0.9总结常用ETL数据匹配算法理论wangheAbout this document数据是组织最具价值的资产之一。企业的数据质量与业务绩效之间存在着直接联系，高质量的数据可以使公司保持竞争力并在经济动荡时期立于不败之地。有了普遍深入的数据质量，企业在任何时候都可以信任满足所有需求的所有数据。然而大多数情况下、我们的数据源来自企业中各个系统、并不是所有的数据都有统一的标准、这样在我们做ETL过程的时候就需要将我们需要的数据清洗出来、而清洗的过程中主要是对数据进行操作、因此采用一个高效的合理的算法必不可少。此文档简单对数据匹配的几种经典进行阐述与分析。以供参考，此文档介绍Jaro–Winkler distance。Jaro- Winkler DistanceIntroductionThe Jaro–Winkler distance (Winkler, 1990)是计算2个字符串之间相似度的一种算法。它是Jaro distance算法的变种。主要用于record linkage/数据连接（duplicate detection/重复记录）方面的领域，Jaro–Winkler distance最后得分越高说明相似度越大。Jaro–Winkler distance 是适合于串比如名字这样较短的字符之间计算相似度。0分表示没有任何相似度，1分则代表完全匹配。DefinitionThe Jaro distance算法最后得分公式:; //公式一其中: s1、s2 是要比对的两个字符是最后得分m是匹配的字符数t 是换位的数目Match Window(匹配窗口)计算公式 ; //公式二其中:s1、s2 是要比对的两个字符MW是匹配窗口值解释上面两组公式1.字符串s1与字符串s2在做匹配计算时，当两个字符的距离不大于公式二的最后结果(匹配窗口)即认为是匹配的。2.当s1、s2中字符相匹配但是字符位置不一样时发生换位操作、而公式一中换位的数目t为不同顺序的匹配字符的数目的一半。比如:两个字符串CRATE和TRACE做匹配操作，字符串中仅有R A E三个字符是匹配的，即m=3。为什么C, T不算做是匹配的呢。因为虽然C, T都出现在两个字符串中，但是通过公式二得出匹配窗口值为 (5/2)-1=1.5。而两个字符串中C, T字符的距离均大于1.5。所以不算做匹配。因此t=0。在另一组字符串DwAyNE 与 DuANE 。匹配的字符D-A-N-E 在两个字符串中有相同的字符顺序，所以不需要进行换位操作，因此t=0,m=4。Jaro–Winkler distance算法公式 Jaro-Winkler算法给予了起始部分就相同的字符串更高的分数，它定义了一个前缀范围p，对于要匹配的两个字符串，如果前缀部分有长度为L的部分字符串相同，则Jaro-Winkler Distance为: ; //公式三其中:是Jaro distance最后得分L是前缀部分匹配的长度P是一个范围因子常量，用来调整前缀匹配的权值，但是P的值不能超过0.25，因为这样最后得分可能超过1分.Winkler的标准默认设置值P=0.1。Although often referred to as a distance metric, the Jaro–Winkler distance is actually not a /wiki/Metric_%28mathematics%29metric in the mathematical sense of that term.Example例子1给出两个字符串 s1 MARTHA 和 s2 MARHTA、我们可以得出：m = 6| s1 | = 6| s2 | = 6两组字符T/H和H/T要进行换位操作，因此t=2/2=1; 我们可以根据公式一得出Jaro得分：如果使用Jaro–Winkler，并且取范围因子P=0.1,我们会得出:P=0.1L=3假使串 s1 DWAY