字符串编辑距离：修订间差异

2025年5月12日 (一) 00:18的最新版本

字符串编辑距离（Edit Distance），又称莱文斯坦距离（Levenshtein Distance），是衡量两个字符串之间相似程度的一种方法。它定义为将一个字符串转换成另一个字符串所需的最少单字符编辑操作（插入、删除或替换）次数。该概念在拼写检查、生物信息学、自然语言处理等领域有广泛应用。

基本概念[编辑 | 编辑源代码]

给定两个字符串 $s$ 和 $t$ ，编辑距离 $d (s, t)$ 的计算方式如下：

插入：在 $s$ 中插入一个字符，使其更接近 $t$ 。
删除：从 $s$ 中删除一个字符，使其更接近 $t$ 。
替换：将 $s$ 中的一个字符替换为 $t$ 中的一个字符。

数学定义[编辑 | 编辑源代码]

编辑距离可以通过动态规划计算，其递推公式为：

$d [i] [j] = {\begin{cases} \max (i, j) & 如果 \min (i, j) = 0, \\ \min {\begin{cases} d [i - 1] [j] + 1, \\ d [i] [j - 1] + 1, \\ d [i - 1] [j - 1] + 𝕀 (s_{i} \neq t_{j}) \end{cases} & 否则 \end{cases}$

其中：

$d [i] [j]$ 表示 $s$ 的前 $i$ 个字符和 $t$ 的前 $j$ 个字符之间的编辑距离。
$𝕀 (s_{i} \neq t_{j})$ 是指示函数，当 $s_{i} \neq t_{j}$ 时值为 1，否则为 0。

动态规划实现[编辑 | 编辑源代码]

以下是一个 Python 实现示例：

def edit_distance(s: str, t: str) -> int:
    m, n = len(s), len(t)
    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):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(
                    dp[i - 1][j] + 1,    # 删除
                    dp[i][j - 1] + 1,    # 插入
                    dp[i - 1][j - 1] + 1 # 替换
                )
    return dp[m][n]

# 示例
s = "kitten"
t = "sitting"
print(edit_distance(s, t))  # 输出: 3

示例解析[编辑 | 编辑源代码]

对于输入 s = "kitten" 和 t = "sitting"，编辑距离为 3，操作如下： 1. 替换 'k' → 's'（"kitten" → "sitten"） 2. 替换 'e' → 'i'（"sitten" → "sittin"） 3. 插入 'g'（"sittin" → "sitting"）

可视化计算过程[编辑 | 编辑源代码]

以下是一个动态规划表的示例（部分）：

实际应用[编辑 | 编辑源代码]

拼写检查[编辑 | 编辑源代码]

编辑距离用于拼写纠错，如：

用户输入 "helo"，系统建议 "hello"（编辑距离 = 1）。

DNA序列比对[编辑 | 编辑源代码]

在生物信息学中，编辑距离用于衡量DNA序列的相似性：

比较 "AGCT" 和 "AGGT" 的差异（编辑距离 = 1）。

模糊搜索[编辑 | 编辑源代码]

搜索引擎使用编辑距离处理拼写错误：

搜索 "Googel" 可能返回 "Google" 的结果（编辑距离 = 1）。

优化与变种[编辑 | 编辑源代码]

空间优化[编辑 | 编辑源代码]

动态规划的空间复杂度可优化为 $O (n)$ ：

def edit_distance_optimized(s: str, t: str) -> int:
    m, n = len(s), len(t)
    prev = [j for j in range(n + 1)]

    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = min(prev[j] + 1, curr[j - 1] + 1, prev[j - 1] + 1)
        prev = curr
    return prev[n]

加权编辑距离[编辑 | 编辑源代码]

不同操作可以赋予不同权重，如：

替换代价 = 2，插入/删除代价 = 1。

总结[编辑 | 编辑源代码]

字符串编辑距离是衡量两个字符串相似性的重要方法，广泛应用于文本处理、生物信息学等领域。通过动态规划高效计算，并可进一步优化以适应不同场景需求。

@@ 第1行： / 第1行： @@
 {{DISPLAYTITLE:字符串编辑距离}}
-'''字符串编辑距离'''（Edit Distance），又称'''莱文斯坦距离'''（Levenshtein Distance），是衡量两个字符串之间相似程度的经典动态规划问题。它定义为将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除或替换）。
+'''字符串编辑距离'''（Edit Distance），又称'''莱文斯坦距离'''（Levenshtein Distance），是衡量两个字符串之间相似程度的一种方法。它定义为将一个字符串转换成另一个字符串所需的最少'''单字符编辑操作'''（插入、删除或替换）次数。该概念在拼写检查、生物信息学、自然语言处理等领域有广泛应用。
-== 定义与基本概念 ==
+== 基本概念 ==
-给定两个字符串 <math>A</math> 和 <math>B</math>，编辑距离 <math>d(A, B)</math> 的计算基于以下操作：
+给定两个字符串 <math>s</math> 和 <math>t</math>，编辑距离 <math>d(s, t)</math> 的计算方式如下：
-* '''插入'''（Insert）：在字符串中插入一个字符。
-* '''删除'''（Delete）：删除字符串中的一个字符。
-* '''替换'''（Replace）：将字符串中的一个字符替换为另一个字符。
-例如，将 "kitten" 转换为 "sitting" 的编辑距离为 3：
+* '''插入'''：在 <math>s</math> 中插入一个字符，使其更接近 <math>t</math>。
-# kitten → sitten（替换 'k' 为 's'）
+* '''删除'''：从 <math>s</math> 中删除一个字符，使其更接近 <math>t</math>。
-# sitten → sittin（替换 'e' 为 'i'）
+* '''替换'''：将 <math>s</math> 中的一个字符替换为 <math>t</math> 中的一个字符。
-# sittin → sitting（插入 'g'）
-== 动态规划解法 ==
+=== 数学定义 ===
+编辑距离可以通过动态规划计算，其递推公式为：
-编辑距离问题可以通过动态规划高效解决。定义 <math>dp[i][j]</math> 表示字符串 <math>A[0..i-1]</math> 和 <math>B[0..j-1]</math> 之间的编辑距离。状态转移方程如下：
 <math>
-dp[i][j] = \begin{cases}
+d[i][j] = \begin{cases}
-i & \text{if } j = 0, \\
+\max(i, j) & \text{如果 } \min(i, j) = 0, \\
-j & \text{if } i = 0, \\
+\min \begin{cases}
-dp[i-1][j-1] & \text{if } A[i-1] = B[j-1], \\
+d[i-1][j] + 1, \\
-+ \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) & \text{otherwise.}
+d[i][j-1] + 1, \\
+d[i-1][j-1] + \mathbb{I}(s_i \neq t_j)
+\end{cases} & \text{否则}
 \end{cases}
 </math>
