利用编辑距离(Edit Distance)计算两个字符串的相似度
- - Java - 编程语言 - ITeye博客利用编辑距离(Edit Distance)计算两个字符串的相似度. 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数. 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符. 一般来说,编辑距离越小,两个串的相似度越大.
利用编辑距离(Edit Distance)计算两个字符串的相似度
编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。
例如将kitten一字转成sitting:
sitten (k→s)
sittin (e→i)
sitting (→g)
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
之前用jsoup做网络爬虫的时候用到了这个 来计算两个字符串的相似度,今天整理出来向Vladimir Levenshtein致敬。
/** * 编辑距离(Edit Distance)求字符串相似度 * @author InJavaWeTrust http://injavawetrust.iteye.com * */ public class EditDistance { /** * 求三个数中最小的一个 * @param one * @param two * @param three * @return */ public int min(int one, int two, int three) { int min = one; if (two < min) { min = two; } if (three < min) { min = three; } return min; } /** * 求编辑距离(Edit Distance) * @param str1 * @param str2 * @return 编辑距离 */ public int editDistance(String str1, String str2) { int d[][]; // 矩阵 int y = str1.length(); int x = str2.length(); char ch1; // str1的 char ch2; // str2的 int temp; // 记录相同字符,在某个矩阵位置值的增量,不是0就是1 if (y == 0) { return x; } if (x == 0) { return y; } d = new int[y + 1][x + 1]; // 计算编辑距离二维数组 for (int j = 0; j <= x; j++) { // 初始化编辑距离二维数组第一行 d[0][j] = j; } for (int i = 0; i <= y; i++) { // 初始化编辑距离二维数组第一列 d[i][0] = i; } for (int i = 1; i <= y; i++) { // 遍历str1 ch1 = str1.charAt(i - 1); // 去匹配str2 for (int j = 1; j <= x; j++) { ch2 = str2.charAt(j - 1); if (ch1 == ch2) { temp = 0; } else { temp = 1; } // 左边+1,上边+1, 左上角+temp取最小 d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp); } } return d[y][x]; } /** * 计算相似度 * @param str1 * @param str2 * @return */ public double similar(String str1, String str2) { int ed = editDistance(str1, str2); return 1 - (double) ed / Math.max(str1.length(), str2.length()); } public static void main(String[] args) { String str1 = "1234"; String str2 = "1254"; System.out.println("字符串相似度: " + new EditDistance().similar(str1, str2)); } }
运行结果: