Levenshtein距离计算详解 | Baeldung中文网

1. 引言

本文介绍Levenshtein距离（又称编辑距离），该算法由俄罗斯科学家Vladimir Levenshtein于1965年提出。我们将提供该算法的递归和迭代Java实现。

2. 什么是Levenshtein距离？

Levenshtein距离衡量两个字符串之间的差异程度。数学上，给定字符串x和y，该距离表示将x转换为y所需的最少字符编辑次数。允许的编辑操作包括：

✅ 插入：添加字符c
✅ 删除：移除字符c
✅ 替换：将字符c替换为c'

示例：若x = "shot"，y = "spot"，编辑距离为1（只需将'h'替换为'p'）。

某些场景下，不同编辑操作的成本可能不同（例如键盘邻近字符替换成本更低），但本文为简化讨论，默认所有操作成本均为1。

典型应用场景：

拼写检查器：检测拼写错误并推荐词典中最接近的正确拼写
抄袭检测（参考IEEE论文）
DNA分析：计算基因序列相似度
语音识别（参考微软研究）

3. 算法原理

设字符串x（长度m）和y（长度n），分别表示为x[1:m]和y[1:n]。最终转换后两字符串长度相等且字符完全匹配。针对首字符，有三种操作选择：

替换操作：
- 计算将x[1]替换为y[1]的成本（D1）：字符相同则成本为0，否则为1
- 首字符匹配后，总成本 = D1 + 转换剩余部分x[2:m]→y[2:n]的成本
插入操作：
- 在x中插入字符匹配y[1]，成本固定为1
- 总成本 = 1 + 转换x[1:m]→y[2:n]的成本
删除操作：
- 删除x的首字符，成本固定为1
- 总成本 = 1 + 转换x[2:m]→y[1:n]的成本

由于无法预知哪种选择最终成本最低，必须穷举所有可能并选择最优解。

4. 朴素递归实现

观察发现：第3节中每个操作的第二步本质是子字符串的编辑距离问题。这种特性天然适合递归求解，递推关系可定义为：

D(x[1:m], y[1:n]) = min {
    D(x[2:m], y[2:n]) + 替换x[1]→y[1]的成本,
    D(x[1:m], y[2:n]) + 1,
    D(x[2:m], y[1:n]) + 1
}

边界条件：

两字符串均为空 → 距离为0
仅一字符串为空 → 距离为另一字符串长度（需插入/删除所有字符）

示例：x="dog"，y="" → 距离为3（需3次插入或删除）

public class EditDistanceRecursive {

   static int calculate(String x, String y) {
        if (x.isEmpty()) {
            return y.length();
        }

        if (y.isEmpty()) {
            return x.length();
        } 

        int substitution = calculate(x.substring(1), y.substring(1)) 
         + costOfSubstitution(x.charAt(0), y.charAt(0));
        int insertion = calculate(x, y.substring(1)) + 1;
        int deletion = calculate(x.substring(1), y) + 1;

        return min(substitution, insertion, deletion);
    }

    public static int costOfSubstitution(char a, char b) {
        return a == b ? 0 : 1;
    }

    public static int min(int... numbers) {
        return Arrays.stream(numbers)
          .min().orElse(Integer.MAX_VALUE);
    }
}

⚠️ 复杂度陷阱：该实现复杂度达O(3^n)，每步递归产生三个分支，性能极差。下节将优化。

5. 动态规划优化

分析递归调用发现：子问题参数始终是原字符串的后缀，因此唯一子问题数最多为m×n个（m和n为字符串长度）。最优解复杂度应为**O(m×n)**。

观察子问题重叠性：

D(x[1:m], y[1:n]) 的子问题：
  → D(x[2:m], y[2:n])
  → D(x[1:m], y[2:n])
  → D(x[2:m], y[1:n])

D(x[1:m], y[2:n]) 的子问题：
  → D(x[2:m], y[3:n])
  → D(x[1:m], y[3:n])
  → D(x[2:m], y[2:n])  // 与上重复！

D(x[2:m], y[1:n]) 的子问题：
  → D(x[3:m], y[2:n])
  → D(x[2:m], y[2:n])  // 再次重复！
  → D(x[3:m], y[1:n])

关键发现：子问题D(x[2:m], y[2:n])被重复计算三次！这符合动态规划的两大特征：

重叠子问题（Overlapping Sub-Problems）
最优子结构（Optimal Substructure）

优化方案：使用记忆化存储（Memoization）缓存子问题结果，或采用表格法迭代求解：

static int calculate(String x, String y) {
    int[][] dp = new int[x.length() + 1][y.length() + 1];

    for (int i = 0; i <= x.length(); i++) {
        for (int j = 0; j <= y.length(); j++) {
            if (i == 0) {
                dp[i][j] = j;
            }
            else if (j == 0) {
                dp[i][j] = i;
            }
            else {
                dp[i][j] = min(dp[i - 1][j - 1] 
                 + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), 
                  dp[i - 1][j] + 1, 
                  dp[i][j - 1] + 1);
            }
        }
    }

    return dp[x.length()][y.length()];
}

✅ 性能提升：复杂度降至O(m×n)，但内存消耗较大（需存储m×n的表格）。

进一步优化：注意到当前单元格值仅依赖三个相邻单元格（左、上、左上），可将空间复杂度优化至O(min(m,n))。

6. 总结

本文介绍了Levenshtein距离的概念及两种实现方式（递归与动态规划）。该算法是字符串相似度度量的基础方案，其他常用度量包括：

余弦相似度（基于向量的token方法）
Dice系数等

完整实现代码可在GitHub仓库获取。

Persistence

REST