目录
编辑距离
编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance（莱文斯坦距离）。
在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词之间，由其中一个单词转换为另一个单词所需要的最少单字符编辑操作次数。
在这里定义的单字符编辑操作有且仅有三种：
- 插入（Insertion）
- 删除（Deletion）
- 替换（Substitution）
例如，"kitten" 和 "sitting" 这两个单词，由 "kitten" 转换为 "sitting" 需要的最少单字符编辑操作有：
- kitten → sitten (substitution of "s" for "k")
- sitten → sittin (substitution of "i" for "e")
- sittin → sitting (insertion of "g" at the end)
因此，"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。
定义
我们将两个字符串 a、b 的莱文斯坦距离表示为\(f(m,n)\)，其中，\(m\), \(n\)分别表示字符串 a、b 的长度，那么：
初始条件
当字符串 a、b 其中一个字符串为空字符时，需要编辑的次数就是不为零的字符串的长度，即：
\[f(i, j) = max(m, n), \quad \text i = 0 \quad or \quad j = 0 \]状态转移
当字符串 a、b 都不为空字符串时，对于当字符串 a、b 中的任意一个字符，我们考虑一般情况，我们使用两个指针 i、j 分别指向 a 和 b ，对于任意一个字符 \(a[i]\) 和 \(b[j]\) ，存在两种场景：
场景一：字符a[i]和b[j]相等
那么，此时不需要做任何编辑操作，即\(f[i][j] = f[i - 1][j - 1]\)；
场景二：字符a[i]和b[j]不相等
如果字符 \(a[i]\) 和 \(b[j]\) 不相等，那么，这时，有三种操作：
- 删除字符 \(a[i]\), 此时 \(a[i]\) 和 \(b[j]\) 相等，当前状态，可以由上一个状态\(f[i - 1][j]\) 加 1 转移而来；
- 在 a 中的位置 i 插入一个新的字符\(b[j]\)，此时 \(a[i]\) 和 \(b[j]\) 相等，那么当前状态，可以由上一个状态 \(f[i][j - 1]\) 加 1 转移而来；
- 将字符 \(a[i]\) 替换成 字符 \(b[j]\)，此时 \(a[i]\) 和 \(b[j]\) 相等，那么当前状态，可以由上一个状态 \(f[i - 1][j - 1]\) 加 1 转移而来；
所以，当字符a[i]和b[j]不相等时，只需要取上述三种情况的最小值即可，即
\[dp[i][j] = min(dp[i - 1][j] + 1,\quad dp[i][j - 1] + 1,\quad dp[i - 1][j - 1] + 1) \]综上，对于上述两种场景，状态转移方程：
\[f(i,\ j) = \begin{cases} f(i - 1,\ j - 1), & a[i] = b[j] \\ min(f(i - 1,\ j) + 1,\quad f(i,\ j - 1) + 1,\quad f(i - 1,\ j - 1) + 1), & a[i] \ne b[j] \end{cases} \]代码实现
递归实现
def LevenshteinDistance(str1: str, str2: str):
if len(str1) == 0:
return len(str2)
elif len(str2) == 0:
return len(str1)
elif str1 == str2:
return 0
# 如果两个字符的最后一个字符相等
if str1[len(str1) - 1] == str2[len(str2) - 1]:
return LevenshteinDistance(str1[:-1], str2[:-1])
else:
return min(
LevenshteinDistance(str1, str2[:-1]) + 1,
LevenshteinDistance(str1[:-1], str2) + 1,
LevenshteinDistance(str1[:-1], str2[:-1]) + 1
)
迭代实现
def LevenshteinDistance(str1: str, str2: str):
m, n = len(str1), len(str2)
if m * n == 0:
return m + n
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for i in range(n + 1):
dp[0][i] = i
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
)
return dp[m][n]
应用
应用1：Leetcode.72
题目
分析
略。
代码实现
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
if m * n == 0:
return m + n
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for i in range(n + 1):
dp[0][i] = i
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
)
return dp[m][n]
总结
编辑距离是NLP基本的度量文本相似度的算法，可以作为文本相似任务的重要特征之一，其可应用于诸如拼写检查、论文查重、基因序列分析等多个方面。
但是其缺点也很明显，算法基于文本自身的结构去计算，并没有办法获取到语义层面的信息。
标签：字符,str2,str1,距离,编辑,range,len,dp From： https://www.cnblogs.com/larry1024/p/17006974.html