迹忆客 专注技术分享

今天，我们将学习Python中的编辑距离。 我们还将探讨字符串的插入、删除、替换和递归实现。

在 Python 中编辑距离

编辑距离是将一个字符串转置为另一个字符串所需的量。 这种转置是通过递归、替换、插入和删除字符串的字符来完成的。

将一个单词变成另一个单词所需的字符删除、插入和替换次数取决于两个单词编辑的紧密程度。

它在 Python 中也被称为 Levenshtein 距离，因为它不需要比较两个字符串的长度相同； Levenshtein 距离有很大的影响。

编辑距离很容易直观地理解。 单字符修改的总数决定了两者之间的距离。

输出距离表示需要多少修改才能使两个单词相同。 输出距离越小，需要的改变就越少。

让我们通过以下字符串插入、删除、替换和递归实现的示例代码来了解编辑距离。

字符串的插入

在下面的代码中，t 被插入到字机中的 i 和 n 之间。

示例代码：

w= "Machine"
w= w[:5] + "t" + w[5:]
print(w)

输出:

Machitne

字符串的删除

下面的代码中，在字机中a和h之间删除了c。

示例代码：

w= "Machine"
w = w[:2] + w[3:]
print(w)

输出:

Mahine

字符串的替换

在下面的代码中，c在字机中的a和h之间被a替换。

示例代码：

w = "Machine"
w = w[:2] + "a" + w[3:]
print(w)

输出:

Maahine

字符串的递归实现

机器和学习之间的编辑距离为 5，如下面的输出所示。

我们可以获取用户输入的任何字符串，并在以下 Python 方法中递归实现编辑距离。

这种递归技术效率低下，因为重复计算相同子串的编辑距离。

示例代码：

w1=input("Type here for word 1: ")
w2=input("Type here for word 2: ")

len1=len(w1)
len2=len(w2)

a =[[0]*(len2+1) for _ in range(len1+1)]

for m in range(0,len1+1):
    a[m][0]=m
    
for n in range(0,len2+1):
    a[0][n]=n
    
for m in range (1,len1+1):
    for n in range(1,len2+1):
        if w1[m-1]==w2[n-1]:
            a[m][n] = a[m-1][n-1]
        else :
            a[m][n]= min(a[m][n-1],a[m-1][n],a[m-1][n-1])+1
print(a[m][n])

输出:

Type here for word 1: machine
Type here for word 2: learning
5