Java⽐较两个字符串的相似度算法（LevenshteinDistance）转载⾃： blog.csdn/JavaReact/article/details/82144732
算法简介：
Levenshtein Distance，⼜称编辑距离，指的是两个字符串之间，由⼀个转换成另⼀个所需的最少编辑操作次数。
许可的编辑操作包括将⼀个字符替换成另⼀个字符，插⼊⼀个字符，删除⼀个字符。
编辑距离的算法是⾸先由科学家Levenshtein提出的，故⼜叫Levenshtein Distance。
1.
/**
2.
* ⽐较两个字符串的相识度
3.
* 核⼼算法：⽤⼀个⼆维数组记录每个字符串是否相同，如果相同记为0，不相同记为1，每⾏每列相同个数累加
4.
* 则数组最后⼀个数为不相同的总数，从⽽判断这两个字符的相识度
5.
*
6.
* @param str
7.
* @param target
8.
* @return
9.
*/
10.
private static int compare(String str, String target) {
11.
int d[][]; // 矩阵
12.
int n = str.length();
13.
int m = target.length();
14.
int i; // 遍历str的
15.
int j; // 遍历target的
16.
char ch1; // str的
17.
char ; // target的
18.
int temp; // 记录相同字符，在某个矩阵位置值的增量，不是0就是1
19.
if (n == 0) {
20.
return m;
21.
}
22.
if (m == 0) {
23.
return n;
24.
d = new int[n + 1][m + 1];
26.
// 初始化第⼀列
27.
for (i = 0; i <= n; i++) {
28.
d[i][0] = i;
29.
}
30.
/
/ 初始化第⼀⾏
31.
for (j = 0; j <= m; j++) {
32.
d[0][j] = j;
33.
}
34.
for (i = 1; i <= n; i++) {
35.
// 遍历str
36.
ch1 = str.charAt(i - 1);
37.
// 去匹配target
38.
for (j = 1; j <= m; j++) {
39.
ch2 = target.charAt(j - 1);
40.
if (ch1 == ch2 || ch1 == ch2 + 32 || ch1 + 32 == ch2) { 41.
temp = 0;
42.
} else {
43.
temp = 1;
44.
}
45.
// 左边+1，上边+1, 左上⾓+temp取最⼩
46.
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
47.
}
48.
}
49.
return d[n][m];
50.
}
51.
52.
53.
/**
54.
* 获取最⼩的值
55.
*/
56.
private static int min(int one, int two, int three) {
57.
return (one = one < two ? one : two) < three ? one : three;
58.
60.
/**
61.
* 获取两字符串的相似度
62.
*/
63.
public static float getSimilarityRatio(String str, String target) {
64.
int max = Math.max(str.length(), target.length());
65.
return 1 - (float) compare(str, target) / max;
字符串长度比较66.
}
1.
public static void main(String[] args) {
2.
String a= "Steel";
3.
String b = "Steel Pipe";
4.
System.out.println("相似度："+getSimilarityRatio(a,b));
5.
}
算法原理：
该算法的解决是基于动态规划的思想，具体如下：
设 s 的长度为 n，t 的长度为 m。如果 n = 0，则返回 m 并退出；如果 m=0，则返回 n 并退出。否则构建⼀个数组 , 0..n]。将第0⾏初始化为 0..n，第0列初始化为0..m。
依次检查 s 的每个字母()。
依次检查 t 的每个字母()。
如果 s[i]=t[j]，则 cost=0；如果 s[i]!=t[j]，则 cost=1。将 d[i,j] 设置为以下三个值中的最⼩值：
紧邻当前格上⽅的格的值加⼀，即 d[,j]+1
紧邻当前格左⽅的格的值加⼀，即 d[i,j-1]+1
当前格左上⽅的格的值加cost，即 d[i-1,j-1]+cost
重复3-6步直到循环结束。d[n,m]即为莱茵斯坦距离。
参考链接：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。