使用编辑距离衡量字符串的相似度
-
使用一个二维数组 $E(x,y)$ 来保存字符串1的前$x$项与字符串2的前$y$项的编辑距离
-
递推
\(E(x,y)=min\left\{
\begin{array}
E(x-1,y) & \mbox{删除}\\
E(x,y-1) & \mbox{插入}\\
\left\{
\begin{array}{lr}
E(x-1,y-1) & C(x)=C(y)\\
E(x-1,y-1)+1&C(x)\ne C(y)
\end{array}
\right.
& \mbox{替换}
\end{array}
\right.\)
其中：$C(x)$表示$x$处的字符，默认$x$为第一个字符串的第$x$个字符，$y$为第二个字符串的第$y$个字符
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
| '''
@Author: MetaNetworks
@Date: 2019-11-21 11:16:44
@LastEditors: MetaNetworks
@LastEditTime: 2019-11-21 11:40:10
@Description: MetaNetworks' Code
'''
import numpy as np
str_s = ['sunny','snowy']
nd = None
def cal(x,y):
global nd
if nd[x][y] != -1:
return nd[x][y]
# 计算nd[x][y]
n1 = cal(x-1,y) + 1
n2 = cal(x,y-1) + 1
n3 = cal(x-1,y-1)
if str_s[0][x-1] != str_s[1][y-1]:
n3 = n3 + 1
n = min(n1,n2,n3)
nd[x][y]=n
return n
if __name__ == "__main__":
n_row = (len(str_s[0])+1)
n_col = (len(str_s[1])+1)
nd = np.arange(n_row*n_col).reshape(n_row,n_col)
# 全 -1 数组
nd = - np.ones((n_row,n_col))
# 初始化0行0列
for r in range(n_row):
nd[r][0] = r
for c in range(n_col):
nd[0][c] = c
# 填表
x = n_row - 1
y = n_col - 1
# 输出
print(cal(x,y))
|
结果
动态规划的LIS（最长非降子序列）
\[A = <1,-1,2,-3,4,-5,6,-7>\]
| A |
1 |
-1 |
2 |
-3 |
4 |
-5 |
6 |
-7 |
| $L(i)$ |
1 |
1 |
2 |
1 |
3 |
1 |
4 |
1 |
- 碰到比上一个小的，$L(i)$置为$1$
- 碰到一个大的，则$L(i)$等于上一个大的$+1$
