编辑“︁字符串编辑距离”︁

{{DISPLAYTITLE:字符串编辑距离}}

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

== 基本概念 ==

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

* '''插入'''：在 <math>s</math> 中插入一个字符，使其更接近 <math>t</math>。
* '''删除'''：从 <math>s</math> 中删除一个字符，使其更接近 <math>t</math>。
* '''替换'''：将 <math>s</math> 中的一个字符替换为 <math>t</math> 中的一个字符。

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

<math>
d[i][j] = \begin{cases}
\max(i, j) & \text{如果 } \min(i, j) = 0, \\
\min \begin{cases}
d[i-1][j] + 1, \\
d[i][j-1] + 1, \\
d[i-1][j-1] + \mathbb{I}(s_i \neq t_j)
\end{cases} & \text{否则}
\end{cases}
</math>

其中：
* <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(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
</syntaxhighlight>

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

== 可视化计算过程 ==

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

<mermaid>
flowchart TD
    A[(" ")] --> B[("s")]
    A --> C[("i")]
    A --> D[("t")]
    B --> E[("k:1")]
    C --> F[("i:2")]
    D --> G[("t:3")]
    E --> H[("s:1")]
    F --> I[("i:1")]
    G --> J[("t:2")]
</mermaid>

== 实际应用 ==

=== 拼写检查 ===
编辑距离用于拼写纠错，如：
* 用户输入 "helo"，系统建议 "hello"（编辑距离 = 1）。

=== DNA序列比对 ===
在生物信息学中，编辑距离用于衡量DNA序列的相似性：
* 比较 "AGCT" 和 "AGGT" 的差异（编辑距离 = 1）。

=== 模糊搜索 ===
搜索引擎使用编辑距离处理拼写错误：
* 搜索 "Googel" 可能返回 "Google" 的结果（编辑距离 = 1）。

== 优化与变种 ==

=== 空间优化 ===
动态规划的空间复杂度可优化为 <math>O(n)</math>：

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

=== 加权编辑距离 ===
不同操作可以赋予不同权重，如：
* 替换代价 = 2，插入/删除代价 = 1。

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:字符串算法]]