字符串编辑距离

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

基本概念

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

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

数学定义

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

$d[i][j]=\{\begin{array}{ll}\max (i,j)& \text{如果 }\min (i,j)=0,\\ \min \{\begin{array}{l}d[i-1][j]+1,\\ d[i][j-1]+1,\\ d[i-1][j-1]+\mathbb{𝕀}(s_i\ne t_j)\end{array}& \text{否则}\end{array}$

其中：

• $d[i][j]$ 表示 $s$ 的前 $i$ 个字符和 $t$ 的前 $j$ 个字符之间的编辑距离。
• $\mathbb{𝕀}(s_i\ne t_j)$ 是指示函数，当 $s_i\ne 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"）

可视化计算过程

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

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")]

实际应用

拼写检查

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

• 用户输入 "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。

总结

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