-=== 代码实现 ===
+其中：
-以下是 Python 实现示例：
+* <math>d[i][j]</math> 表示 <math>s</math> 的前 <math>i</math> 个字符和 <math>t</math> 的前 <math>j</math> 个字符之间的编辑距离。
+* <math>\mathbb{I}(s_i \neq t_j)</math> 是指示函数，当 <math>s_i \neq t_j</math> 时值为 1，否则为 0。
+== 动态规划实现 ==
+以下是一个 Python 实现示例：
 <syntaxhighlight lang="python">
-def edit_distance(str1, str2):
+def edit_distance(s: str, t: str) -> int:
-     m, n = len(str1), len(str2)
+     m, n = len(s), len(t)
      dp = [[0] * (n + 1) for _ in range(m + 1)]
@@ 第43行： / 第45行： @@
      for i in range(1, m + 1):
          for j in range(1, n + 1):
-             if str1[i - 1] == str2[j - 1]:
+             if s[i - 1] == t[j - 1]:
                  dp[i][j] = dp[i - 1][j - 1]
              else:
-                 dp[i][j] = 1 + min(dp[i - 1][j],      # 删除
+                 dp[i][j] = min(
-                                   dp[i][j - 1],      # 插入
+                    dp[i - 1][j] + 1,    # 删除
-                                   dp[i - 1][j - 1])  # 替换
+                    dp[i][j - 1] + 1,    # 插入
+                    dp[i - 1][j - 1] + 1 # 替换
+                )
      return dp[m][n]
 # 示例
-print(edit_distance("kitten", "sitting"))  # 输出: 3
+s = "kitten"
+t = "sitting"
+print(edit_distance(s, t))  # 输出: 3
 </syntaxhighlight>
-=== 动态规划表解析 ===
+=== 示例解析 ===
-以 "kitten" 和 "sitting" 为例，动态规划表如下：
+对于输入 <code>s = "kitten"</code> 和 <code>t = "sitting"</code>，编辑距离为 3，操作如下：
+. '''替换''' 'k' → 's'（"kitten" → "sitten"）
+. '''替换''' 'e' → 'i'（"sitten" → "sittin"）
+. '''插入''' 'g'（"sittin" → "sitting"）
+== 可视化计算过程 ==
+以下是一个动态规划表的示例（部分）：
 <mermaid>
