编辑距离（Levenshtein Distance）

字符串相似度的经典度量

算法分类： 字符串算法 / 动态规划

核心思想： 通过动态规划计算将一个字符串转换为另一个字符串所需的最少编辑操作次数

主要内容： 算法定义与原理、动态规划解法、代码实现、路径回溯、空间优化、算法变体、应用场景、加权编辑距离

关键词： 编辑距离, Levenshtein, 字符串相似度, DP, 拼写检查, Damerau-Levenshtein

一、算法概述

编辑距离（Edit Distance），又称 Levenshtein 距离，是由苏联数学家 Vladimir Levenshtein 于 1965 年提出的一个经典字符串度量算法。它定义了将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。

三种基本操作：

插入（Insert）： 在字符串中插入一个字符，代价为1
删除（Delete）： 从字符串中删除一个字符，代价为1
替换（Substitute）： 将一个字符替换为另一个字符，代价为1

例如，将字符串 "kitten" 转换为 "sitting" 的编辑距离为 3：

kitten → sitten（将 'k' 替换为 's'）
sitten → sittin（将 'e' 替换为 'i'）
sittin → sitting（在末尾插入 'g'）

编辑距离广泛应用于拼写检查、DNA/基因序列比对、自然语言处理、抄袭检测和搜索引擎等领域。其核心价值在于提供一个量化指标来衡量两个字符串之间的相似程度——距离越小，相似度越高。

数学定义：

设两个字符串 A 和 B，长度分别为 m 和 n，

编辑距离 ed(A, B) = 将 A 转换为 B 所需的最少编辑操作次数

二、算法原理与动态规划解法

编辑距离的计算核心是动态规划（Dynamic Programming）。我们构建一个 (m+1) x (n+1) 的二维矩阵 dp，其中 dp[i][j] 表示将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最小编辑距离。

递推公式

dp[i][j] = min(

dp[i-1][j] + 1, // 删除 A[i]（等价于插入到 B）

dp[i][j-1] + 1, // 插入 B[j]（等价于从 A 删除）

dp[i-1][j-1] + cost // 替换：如果 A[i] == B[j] 则 cost = 0，否则 cost = 1

)

边界条件

dp[0][j] = j：将空字符串转换为 B 的前 j 个字符，需要 j 次插入操作
dp[i][0] = i：将 A 的前 i 个字符转换为空字符串，需要 i 次删除操作

可视化矩阵

以 "saturday" → "sunday" 为例，其编辑距离矩阵如下（完整计算过程）：

s u n d a y 0 1 2 3 4 5 6 s 1 0 1 2 3 4 5 a 2 1 1 2 3 3 4 t 3 2 2 2 3 4 4 u 4 3 2 3 3 4 5 r 5 4 3 3 4 4 5 d 6 5 4 4 3 4 5 a 7 6 5 5 4 3 4 y 8 7 6 6 5 4 3

右下角 dp[8][6] = 3，即 "saturday" 到 "sunday" 的编辑距离为 3。

算法复杂度：

时间复杂度： O(m x n)，其中 m 和 n 分别为两个字符串的长度
空间复杂度： O(m x n)，使用完整的二维矩阵存储中间结果
在字符串长度相近时，实际运行时间约正比于字符串长度的平方

三、代码实现

Python 实现（基础二维 DP）

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    # 创建 (m+1) x (n+1) 的 DP 矩阵
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化边界条件
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # 填充 DP 矩阵
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,      # 删除
                dp[i][j - 1] + 1,      # 插入
                dp[i - 1][j - 1] + cost  # 替换
            )

    return dp[m][n]


# 测试
print(levenshtein_distance("kitten", "sitting"))   # 输出: 3
print(levenshtein_distance("saturday", "sunday"))  # 输出: 3
print(levenshtein_distance("hello", "world"))     # 输出: 4

JavaScript 实现

function levenshteinDistance(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = Array.from({ length: m + 1 },
        () => Array(n + 1).fill(0));

    // 初始化边界
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            const cost = s1[i - 1] === s2[j - 1] ? 0 : 1;
            dp[i][j] = Math.min(
                dp[i - 1][j] + 1,      // 删除
                dp[i][j - 1] + 1,      // 插入
                dp[i - 1][j - 1] + cost  // 替换
            );
        }
    }
    return dp[m][n];
}

console.log(levenshteinDistance("kitten", "sitting")); // 3
console.log(levenshteinDistance("saturday", "sunday")); // 3

