（2） 在匹配窗口范围为7之内比较，即 中每个字符在对应 左右7个之内比较， 中字符在 中第一次出现，则在数组 中记录下 中出现的字符的索引值（见表3-2）。
表3-2
s1 N a n k i n g
matchesIndex 0 1 2 -1 4 5 6
s2 N a n j i n g u n v e r s i t y
Index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
（3） 中值不为-1的即是公共字符，容易得到公共字符数 。
3、 算出匹配字符序列中公共字符不同顺序的数目 ，其得到交换次数为 。如：
（1）分别将公共字符相对于字符串 与 放入对应的数组ms1[]={‘N’,’a’,’n’,’i’,’n’,’g’}，ms2[]={‘N’,’a’,’n’,’i’,’n’,’g’}中。
（2）数组ms1[]与ms2[]对应索引一一比较，字符不同即 加1，本例不同顺序数目 为0，则交换次数也为0。
4、 以上算出的 ， ， ， 通过公式2.2，计算出两个字符串的相似度 。
Jaro算法
输入：两个带判定的字符串s，t；
输出：Jaro distance；
原文请找腾讯752018766辣'文.论,文.网http://www.751com.cn 换次数
//***********************
String max,min;
//分别找出长度最大字符串和最小字符串
if(s1.length()>s2.length()){
max=s1;
min=s2;
}else{
max=s2;
min=s1;
}
//step1: 匹配窗口范围
int matchRange = Math.max(max.length() / 2 - 1, 0);
/*给定可能匹配的最大数组，初始化其值为-1；*/
initMatchindex(){方法体，初始化数组和标识}
/*step2: 在匹配范围的窗口内比较，算出匹配的字符数matches*/
getMatches(){方法体，返回匹配的字符数matches值}
/*找出匹配的字符序列ms1，ms2，以数组存放*/
getEachMatches(int matches){ 方法体，返回与对应字符串匹配的公共字符数组ms1[]，ms2[]}
/*step3: 算出匹配字符序列顺序不同的个数transpositions*/
getTranspositions(){方法体，返回return new int[] { matches， transpositions / 2}}
//***************************************
// step4:计算Jaro distance，公式计算相似度
//****************************************
public float getDistance(String s1, String s2) {方法体;用公式2.2返回Jaro distance}
3.2 Jaro-winkler算法
Jaro-Winkler的设计最适用于短字符串，被研究出来的的Jaro-Winkler距离方法用在美国的人口统计中，它被设计用来把姓和姓，名和名比较，而不是把整个姓名进行比较。Jaro算法考虑的是相同字符的顺序位置和个数，而Jaro-winkler目的就是通过前缀长度来客观提高jaro算法结果的相似程度
在实际应用中，大量的词以复合词的形式出现，如s1 = where is the book， s2 = where is the chassroom，其公共字符所占比例较高，但其语义不同，判断误差比较大。两个记录的前缀有很多相同的字符，但我们不希望相同的前缀把后面不相同的那部分覆盖掉，所以要对前缀占的比重进行一个限制。相同前缀取值最多取4，如果取值大于4的话，后面的字符串不一致，而前面很长的字符串一致的话，就会导致误判。
William Winkler在Jaro 算法的基础上对其作了修正，给定一个标准，在给定的标准内相似度仍按Jaro distance计算，超过给定的标准的考虑记录的相同前缀并作修正。
3.2.1 Jaro-winkler原理
通过对Jaro distance修正计算Jaro-winkler distance[7]来判断两记录是否为同一实体的不同表述。
Jaro distance大于给定的最低标准（Winkler给定标准值为0.7）时，Jaro-Winkler给两个记录 和 定义了一个修正值p，如果前缀相同的部分长度为 ，则Jaro-winkler distance为：
(公式2.3)
是两个字符串的Jaro distance ， 是前缀相同字符的长度，但是规定最大为4 （当 时取 ，当 >4时取 ）， 则是根据前缀长度而调整的常数，规定不能超过0.25，不然可能出现 大于1的情况，在Winkler著作中这个常数的标准值是
上一页 [1] [2] [3] [4] [5] [6] 下一页