编辑距离算法其实就是,在规定的编辑操作(替换字符串、插入字符串、删除字符串)中,经过几步可以把一个字符串变成另一个字符串,而这个所需的步数就是你的编辑距离。
测试样例:
str1 = abc
str2 = yabd
表里的每一个值都代表着将str1转换成str2所需要的步数,每个单元格的值都遵循这样一个规律,第一行和第一列都是从0到n;其他的值要分情况计算,行索引和列索引对比大小,相同的话直接取左上方单元格的值,不同的话对比其左上方、左边、上边,找到三个单元格之中的最小值再加1即这个单元格的值。
str1 a b c
str2
0 1 2 3
y 1 1 2 3
a 2 1 2 3
b 3 2 1 2
d 4 3 3 2
最后一个单元格的值就是两个字符串间不同字符的个数,利用这个数与两个字符串中最长的长度相除就得到了不相似的程度,再用1减去就是相似率。
public class FileCompared { public static void main(String[] args) { String str1 = "ABCDEFGZ"; String str2 = "ABFDFEGXY"; System.out.println("两个字符串的相似率为:" + similarRates(str1,str2) +"%"); } //定义一个similarRates方法获取两个字符串间不同字符的个数并求出两个字符串的相似率 public static int similarRates(String str1 , String str2){ //确定二维距离表distance的维度 int str1Len = str1.length(); int str2Len = str2.length(); //如果一个字符串的内容为空就返回另一个字符串的长度 if (str1Len == 0) return str2Len; if (str2Len == 0) return str1Len; //定义一张二维距离表distance int[][] distance = new int[str1Len + 1][str2Len + 1]; //给二维数组的第一行第一列赋值 int maxLen = str1Len > str2Len ? str1Len : str2Len; for (int num = 0; num < maxLen + 1; num++){ if (num<str1Len + 1) distance[num][0] = num; if (num<str2Len + 1) distance[0][num] = num; } /** * 补全二维数组除第一行第一列的其他值 * 行列索引进行对比,相同的话直接取左上方值,不同的话采用最小距离算法 */ for (int row = 1; row < str1Len+1; row++){ char c1 = str1.charAt(row - 1); for (int col = 1; col < str2Len+1; col++){ char c2 = str2.charAt(col - 1); if (c1 == c2) { distance[row][col] = distance[row - 1][col - 1]; } else { // 最小距离算法就是,取该元素左上方值、左边值、上边值,找到三个之中的最小值再加1即最终距离 distance[row][col] = mostMin(distance[row-1][col], distance[row][col-1], distance[row-1][col-1]) + 1; } } } //二维数组中的最后一个元素即是两个字符串间不同字符的个数 int notSimilarNum = distance[str1Len][str2Len]; //求出相似率 double similarRates = (1- (double)notSimilarNum / maxLen)*100; return (int)similarRates; } //取三个数中的最小值 public static int mostMin(int up, int left, int upLeft){ int min = up < left ? up : left; min = min < upLeft ? min : upLeft; return min; } }
如此便求出了两个字符串的相似率,字符串换成读取文件的话就可以得到两个文件的相似度。