-flowchart LR
+flowchart TD
-     subgraph DP Table
+     A[(" ")] --> B[("s")]
-        A[0,1,2,3,4,5,6,7]
+    A --> C[("i")]
-        B[1,1,2,3,4,5,6,7]
+    A --> D[("t")]
-        C[2,2,1,2,3,4,5,6]
+    B --> E[("k:1")]
-        D[3,3,2,1,2,3,4,5]
+    C --> F[("i:2")]
-        E[4,4,3,2,1,2,3,4]
+    D --> G[("t:3")]
-        F[5,5,4,3,2,2,3,4]
+    E --> H[("s:1")]
-        G[6,6,5,4,3,3,2,3]
+    F --> I[("i:1")]
-    end
+    G --> J[("t:2")]
 </mermaid>
-== 优化空间复杂度 ==
+== 实际应用 ==
-上述算法空间复杂度为 <math>O(mn)</math>。可优化至 <math>O(\min(m, n))</math>，仅保留前一行的数据：
+=== 拼写检查 ===
+编辑距离用于拼写纠错，如：
+* 用户输入 "helo"，系统建议 "hello"（编辑距离 = 1）。
+=== DNA序列比对 ===
+在生物信息学中，编辑距离用于衡量DNA序列的相似性：
+* 比较 "AGCT" 和 "AGGT" 的差异（编辑距离 = 1）。
+=== 模糊搜索 ===
+搜索引擎使用编辑距离处理拼写错误：
+* 搜索 "Googel" 可能返回 "Google" 的结果（编辑距离 = 1）。
+== 优化与变种 ==
+=== 空间优化 ===
+动态规划的空间复杂度可优化为 <math>O(n)</math>：
 <syntaxhighlight lang="python">
-def edit_distance_optimized(str1, str2):
+def edit_distance_optimized(s: str, t: str) -> int:
-     m, n = len(str1), len(str2)
+     m, n = len(s), len(t)
-    if m < n:
+     prev = [j for j in range(n + 1)]
-        return edit_distance_optimized(str2, str1)
-     prev = list(range(n + 1))
      for i in range(1, m + 1):
          curr = [i] + [0] * n
          for j in range(1, n + 1):
-             if str1[i - 1] == str2[j - 1]:
+             if s[i - 1] == t[j - 1]:
                  curr[j] = prev[j - 1]
              else:
-                 curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
+                 curr[j] = min(prev[j] + 1, curr[j - 1] + 1, prev[j - 1] + 1)
          prev = curr
      return prev[n]
 </syntaxhighlight>
-== 实际应用案例 ==
+=== 加权编辑距离 ===
-. '''拼写检查'''：如输入法建议最接近的正确单词。
+不同操作可以赋予不同权重，如：
-. '''生物信息学'''：比较DNA序列的相似性。
+* 替换代价 = 2，插入/删除代价 = 1。
-. '''自然语言处理'''：模糊字符串匹配，如搜索引擎纠错。
-=== 案例：拼写纠正 ===
-假设用户输入 "helo"，候选词为 ["hello", "help", "hole"]。计算编辑距离：
-* helo → hello: 1（插入 'l'）
-* helo → help:  2（替换 'o' 为 'p'，插入 'p'）
-* helo → hole:  1（替换 'e' 为 'o'）
-优先推荐 "hello" 和 "hole"。
-== 变种与扩展 ==
-* '''Damerau-Levenshtein 距离'''：增加相邻字符交换操作。
-* '''加权编辑距离'''：为不同操作分配不同权重。
-* '''最长公共子序列'''（LCS）：仅允许插入和删除操作。
 == 总结 ==
-字符串编辑距离是动态规划的经典应用，通过分解子问题并存储中间结果，高效解决了字符串相似度计算问题。理解其原理有助于掌握更复杂的序列比对算法。
+字符串编辑距离是衡量两个字符串相似性的重要方法，广泛应用于文本处理、生物信息学等领域。通过动态规划高效计算，并可进一步优化以适应不同场景需求。
-{{算法导航}}
 [[Category:计算机科学]]
 [[Category:数据结构与算法]]
-[[Category:动态规划]]
+[[Category:字符串算法]]