C++ 实现（带注释）

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        // 处理空字符串的边界情况
        if (m == 0) return n;
        if (n == 0) return m;

        // dp[i][j] 表示 word1[0..i-1] 到 word2[0..j-1] 的编辑距离
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        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++) {
                int cost = (word1[i - 1] == word2[j - 1]) ? 0 : 1;
                dp[i][j] = min({
                    dp[i - 1][j] + 1,       // 删除 word1[i-1]
                    dp[i][j - 1] + 1,       // 插入 word2[j-1]
                    dp[i - 1][j - 1] + cost  // 替换
                });
            }
        }
        return dp[m][n];
    }
};

四、路径回溯：输出编辑操作序列

在计算出最小编辑距离之后，我们往往还希望知道具体的编辑操作序列——即到底是通过哪些插入、删除和替换操作完成的转换。这可以通过从 DP 矩阵的右下角回溯到左上角来实现。

回溯的基本规则：从 dp[m][n] 出发，每一步检查当前格子是从哪个方向转移而来的：

如果来自于 dp[i-1][j-1] + cost 且 cost=0，说明字符匹配，无需操作
如果来自于 dp[i-1][j-1] + cost 且 cost=1，说明发生了替换操作
如果来自于 dp[i-1][j] + 1，说明发生了删除操作
如果来自于 dp[i][j-1] + 1，说明发生了插入操作

回溯 Python 实现

def edit_operations(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + cost
            )

    # 回溯 — 从右下角开始
    ops = []
    i, j = m, n
    while i > 0 or j > 0:
        if i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f"删除 '{s1[i-1]}' (位置 {i-1})")
            i -= 1
        elif j > 0 and dp[i][j] == dp[i][j - 1] + 1:
            ops.append(f"插入 '{s2[j-1]}' (位置 {j-1})")
            j -= 1
        else:
            if s1[i - 1] != s2[j - 1]:
                ops.append(f"替换 '{s1[i-1]}' → '{s2[j-1]}' (位置 {i-1})")
            i -= 1
            j -= 1

    ops.reverse()  # 从前往后排列
    return ops


print(edit_operations("kitten", "sitting"))
# 输出: ["替换 'k' → 's' (位置 0)", "替换 'e' → 'i' (位置 4)", "插入 'g' (位置 6)"]

五、空间优化：滚动数组

标准的二维 DP 解法空间复杂度为 O(m x n)，对于长字符串可能消耗大量内存。通过分析递推关系可以发现，dp[i][j] 只依赖于 dp[i-1][j]（上一行同列）、dp[i][j-1]（同一行前一列）和 dp[i-1][j-1]（左上角）三个值。

因此我们可以将空间优化到 O(min(m, n))，使用两个长度为 n+1 的一维数组（甚至一个数组加一个临时变量）即可完成计算。

空间优化思路：

只用两个一维数组：prev 表示上一行，curr 表示当前行
每次迭代时，用 prev[j-1] 保存左上角的值（即 dp[i-1][j-1]）
遍历完当前行后，交换 prev 和 curr 的引用
空间复杂度从 O(mn) 降至 O(n)

空间优化版 Python 实现

def levenshtein_distance_optimized(s1, s2):
    # 确保 s2 是较短的字符串，以最小化空间
    if len(s1) < len(s2):
        s1, s2 = s2, s1

    m, n = len(s1), len(s2)
    # 只使用两个一维数组
    prev = list(range(n + 1))  # 第0行: [0, 1, 2, ..., n]
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        curr[0] = i  # 边界: dp[i][0] = i
        for j in range(1, n + 1):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            curr[j] = min(
                prev[j] + 1,          # 删除
                curr[j - 1] + 1,      # 插入
                prev[j - 1] + cost     # 替换
            )
        # 交换引用
        prev, curr = curr, prev

    return prev[n]


print(levenshtein_distance_optimized("kitten", "sitting"))  # 3

通过这种方法，空间复杂度从 O(mn) 降低到了 O(min(m, n))。当处理上万字符的字符串（如 DNA 序列片段）时，这一优化至关重要，可将内存消耗从数百 MB 降至数 KB。

六、算法变体

1. Damerau-Levenshtein 距离

在经典 Levenshtein 距离的三种操作基础上，额外增加了交换（Transposition）操作——即交换两个相邻字符的位置，代价为 1。例如 "ab" → "ba" 的 Damerau-Levenshtein 距离为 1（一次交换），而经典 Levenshtein 距离为 2（一次删除加一次插入）。

该变体由 Frederick Damerau 于 1964 年提出，特别适合处理拼写错误（人类打字时约 80% 的错误为单字符操作，其中相邻字符交换非常常见）。

