java实现编辑距离算法,计算字符串或者是文本之间的相似度
时间: 2024-03-19 22:45:50 浏览: 12
Java实现编辑距离算法,可以使用动态规划的思想,具体步骤如下:
1. 定义二维数组dp[i][j],表示将字符串s1的前i个字符转换为字符串s2的前j个字符所需的最少操作数。
2. 初始化dp数组:dp[0][0] = 0,dp[i][0] = i,dp[0][j] = j。
3. 逐个字符比较s1和s2,若s1[i]等于s2[j],则dp[i][j] = dp[i-1][j-1],否则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
4. 最终的编辑距离为dp[s1.length()][s2.length()]。
下面是Java代码实现:
```java
public class EditDistance {
public static int getEditDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
}
}
return dp[m][n];
}
public static double getSimilarity(String s1, String s2) {
int distance = getEditDistance(s1, s2);
return 1.0 - (double)distance / Math.max(s1.length(), s2.length());
}
public static void main(String[] args) {
String s1 = "hello world";
String s2 = "helo wold";
System.out.println("编辑距离为:" + getEditDistance(s1, s2));
System.out.println("相似度为:" + getSimilarity(s1, s2));
}
}
```
其中,getEditDistance方法计算编辑距离,getSimilarity方法计算相似度,main方法是测试代码。