匹配算法Jaro–Winkler distance简介教案.docx

常用数据匹配算法简介系类--Jaro–Winkler distance 算法数据是组织最具价值的资产之一。企业的数据质量与业务绩效之间存在着直接联系，高质量的数据可以使公司保持竞争力并在经济动荡时期立于不败之地。本文介绍在数据匹配算法 Jaro–Winkler distancewanghetommy@163.com2011-6-8  目 录  TOC \o 1-3 \h \z \u  HYPERLINK \l _Toc295291475 About this document  PAGEREF _Toc295291475 \h 4  HYPERLINK \l _Toc295291476 Jaro- Winkler Distance  PAGEREF _Toc295291476 \h 4  HYPERLINK \l _Toc295291477 1) Introduction  PAGEREF _Toc295291477 \h 4  HYPERLINK \l _Toc295291478 2) Definition  PAGEREF _Toc295291478 \h 4  HYPERLINK \l _Toc295291479 a) The Jaro distance算法最后得分公式:  PAGEREF _Toc295291479 \h 4  HYPERLINK \l _Toc295291480 b) Match Window(匹配窗口)计算公式  PAGEREF _Toc295291480 \h 4  HYPERLINK \l _Toc295291481 c) 解释上面两组公式  PAGEREF _Toc295291481 \h 5  HYPERLINK \l _Toc295291482 d) Jaro–Winkler distance算法公式  PAGEREF _Toc295291482 \h 5  HYPERLINK \l _Toc295291483 3) 引用资源  PAGEREF _Toc295291483 \h 5  教程版本说明作者0.9总结常用ETL数据匹配算法理论wanghe About this document 数据是组织最具价值的资产之一。企业的数据质量与业务绩效之间存在着直接联系，高质量的数据可以使公司保持竞争力并在经济动荡时期立于不败之地。有了普遍深入的数据质量，企业在任何时候都可以信任满足所有需求的所有数据。然而大多数情况下、我们的数据源来自企业中各个系统、并不是所有的数据都有统一的标准、这样在我们做ETL过程的时候就需要将我们需要的数???清洗出来、而清洗的过程中主要是对数据进行操作、因此采用一个高效的合理的算法必不可少。此文档简单对数据匹配的几种经典进行阐述与分析。以供参考，此文档介绍Jaro–Winkler distance。 Jaro- Winkler Distance Introduction The Jaro–Winkler distance (Winkler, 1990)是计算2个字符串之间相似度的一种算法。它是Jaro distance算法的变种。主要用于record linkage/数据连接（duplicate detection/重复记录）方面的领域，Jaro–Winkler distance最后得分越高说明相似度越大。Jaro–Winkler distance 是适合于串比如名字这样较短的字符之间计算相似度。0分表示没有任何相似度，1分则代表完全匹配。 Definition The Jaro distance算法最后得分公式: dj= 13ms1+ms1+m-tm ; //公式一 其中: s1、s2 是要比对的两个字符 dj是最后得分 m是匹配的字符数 t 是换位的数目 Match Window(匹配窗口)计算公式 MW= Max(s1,|s2|)2-1 ; //公式二 其中: s1、s2 是要比对的两个字符 MW是匹配窗口值 解释上面两组公式 1.字符串s1与字符串s2在做匹配计算时，当两个字符的距离不大于公式二的最后结果(匹配窗口)即认为是匹配的。 2.当s1、s2中字符相匹配但是字符位置不一样时发生换位操作、而公式一中换位的数目t为不同顺序的匹配字符的数目的一半。比如:两个字符串CRATE和TRACE做匹配操作，字符串中仅有R A E三个字符是匹配的，即m=3。为什么C, T不算做是匹配的呢。因为虽然C, T都出现在两个字符串中，但是通过公式二得出匹配