最小编辑距离

最小编辑距离

目的：找出串S经过多少次变化之后成为串T，要让这个次数变的最小

方法：插入，删除，替换

.注意 ：这里我们只对串S进行操作

操作方法

  1. 删除方法：

image-20220508204908549

S删除最后一位来进行对串T的转换

​ D[i, j] = D[i-1, j] + 1 ==>这里的含义是：S， T串中分别以i和j结尾的的最小编辑距离，依靠于D[i-1, j] 的最小编辑距离 + 1（删除操作）

  1. 插入方法：

​ 在串S的后面插入串T的最后一位（因为是要将串S变为T所以 需要在串S的后面加入T的最后一个元素）

​ image-20220508205340821

S最后插入一个元素来进行对串T的转换

D[i, j] = D[i, j-1] + 1 ==>这里的含义就是 S， T串中分别以i和j结尾的的最小编辑距离，依靠于串S的i位和串T的j-1为的最小编辑距离 + 1 （串S进行插入操作 插入串T的最后一位）

  1. 替换操作

在进行字符串变化操作的时候我们可以通过替换S的最后一个元素为T的最后一个元素，来进行字符串的变换操作

image-20220508211030351

D[i , j] = D[i-1, j-1] + (a = 0 if S[i] == T[j] else 1)

递推方式

  1. 初始化D数组：

D[i , 0] = i 把长度为i的串变为空串至少需要进行i次操作（删除）

D[0, j] = j 把空串变为长度为j的串至少需要进行j次操作（插入）

image-20220508212243123

  1. 递推公式：

​ D[i, j] = min(D[i-1, j] + 1 (删除) ， D[i, j-1] + 1 (插入)， D[i-1, j-1] + (a = 0 if S[i] == T[j] else 1)（替换）)

image-20220508212429149

  1. 标记Rec数组，记录操作方法：

​

Rec[i, j] 子问题来源 操作
U 上侧，即D[i-1, j] 删除S[i]
L 左侧，即D[i, j-1] 插入T[j]
LU 左上，即D[i-1, j-1] 用T[j]替换S[i]/无操作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
'''
最小编辑距离
    通过删除插入和操作来进行字符串的修改问题
'''
def mid_edit_distance(S, T, D, rec):

    # 进行数组D和rec的 填充
    for line in range(1, len(S)+1):
        for column in range(1, len(T)+1):
            # 一下两步是为了确定LU（替换） 操作是否需要替换操作 如果该元素相同的话则需要 +1操作， 如果不需要替换则不需要加一操作
            c = 1
            if S[line - 1] == T[column - 1]:
                c = 0

            # 进行各种操作的赋值
            LU = D[line - 1][column - 1] + c
            L = D[line][column-1] + 1
            U = D[line - 1][column] + 1

            # 我们的先后顺序是 先替换 后左 在上
            if LU <= L and LU <= U:
                D[line][column] = LU
                rec[line][column] = "LU"
            elif L <= LU and L <= U:
                D[line][column] = L
                rec[line][column] = "L"
            elif U <= LU and U <= L:
                D[line][column] = U
                rec[line][column] = "U"

# 初始化数组D Rec
def init_d_rec(S, T):
    line = len(S) + 1
    column = len(T) + 1
    
    D = [ [ [] for m in range(column)] for i in range(line)]
    rec = [ [ [] for m in range(column)] for i in range(line)]

    for l in range(line):
        D[l][0] = l
        rec[l][0] = 'U'
    for c in range(column):
        D[0][c] = c
        rec[0][c] = 'L'
    
    return D, rec


S = "ABCBDAB"
T = "BDCABA"

D, rec = init_d_rec(S, T)

mid_edit_distance(S, T, D, rec)

for line in D:
    for column in line:
        print(column, end = "\t")
    print()