每日算法 — 使用java实现编辑距离：Levenshtein动态规划与字符串相似度

问题描述

编辑距离（Edit Distance），又称Levenshtein距离，是指将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数。允许的编辑操作包括：

插入：在字符串中插入一个字符
删除：删除字符串中的一个字符
替换：将字符串中的一个字符替换为另一个字符

例如：将 “kitten” 转换为 “sitting” 的编辑距离为3：
– kitten → sitten（替换k为s）
– sitten → sittin（替换e为i）
– sittin → sitting（插入g）

最优子结构

设dp[i][j]表示word1的前i个字符转换为word2的前j个字符所需的最少操作次数。

状态转移方程：
– 如果word1[i-1] == word2[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
– dp[i-1][j] + 1：删除word1[i-1]
– dp[i][j-1] + 1：在word1中插入word2[j-1]
– dp[i-1][j-1] + 1：替换word1[i-1]为word2[j-1]

Java完整实现

import java.util.*;

/**
 * 编辑距离（Levenshtein Distance）完整Java实现
 * 包含标准DP、空间优化、编辑路径回溯、加权编辑距离
 */
public class EditDistance {

    /**
     * 标准动态规划求解编辑距离
     * 时间复杂度：O(m*n)，空间复杂度：O(m*n)
     */
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j]表示word1[0..i-1]转换为word2[0..j-1]的最小操作数
        int[][] dp = new int[m + 1][n + 1];

        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // word1前i个字符转换为空串需要i次删除
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // 空串转换为word2前j个字符需要j次插入
        }

        // 填充DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 字符相同，无需操作
                } else {
                    int deleteCost = dp[i - 1][j] + 1;      // 删除
                    int insertCost = dp[i][j - 1] + 1;      // 插入
                    int replaceCost = dp[i - 1][j - 1] + 1; // 替换
                    dp[i][j] = Math.min(Math.min(deleteCost, insertCost), replaceCost);
                }
            }
        }

        return dp[m][n];
    }

    /**
     * 空间优化版本：仅使用两行
     * 时间复杂度：O(m*n)，空间复杂度：O(min(m,n))
     */
    public static int minDistanceOptimized(String word1, String word2) {
        if (word1.length() < word2.length()) {
            String temp = word1;
            word1 = word2;
            word2 = temp;
        }

        int m = word1.length();
        int n = word2.length();
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        for (int j = 0; j <= n; j++) {
            prev[j] = j;
        }

        for (int i = 1; i <= m; i++) {
            curr[0] = i;
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    curr[j] = prev[j - 1];
                } else {
                    curr[j] = Math.min(Math.min(prev[j] + 1, curr[j - 1] + 1), prev[j - 1] + 1);
                }
            }
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }

        return prev[n];
    }

    /**
     * 回溯编辑路径，输出具体操作序列
     */
    public static List<String> getEditPath(String word1, String word2) {
        int m = word1.length();
        int n = word2.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 (word1.charAt(i - 1) == word2.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;
                }
            }
        }

        List<String> path = new ArrayList<>();
        int i = m, j = n;

        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && word1.charAt(i - 1) == word2.charAt(j - 1)) {
                path.add("KEEP '" + word1.charAt(i - 1) + "'");
                i--;
                j--;
            } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
                path.add("REPLACE '" + word1.charAt(i - 1) + "' with '" + word2.charAt(j - 1) + "'");
                i--;
                j--;
            } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
                path.add("DELETE '" + word1.charAt(i - 1) + "'");
                i--;
            } else {
                path.add("INSERT '" + word2.charAt(j - 1) + "'");
                j--;
            }
        }

        Collections.reverse(path);
        return path;
    }

    /**
     * 加权编辑距离：不同操作有不同的代价
     */
    public static int weightedEditDistance(String word1, String word2,
                                           int insertCost, int deleteCost, int replaceCost) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i * deleteCost;
        for (int j = 0; j <= n; j++) dp[0][j] = j * insertCost;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(
                        dp[i - 1][j] + deleteCost,
                        dp[i][j - 1] + insertCost),
                        dp[i - 1][j - 1] + replaceCost);
                }
            }
        }

        return dp[m][n];
    }

    /**
     * 计算相似度（0到1之间，1表示完全相同）
     */
    public static double similarity(String word1, String word2) {
        int maxLen = Math.max(word1.length(), word2.length());
        if (maxLen == 0) return 1.0;
        int distance = minDistance(word1, word2);
        return 1.0 - (double) distance / maxLen;
    }

    /**
     * 打印DP表
     */
    public static void printDPTable(String word1, String word2) {
        int m = word1.length();
        int n = word2.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 (word1.charAt(i - 1) == word2.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;
                }
            }
        }

        System.out.print("      ");
        for (int j = 0; j < n; j++) System.out.print(word2.charAt(j) + " ");
        System.out.println();
        for (int i = 0; i <= m; i++) {
            if (i > 0) System.out.print(word1.charAt(i - 1) + " ");
            else System.out.print("  ");
            for (int j = 0; j <= n; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        String word1 = "kitten";
        String word2 = "sitting";

        System.out.println("字符串1: " + word1);
        System.out.println("字符串2: " + word2);
        System.out.println();

        System.out.println("DP表：");
        printDPTable(word1, word2);
        System.out.println();

        System.out.println("编辑距离：" + minDistance(word1, word2));
        System.out.println("空间优化版本：" + minDistanceOptimized(word1, word2));
        System.out.println("相似度：" + String.format("%.2f%%", similarity(word1, word2) * 100));
        System.out.println();

        System.out.println("编辑路径：");
        List<String> path = getEditPath(word1, word2);
        for (String step : path) {
            System.out.println("  " + step);
        }

        System.out.println("
加权编辑距离（插入=1, 删除=2, 替换=3）：" + 
            weightedEditDistance(word1, word2, 1, 2, 3));
    }
}

DP表示例

以word1=”horse”, word2=”ros”为例：

      r o s
    0 1 2 3
h   1 1 2 3
o   2 2 1 2
r   3 2 2 2
s   4 3 3 2
e   5 4 4 3

编辑距离为3：horse→rorse→rose→ros（或horse→rorse→rorse→ros等）

复杂度分析

版本	时间复杂度	空间复杂度
标准DP	O(m×n)	O(m×n)
空间优化	O(m×n)	O(min(m,n))
加权版本	O(m×n)	O(m×n)

应用场景

拼写纠错：搜索引擎和输入法自动纠正错别字
DNA序列比对：计算基因序列的差异程度
语音识别：匹配语音转文本与实际词汇
抄袭检测：衡量文本相似度
机器翻译：评估翻译质量（BLEU分数的基础）

扩展思考

Damerau-Levenshtein距离：增加交换相邻字符的操作
Jaro-Winkler距离：对前缀匹配给予更高权重
最长公共子序列与编辑距离的关系：对于仅允许插入和删除的情况，编辑距离 = m + n – 2*LCS长度

总结

编辑距离是衡量字符串相似度的基础算法，其动态规划解法优雅高效。理解编辑距离有助于掌握更复杂的序列比对算法，也是自然语言处理和生物信息学的重要基础。

Tagged with: Java Levenshtein距离动态规划字符串算法编辑距离