加权莱文斯坦距离/加权最小编辑距离(python)

115 阅读 0 评论 76 点赞

我是靠谱客的博主兴奋黄豆，这篇文章主要介绍加权莱文斯坦距离/加权最小编辑距离(python)，现在分享给大家，希望可以做个参考。

不加权的最小编辑距离链接：

https://blog.csdn.net/qq_36282995/article/details/116419855

之前讲解了关于不加权的最小编辑距离，即字符串之间添加、删除、修改字符的比重是一样的。

但这其实是不太合理的。

比如‘abc’转换为‘abv’，我们只需要将字母c转换为字母v即可。我们记为编辑距离为1.

对于‘abc’转换为‘abp’，只需要将字母c转换为字母p即可，编辑距离也为1.

但我们知道，在键盘上字母c和字母v的距离很近，但字母c和字母p的距离很远，所以一个人将字母c误编辑为字母p的概率是比较低的。

因此我们在之前的基础上添加加权的操作。

我们在未加权时，是这样设定的：

复制代码

1
2
3
4
if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])

其中：dp[i-1][j-1]，对应的是修改操作。

dp[i][j-1],对应的是添加操作。

dp[i-1][j]，对应的是删除操作。

我们只需要针对不同的操作，将之前设置的权重1进行修改即可。这里的权重可以是基于统计的权重表格，也可以是基于一定规则的运算，比如一个时间序列，其权重可以是时间之差。

示例代码如下：

复制代码

def insert(a):
#这里定义插入数据a时的权重
#比如插入数据是很重要的，权重设为10
#我没有定义删除数据a时的函数，因为我假设删除和添加的权重是一样的。
    return 10

def count(a,b):
#这里定义将数据a修改为数据b时的权重
#假设设置为a与b的差
    return a-b

def weightedDistance( word1: str, word2: str) -> int:
    '''
        加权动态规划求解
    '''
    print(word1)
    m = len(word1)
    n = len(word2)
    print(m)
    print(n)

dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

dp[0][0] = 0
    #要记得初始化权重，在这里就已经要加权计算了
    for i in range(1,m+1):
        dp[i][0] = dp[i-1][0] + insert(word1[i-1])
    for j in range(1,n+1):
        dp[0][j] = dp[0][j-1] + insert(word2[j-1])
    
    # for i in range(m+1):
    #     for j in range(n+1):
    #         print(dp[i][j],end=' ')
    #     print()
    for i in range(1,1+m):
        for j in range(1,1+n):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                #对三种情况分别计算，再比较
                t1=dp[i-1][j-1]+count(word1[i-1],word2[j-1])
                t2=dp[i][j-1]+insert(word2[j-1])
                t3=dp[i-1][j]+insert(word1[i-1])
                dp[i][j] = min(t1,t2,t3)
    for i in range(m+1):
        for j in range(n+1):
            print(dp[i][j],end=' ')
        print()
    return dp[m][n]

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
def insert(a):
#这里定义插入数据a时的权重
#比如插入数据是很重要的，权重设为10
#我没有定义删除数据a时的函数，因为我假设删除和添加的权重是一样的。
    return 10

def count(a,b):
#这里定义将数据a修改为数据b时的权重
#假设设置为a与b的差
    return a-b

def weightedDistance( word1: str, word2: str) -> int:
    '''
        加权动态规划求解
    '''
    print(word1)
    m = len(word1)
    n = len(word2)
    print(m)
    print(n)

    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    dp[0][0] = 0
    #要记得初始化权重，在这里就已经要加权计算了
    for i in range(1,m+1):
        dp[i][0] = dp[i-1][0] + insert(word1[i-1])
    for j in range(1,n+1):
        dp[0][j] = dp[0][j-1] + insert(word2[j-1])
    
    # for i in range(m+1):
    #     for j in range(n+1):
    #         print(dp[i][j],end=' ')
    #     print()
    for i in range(1,1+m):
        for j in range(1,1+n):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                #对三种情况分别计算，再比较
                t1=dp[i-1][j-1]+count(word1[i-1],word2[j-1])
                t2=dp[i][j-1]+insert(word2[j-1])
                t3=dp[i-1][j]+insert(word1[i-1])
                dp[i][j] = min(t1,t2,t3)
    for i in range(m+1):
        for j in range(n+1):
            print(dp[i][j],end=' ')
        print()
    return dp[m][n]