在做字符串相似度匹配时很有用，我更愿意叫它“相似度算法”~

简介

Levenshtein算法，又称编辑距离算法，是一种用于计算两个字符串之间最小编辑操作数的算法。编辑操作包括插入、删除和替换字符。该算法由苏联科学家Vladimir Levenshtein于1965年提出。

编辑操作

Levenshtein距离通过以下三种基本操作来衡量两个字符串的相似度：

  • 插入：在字符串中插入一个字符。
  • 删除：从字符串中删除一个字符。
  • 替换：将字符串中的一个字符替换为另一个字符。

算法实现

Levenshtein算法通常使用动态规划来实现。其核心思想是通过构建一个二维矩阵来记录两个字符串之间的编辑距离。具体步骤如下：

  • 初始化矩阵：

    • 创建一个大小为 (m+1) x (n+1) 的矩阵，其中 m 和 n 分别是两个字符串的长度。
    • 矩阵的第一行和第一列分别填充 0 到 m 和 0 到 n 的值。

  • 填充矩阵：

    • 对于矩阵中的每个元素，计算其值。该值等于以下三个值中的最小值加1：
      • 左边的值（表示删除操作）
      • 上面的值（表示插入操作）
      • 左上角的值（表示替换操作，如果字符相同则不加1）

  • 返回结果：

    • 矩阵右下角的值即为两个字符串的Levenshtein距离。

代码示例

以下是Levenshtein算法的Python实现：

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
def levenshtein_distance(s1, s2):
m, n = len(s1), len(s2)
# 初始化矩阵
dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 填充第一行和第一列
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # 填充矩阵
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                cost = 0
            else:
                cost = 1
            dp[i][j] = min(dp[i - 1][j] + 1,    # 删除
                           dp[i][j - 1] + 1,    # 插入
                           dp[i - 1][j - 1] + cost)  # 替换
    
    return dp[m][n]
    
# 示例使用
s1 = "kitten"
s2 = "sitting"
distance = levenshtein_distance(s1, s2)
print(f"Levenshtein距离: {distance}")

应用场景

Levenshtein算法在多个领域有广泛应用，包括但不限于：

  • 拼写检查：用于计算输入词与词典中词的相似度，从而建议正确的拼写。
  • DNA序列比对：用于测量两个DNA序列的相似性和差异。
  • 自然语言处理：用于文本相似度计算，文本去重等。
  • 信息检索：用于模糊搜索，找到与查询字符串相似的结果。

优缺点

优点：

  • 简单易懂，易于实现。
  • 能准确衡量字符串之间的相似度。

缺点：

  • 计算复杂度较高，为O(m*n)，其中m和n是两个字符串的长度。
  • 对于长字符串或需要大量比较的场景，性能可能不够理想。

Levenshtein算法是一个非常有用的工具，特别是在需要衡量字符串相似度的各种应用中。通过优化和改进，可以在不同的场景中实现更高效的性能。

Levenshtein算法简单示例

示例字符串

假设我们有两个字符串lhs = “cat”和rhs = “cut”，我们要计算它们之间的Levenshtein距离。

初始化矩阵

首先，我们初始化一个大小为(len(lhs) + 1) x (len(rhs) + 1)的矩阵，并填充第一行和第一列。

1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1
a    2
t    3

填充矩阵

我们逐步填充矩阵的每个位置dp[i][j]，并计算从lhs的前i个字符转换为rhs的前j个字符所需的最小编辑距离。

比较 c 和 c：

  • 删除 c：dp[0][1] + 1 = 2
  • 插入 c：dp[1][0] + 1 = 2
  • 替换 c 为 c：dp[0][0] + 0 = 0（字符相同，cost 为 0）
  • 取最小值：dp[1][1] = 0
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0
a    2
t    3

比较 c 和 u：

  • 删除 c：dp[0][2] + 1 = 3
  • 插入 u：dp[1][1] + 1 = 1
  • 替换 c 为 u：dp[0][1] + 1 = 2
  • 取最小值：dp[1][2] = 1
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1
a    2
t    3

比较 c 和 t：

  • 删除 c：dp[0][3] + 1 = 4
  • 插入 t：dp[1][2] + 1 = 2
  • 替换 c 为 t：dp[0][2] + 1 = 3
  • 取最小值：dp[1][3] = 2
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2
t    3

比较 a 和 c：

  • 删除 a：dp[1][1] + 1 = 1
  • 插入 c：dp[2][0] + 1 = 3
  • 替换 a 为 c：dp[1][0] + 1 = 2
  • 取最小值：dp[2][1] = 1
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2  1
t    3

比较 a 和 u：

  • 删除 a：dp[1][2] + 1 = 2
  • 插入 u：dp[2][1] + 1 = 2
  • 替换 a 为 u：dp[1][1] + 1 = 1
  • 取最小值：dp[2][2] = 1
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2  1  1
t    3

比较 a 和 t：

  • 删除 a：dp[1][3] + 1 = 3
  • 插入 t：dp[2][2] + 1 = 2
  • 替换 a 为 t：dp[1][2] + 1 = 2
  • 取最小值：dp[2][3] = 2
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2  1  1  2
t    3

比较 t 和 c：

  • 删除 t：dp[2][1] + 1 = 2
  • 插入 c：dp[3][0] + 1 = 4
  • 替换 t 为 c：dp[2][0] + 1 = 3
  • 取最小值：dp[3][1] = 2
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2  1  1  2
t    3  2

比较 t 和 u：

  • 删除 t：dp[2][2] + 1 = 2
  • 插入 u：dp[3][1] + 1 = 3
  • 替换 t 为 u：dp[2][1] + 1 = 2
  • 取最小值：dp[3][2] = 2
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2  1  1  2
t    3  2  2

比较 t 和 t：

  • 删除 t：dp[2][3] + 1 = 3
  • 插入 t：dp[3][2] + 1 = 3
  • 替换 t 为 t：dp[2][2] + 0 = 1（字符相同，cost 为 0）
  • 取最小值：dp[3][3] = 1
1
2
3
4
5
     ""  c  u  t
""   0  1  2  3
c    1  0  1  2
a    2  1  1  2
t    3  2  2  1

结果

矩阵右下角的值dp[3][3]为 1，即字符串 “cat” 和 “cut” 之间的Levenshtein距离为 1。这意味着只需要一次编辑操作（替换a为u）就可以将 “cat” 转换为 “cut”。

通俗解释

通过这个简单的例子，我们可以看到Levenshtein算法的工作原理。我们逐步比较两个字符串的每个字符，并选择最小的编辑操作（删除、插入或替换）来填充动态规划矩阵。最终，矩阵右下角的值就是两个字符串之间的最小编辑距离。