2. 最长公共子序列（LCS）与编辑距离

如果将编辑操作限制为仅允许插入和删除（不允许替换），则编辑距离与最长公共子序列（Longest Common Subsequence, LCS）存在如下关系：

ed_LCS(A, B) = len(A) + len(B) - 2 x LCS(A, B)

这是因为 LCS 是两个字符串中保留最多的公共部分，其余字符需要被删除或插入。

3. 最长公共子串（LCSubstr）

与 LCS（不要求连续）不同，最长公共子串（Longest Common Substring）要求公共部分在原始字符串中连续出现。其动态规划递推公式更简单：

当 s1[i] == s2[j] 时，dp[i][j] = dp[i-1][j-1] + 1
否则 dp[i][j] = 0

整个矩阵的最大值即为最长公共子串的长度。

4. Jaro-Winkler 距离

另一种常用的字符串相似度度量，特别适用于短字符串的比较。它基于匹配字符的数量和换位次数，并给予前缀相同的字符串额外加分。Jaro-Winkler 距离在姓名匹配和记录链接领域表现优异。

七、应用场景

1. 拼写检查与纠错

搜索引擎和文本编辑器中，当用户输入一个可能拼写错误的单词时，系统会从词典中找出与输入单词编辑距离最小的若干候选词作为建议。例如输入 "speling"，系统可以计算出其与 "spelling" 的编辑距离为 1（插入一个 'l'），从而给出正确的拼写建议。

实际系统中通常结合BK-Tree（Burkhard-Keller Tree）等数据结构进行加速，避免与词典中所有单词逐一计算编辑距离。

2. 生物信息学与基因序列比对

在生物信息学中，DNA 序列可以表示为 A、T、C、G 组成的字符串。编辑距离（在生物信息学中常称为 Needleman-Wunsch 算法或序列比对）用于衡量不同物种之间基因序列的相似程度。进化距离越近的物种，其 DNA 序列的编辑距离越小。

例如人类与黑猩猩的基因序列相似度高达约 99%，对应极小的编辑距离。

3. 自然语言处理与文本相似度

在 NLP 领域，编辑距离可用于：

机器翻译评估： 比较机器翻译结果与人工参考译文之间的差异
语音识别纠错： 修正语音识别产生的近似错误
抄袭检测： 通过计算文本间编辑距离识别抄袭片段（常与滑动窗口结合使用）
自动摘要评估： 衡量生成摘要与参考摘要的相似度

4. 搜索引擎与模糊匹配

搜索引擎中的以下功能都依赖于编辑距离或其变体：

"您是不是要找：" 功能（搜索词纠错）
模糊查询： 允许用户拼写误差的数据库查询
记录链接（Record Linkage）： 在不同数据源中匹配同一实体的记录（如匹配 "Jon Smith" 和 "John Smith"）
重复数据检测： 发现数据库中相似但非完全相同的重复记录

八、加权编辑距离

在实际应用中，不同的编辑操作往往具有不同的权重。例如在 OCR（光学字符识别）纠错中，"rn" 被误识别为 "m" 的概率很高，因此将 "rn" 替换为 "m" 的代价应该远低于其他替换操作。这种加权编辑距离（Weighted Edit Distance）允许为每种编辑操作赋予自定义的代价。

加权编辑距离的数学定义

dp[i][j] = min(

dp[i-1][j] + w_del(s1[i-1]),

dp[i][j-1] + w_ins(s2[j-1]),

dp[i-1][j-1] + w_sub(s1[i-1], s2[j-1])

)

其中 w_del、w_ins 和 w_sub 分别是删除、插入和替换的代价函数，可以根据具体应用灵活定义。

加权编辑距离 Python 实现

def weighted_edit_distance(s1, s2, w_del, w_ins, w_sub):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        dp[i][0] = dp[i - 1][0] + w_del(s1[i - 1])
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] + w_ins(s2[j - 1])

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = w_sub(s1[i - 1], s2[j - 1])
            dp[i][j] = min(
                dp[i - 1][j] + w_del(s1[i - 1]),
                dp[i][j - 1] + w_ins(s2[j - 1]),
                dp[i - 1][j - 1] + cost
            )
    return dp[m][n]


# 示例：OCR 纠错场景，字符 '0' 和 'O' 之间的替换代价较低
def ocr_sub(a, b):
    if a == b:
        return 0
    if (a, b) in [('0', 'O'), ('O', '0'),
                    ('1', 'l'), ('l', '1'),
                    ('m', 'rn'), ('rn', 'm')]:
        return 0.5  # 视觉相似字符的替换代价减半
    return 1.0   # 不相似字符的完全替换代价


