当前位置：
  1. 首页
  2. 后端开发
  3. Python
  4. 正文

Python编辑距离

Python 58

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

Python中的编辑距离

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

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

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

Levenshtein 距离在直觉上是很容易理解的。单字符修改的总数决定了两者之间的距离。

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

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

字符串的插入

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

示例代码：

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

输出：

Machitne

字符串的删除

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

示例代码：

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

字符串的递归实现

machine 和learning 之间的编辑距离是5，如下面的输出所示。

我们可以接受用户的任何字符串输入，Levenshtein 距离在下面的Python方法中递归实现。

这种递归技术是低效的，因为相同的子字符串的Levenshtein 距离是重复计算的。

示例代码：

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
上一篇 Python的步骤代码
下一篇 在Python中使用Fsolve

相关文章