Java编辑距离算法详解（从零实现Levenshtein距离计算）

为什么需要编辑距离？

编辑距离广泛应用于：

• 拼写纠错（如输入“helo”自动提示“hello”）
• 生物信息学中的基因序列比对
• 抄袭检测系统
• 模糊搜索与推荐系统

掌握字符串相似度计算的核心思想，是进阶NLP和数据处理的重要一步。

算法原理：动态规划

编辑距离通常使用动态规划算法高效求解。我们构建一个二维数组 dp[i][j]，表示将字符串 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最小操作数。

状态转移方程如下：

• 如果 str1[i-1] == str2[j-1]，则 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

Java代码实现

下面是一个完整的、易于理解的Java实现：

public class EditDistance {    public static int calculateEditDistance(String str1, String str2) {        int m = str1.length();        int n = str2.length();                // 创建 (m+1) x (n+1) 的DP表        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; // 插入所有字符        }                // 填充DP表        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1];                } else {                    dp[i][j] = Math.min(                        Math.min(dp[i - 1][j],     // 删除                                 dp[i][j - 1]),   // 插入                        dp[i - 1][j - 1]           // 替换                    ) + 1;                }            }        }                return dp[m][n];    }        // 测试示例    public static void main(String[] args) {        String word1 = "kitten";        String word2 = "sitting";        int distance = calculateEditDistance(word1, word2);        System.out.println("编辑距离: " + distance); // 输出: 3    }}

代码解析

1. 初始化：第一行和第一列表示空字符串到目标字符串的操作数（全插入或全删除）。

2. 状态转移：逐个比较字符，若相同则继承左上角值；若不同，则取上、左、左上三个方向的最小值加1。

3. 结果：右下角 dp[m][n] 即为最终的编辑距离。

优化建议

上述实现空间复杂度为 O(mn)。若只需距离值（不要具体操作路径），可优化为 O(min(m, n)) 空间，仅保留当前行和上一行数据。

总结

通过本教程，你已经掌握了Java编辑距离算法的核心思想与实现方法。这项技术是字符串相似度计算的基础，也是理解更复杂动态规划算法的良好起点。动手试试修改代码，计算不同单词之间的距离吧！

记住，无论是做拼写检查还是生物序列分析，Levenshtein距离实现都是你工具箱中不可或缺的利器。