字符编辑的字符串匹配算法的实现+编辑距离算法+JARO算法
通过 来求得 的值。
2.3.2 Levenshtein算法实现
输入：两个待判定的字符串s，t；
输出: Levenshtein distance；
class Levenshtein｛
//*************************
//计算 Levenshtein distance
//*************************
int distance(String s, String t){
int cost; // cost
// Step 1 开辟（n+1）* (m+1)矩阵空间
原文请找腾讯752018766辣'文.论,文.网
http://www.751com.cn return m;
if (m == 0)
return n;
d = new int[n+1][m+1];
// Step 2 第i行 第j列。只要删除i个字符，s[1..i]便可以变成空字符串t[1..0],则d[i][0] = i;同样,只要插入j个字符，s[1..0]便可以变成t[1..j],则d[0][j] = j.
for (i = 0; i <= n; i++)
d[i][0] = i;
for (j = 0; j <= m; j++)
d[0][j] = j;
// Step 3 n重循环，前i行的字符
for (i = 1; i <= n; i++){
s_i = s.charAt (i - 1);
// Step 4 m重循环，前j列的字符
for (j = 1; j <= m; j++){
t_j = t.charAt(j - 1);
// Step 5 前i行的字符与前j列的字符比较，字符相同标记为0，不同记为1
if (s_i == t_j)｛
cost = 0;
｝else｛
cost = 1;
｝// Step 6 每一步取前i行与前j列矩阵上取（删除 插入 替换）最小值
d[i][j] = minimum(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
// Step 7 n,m重循环后求和，得到编辑距离，复杂度为O(mn)。
return d[n][m];
}
2.4 正确性说明
我们可以用最少d[i][j]步操作，将起始段s[1..i]变为t[1..j]，这总是成立的，通过以下几点说明：
（1）它在0列0行就是正确的，因为只要删除i个字符，s[1..i]便可以变成空字符串t[1..0]。同样，只要插入j个字符，s[1..0]便可以变成t[1..j]。
（2）得出了3个距离上的最小值，每一个都是合理的：
如果我们能在k步内将s[1..i] 变为 t[1..j-1]，那么我们就可以在k+1步内通过插入t[j]来得到t[1..j]。
如果我们能在k步内将s[1..i-1] 变为 t[1..j]，那么我们也能对s[1..i]进行同样的操作，然后在k+1步内将原有的s[i]去除。
如果我们能在k步内将 s[1..i-1] 变为t[1..j-1]，那么我们也能对s[1..i]进行同样的操作，最终用t[j]代替原有的s[i]，这需要k+cost步操作。
（3）当然，要将s[1..n] 变为 t[1..m]所需要的操作数与将所有s变为所有t所需的操作数是一样的。因此我们的结果d[m][n]是成立的。原文请找腾讯752018766辣'文.论,文.网http://www.751com.cn以上的证明不能证明d[i][j]是最小的，这一点可以用反证法，假设d[i][j]比以上提出的3个最小值还要小，并以此证明以上的3个并不是最小的。
2.5 Levenshtein算法补充说明
实际上只考虑编辑距离 的大小，对于我们上面提到的拼写错误只判断出它们形体的相似的程度，在语义上是无法准确判断，而我们所需要的相似最好是语义上的。因此，也可以使用相似度 ( 为编辑距离， 为字符串的长度)这个概念来将问题规约到一定范围的数据集中，计算出两个字符串为同一实体相似匹配的程度，提高正确率的判定，之后可对字符串使用其他算法做进一步处理，这里暂不考虑。
第三章 Jaro-Winkler距离(Jaro-Winkler Distance)
3.1 Jaro算法
与Levenshtein算法一样从两方面考虑。若某条记录发生排版错误，则误记录s与原记录t之间必有很高比例的公共字符。
另一方面，若一记录R为误记录，则原记录R0中每个字符在R中的位置应当离它本该在的位置不远。如记录“Nanjing University，Hankou Road”，对于字母”j”在错误记录中，可能由于漏写、多写、误写使”j”没有出现在记录的第4个位置，却极有可能在第2~6的字符位置上，却不太可能出现在第7位以后的位置，倘若出现在较远的位置，则在某种程度上从另一方面说明这两条记录本就不是同一条记录的表述，当然也会有”j”是被误写的情况，暂不考虑。基于此便可使用Jaro distance来衡量两个记录的相似度。
3.1.1 Jaro算法原理
通过计算Jaro distance来判断两记录是否为同一实体的不同表述。Jaro算法是先输入两个字符串 和 ，通过比较字符串，抽出公共字符，得到这些字符序列长度 。在匹配范围的窗口之内，字符串 中的每一个字符与字符串 中第一次出现的字符匹配（未作调整）。匹配范围窗口大小规定为：
（公式2.1）
在公共字符序列中，调整两两不同字符的顺序，计算出交换次数 ，简而言之就是不同顺序的匹配字符的数目的一半即为换位的数目 。
两个字符串 和 的Jaro距离为 。
（公式2.2）
是匹配的字符数， 是字符 的长度， 是字符 的长度， 为交换的次数。
测量值是三个数的平均数（1）第一个字符串匹配百分比，（2）第二个字符串匹配百分比，和（3）未调换的匹配百分比。两个字符串的Jaro距离为 越大，那么两个字符串就越相似，0相当于没有相似度，1是准确匹配。上一页 [1] [2] [3] [4] [5] [6] 下一页
java字符编辑的字符串匹配算法的实现+编辑距离算法+JARO算法 第3页下载如图片无法显示或论文不完整，请联系qq752018766
