最小编辑距离

最小编辑距离

目的:找出串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()