Python 实现 Levenshtein 距离算法:距离方法
以下是一个 Python 实现 Levenshtein 距离算法的示例,该示例还包含一个名为 distance 的方法,该方法接受两个字符串作为参数并返回它们之间的距离。
def distance(s1, s2):
'Compute Levenshtein distance between two strings'
m, n = len(s1), len(s2)
# create a matrix with 0 as initial values
d = [[0] * (n + 1) for _ in range(m + 1)]
# initialize first row and column with incremental values
for i in range(m + 1):
d[i][0] = i
for j in range(n + 1):
d[0][j] = j
# fill the matrix with the minimum distance values
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
d[i][j] = d[i - 1][j - 1]
else:
d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1
return d[m][n]
这个函数使用动态规划技术来计算两个字符串之间的 Levenshtein 距离。它首先创建一个 m + 1 行和 n + 1 列的矩阵,其中 m 和 n 是两个字符串的长度。然后,它将第一行和第一列初始化为递增的值,以便在填充矩阵时有一个起点。最后,它使用一个嵌套的循环来迭代矩阵中的每个单元格,并使用最小距离值来填充它。
例如,如果我们调用 distance('kitten', 'sitting'),它将返回 3,这是 'kitten' 和 'sitting' 之间的最小编辑距离。
原文地址: https://www.cveoy.top/t/topic/nc0S 著作权归作者所有。请勿转载和采集!