result = weighted_edit_distance(
    "He11o", "Hello",
    w_del=lambda c: 1.0,
    w_ins=lambda c: 1.0,
    w_sub=ocr_sub
)
print(result)  # 0.5 (因为 '1' 和 'l' 的替换代价为 0.5)

九、工程实践中的优化技巧

1. 提前终止（Early Termination）

如果只需要判断编辑距离是否小于某个阈值 K（如拼写检查中只推荐距离 ≤ 2 的单词），可以使用提前终止优化：当 DP 矩阵当前行的最小值已经大于 K 时，可以立即停止计算并返回一个大于 K 的近似距离。这一优化结合 BK-Tree 可以大幅缩小搜索空间。

2. 分治策略（Divide and Conquer）

对于超长字符串（如整个基因序列），可以采用 Hirschberg 算法，该算法在计算编辑距离的同时仅使用 O(min(m, n)) 的空间。其核心思想是：

将字符串从中间分割，递归计算左右两半的编辑距离
使用空间优化版 DP 计算每一半的距离
找到最优分割点后拼接结果

3. 并行化计算

DP 矩阵的计算具有反对角线依赖的特性：同一反对角线（i + j 为常数的格子）上的计算互不依赖，可以并行执行。利用这一特性可以在 GPU 或多核 CPU 上实现编辑距离的并行加速。

4. 近似算法

对于不需要精确结果的场景，可以使用近似算法：

Simhash： 通过哈希指纹近似估计文本相似度
MinHash： 基于 Jaccard 相似度的近似方法
局部敏感哈希（LSH）： 将相似字符串映射到同一桶中

十、与其他算法的对比

算法	时间复杂度	允许的操作	典型应用
Levenshtein	O(mn)	插入、删除、替换	通用字符串比较
Damerau-Levenshtein	O(mn)	插入、删除、替换、交换	拼写纠错
LCS	O(mn)	仅保留相同字符（不允许替换）	基因序列比对
Jaro-Winkler	O(m+n)	匹配、换位	姓名匹配
Hamming 距离	O(n)	仅替换（等长字符串）	信息论、纠错码

十一、核心要点总结

编辑距离定义： 将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换），操作成本均为 1
DP 递推公式： dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)，其中 cost 在字符相同时为 0，否则为 1
时间复杂度： O(mn)，空间复杂度可优化至 O(min(m, n))
路径回溯： 从右下角反向遍历 DP 矩阵可输出具体的编辑操作序列
空间优化： 滚动数组技术可将空间从 O(mn) 降低到 O(n)
重要变体： Damerau-Levenshtein 距离增加交换操作；LCS 距离限制为只有插入和删除；加权编辑距离支持自定义操作成本
广泛应用： 拼写检查、搜索引擎纠错、基因序列比对、抄袭检测、语音识别、OCR 纠错
工程优化： 提前终止、分治策略、并行计算、近似算法可以应对大规模和超长字符串场景
加权编辑距离： 允许为不同字符间的编辑操作赋予不同的代价，使算法更贴近实际应用需求

十二、进一步思考

编辑距离作为字符串相似度计算的基础算法，其思想在计算机科学的多个领域产生了深远影响：

扩展思考：

算法思想的迁移： 编辑距离的动态规划思想可以推广到树编辑距离（比较 XML/HTML 文档树结构的差异）和图编辑距离（比较图结构的相似度）
深度学习时代的定位： 虽然深度学习模型（如 BERT、GPT）在语义匹配上表现更优，但编辑距离在字符级精确匹配场景下仍然不可替代，且具备完全的可解释性和确定性
与大语言模型的结合： 在 RAG（检索增强生成）系统中，编辑距离可作为快速筛选候选文档的轻量级特征，与大模型的语义理解形成互补
技术面试价值： 编辑距离是技术面试中最高频的动态规划题目之一，掌握其 DP 推导、空间优化和回溯实现是面试准备的重要内容
Unicode 和多语言支持： 在实际工程中需考虑 Unicode 字符、emoji 和组合字符的处理，简单按字节或按代码点计算都可能产生偏差

掌握编辑距离不仅能帮助理解动态规划的核心思想——最优子结构和重叠子问题，更能为后续学习更复杂的序列比对算法（如 Smith-Waterman 局部比对算法）打下坚实基础。它是一个在理论与工程实践之间达到完美平衡的经典算法。