算法设计与分析编辑距离

### 编辑距离算法的设计与分析

#### 定义与背景
编辑距离，也被称为Levenshtein距离，在信息论、语言学和计算机科学领域是用来度量两个序列相似程度的重要指标。具体来说，编辑距离是指将一个单词 \( w_1 \) 转换为另一个单词 \( w_2 \) 所需的最少单字符编辑操作次数[^2]。

这些编辑操作包括但不限于：

- 删除一个字符；
- 插入一个字符；
- 替换一个字符为另一个不同的字符。

#### 动态规划解法
为了有效地解决这一问题，通常采用动态规划的方法来计算最小编辑距离。该方法通过构建一张二维表格 `dp` 来记录子串之间的转换成本，其中 `dp[i][j]` 表示字符串A前i个字符组成的子串到字符串B前j个字符组成子串所需的最小编辑代价。

对于任意位置 `(i,j)` 上的状态转移方程如下所示：

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(dp[i-1][j],     # delete from A or insert into B
                   dp[i][j-1],      # insert into A or delete from B
                   dp[i-1][j-1]) + 1# replace character at i with j

边界条件则依据特殊情况设定：当一方为空串时，则另一方有多少个字符就需要多少次插入/删除操作才能匹配上对方全部内容；而两者的交集部分自然不需要任何变动即可视为相同[^1]。

最终得到的结果即位于矩阵右下角处元素值 `dp[m][n]` （m,n分别为AB各自长度），这便是所求得的整体最优解——即将整个字符串A完全转变为字符串B所需执行最低限度的操作数目[^3]。

def edit_distance(a, b):
    m, n = len(a), len(b)
    
    # Create matrix of size (m+1)x(n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize base cases where one string is empty
    for i in range(1, m + 1): 
        dp[i][0] = i
        
    for j in range(1, n + 1):  
        dp[0][j] = j
    
    # Fill the DP table using recurrence relation
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            
            dp[i][j] = min(
                dp[i - 1][j] + 1,       # Deletion
                dp[i][j - 1] + 1,       # Insertion
                dp[i - 1][j - 1] + cost # Substitution
            )
            
    return dp[-1]

print(edit_distance("intention", "execution"))