Levenshtein 距离的原理与应用

引言

在文本处理和自然语言处理（NLP）中，衡量两个字符串相似度是一项重要任务。Levenshtein 距离（也称编辑距离）是一种常见的算法，用于计算将一个字符串转换为另一个字符串所需的最少编辑操作次数。这些操作包括插入、删除和替换。

本文将详细介绍 Levenshtein 距离的原理，并通过 Python 代码示例展示其实际应用。

什么是 Levenshtein 距离？

Levenshtein 距离定义为两个字符串之间的最小编辑操作次数，使得一个字符串可以变为另一个字符串。允许的三种操作为：

1. 插入一个字符；
2. 删除一个字符；
3. 替换一个字符。

例如：

• "kitten" 和 "sitting" 的 Levenshtein 距离为 3，因为可以通过以下三步完成转换：
  1. 替换 'k' 为 's'；
  2. 替换 'e' 为 'i'；
  3. 在末尾插入 'g'。

Levenshtein 距离的计算原理

Levenshtein 距离使用动态规划（Dynamic Programming）实现，其核心思想是将问题分解为多个子问题，通过递归公式逐步计算解决。

假设字符串 AA 长度为 mm，字符串 BB 长度为 nn，则动态规划表 dp[i][j]dp[i][j] 表示将 A[0:i]A[0:i] 转换为 B[0:j]B[0:j] 的最小编辑距离。

Levenshtein 距离的 Python 实现

我们用一个简单的 Python 函数实现 Levenshtein 距离：

def levenshtein_distance(a, b):
    m, n = len(a), len(b)
    # 初始化动态规划表
    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):
            cost = 0 if a[i - 1] == b[j - 1] else 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]

# 示例
a = "kitten"
b = "sitting"
distance = levenshtein_distance(a, b)
print(f"'{a}' 和 '{b}' 的 Levenshtein 距离为: {distance}")

运行结果：

'kitten' 和 'sitting' 的 Levenshtein 距离为: 3

Levenshtein 距离的应用场景

1. 拼写纠错

   • Levenshtein 距离可用于计算用户输入与正确单词之间的相似度，从而推荐正确的单词。
   • 例如输入 "recieve"，通过计算与候选词的距离，可以推荐 "receive"。

2. 模糊匹配

   • 在数据库中模糊查找类似记录，比如搜索 "Jon" 时匹配 "John"。
   • 使用 Python 的 TheFuzz 库可以轻松实现。

3. 文本去重

   • 用于检测相似文本并去重，例如处理社交媒体内容或产品描述。

4. DNA 序列比对

   • Levenshtein 距离在生物信息学中也有重要应用，用于比较 DNA 或 RNA 序列的相似性。

使用 Python 库快速计算 Levenshtein 距离

除了手动实现外，我们还可以使用开源库 Levenshtein 或 TheFuzz 快速计算。

安装：

pip install python-Levenshtein

示例代码：

import Levenshtein

a = "kitten"
b = "sitting"
distance = Levenshtein.distance(a, b)
print(f"'{a}' 和 '{b}' 的 Levenshtein 距离为: {distance}")

结果：

'kitten' 和 'sitting' 的 Levenshtein 距离为: 3

总结

Levenshtein 距离是一种高效且实用的字符串相似度度量方法。通过动态规划算法实现，它在拼写纠错、模糊匹配和文本去重等领域得到了广泛应用。无论是从学习算法原理，还是通过现有库快速应用，Levenshtein 距离都能为开发者带来极大帮助。

其它

多个字符串比较的例子 （比较字符串（i love you ）和（love he））

我们利用动态规划的方式，逐步计算字符串 "i love you " 和 "love he " 的 Levenshtein 距离，以下是详细的过程。

1. 初始化动态规划表

假设：

• A="iloveyou"A = "i love you "（长度为 10，包括空格）
• B="lovehe"B = "love he "（长度为 8，包括空格）

动态规划表 dpdp 大小为 (10+1)×(8+1)=11×9(10+1) \times (8+1) = 11 \times 9。
初始状态如下：

• 第一行填充列索引（从空字符串到 B 的编辑距离）
• 第一列填充行索引（从空字符串到 A 的编辑距离）

2. 填充动态规划表

根据递归公式：

dp[i][j]=min⁡{dp[i−1][j]+1,删除dp[i][j−1]+1,插入dp[i−1][j−1]+cost,替换dp[i][j] = \min \begin{cases} dp[i-1][j] + 1, & \text{删除} \\ dp[i][j-1] + 1, & \text{插入} \\ dp[i-1][j-1] + \text{cost}, & \text{替换} \end{cases}

其中：

• 如果 A[i−1]=B[j−1]A[i-1] = B[j-1]，则 cost=0\text{cost} = 0，否则 cost=1\text{cost} = 1。

填充过程：

1. i=1,j=1i = 1, j = 1（比较 'i' 和 'l'）：

   • 插入：dp[1][0]+1=2dp[1][0] + 1 = 2
   • 删除：dp[0][1]+1=2dp[0][1] + 1 = 2
   • 替换：dp[0][0]+1=1dp[0][0] + 1 = 1
     所以 dp[1][1]=1dp[1][1] = 1。

2. i=1,j=2i = 1, j = 2（比较 'i' 和 'o'）：

   • 插入：dp[1][1]+1=2dp[1][1] + 1 = 2
   • 删除：dp[0][2]+1=3dp[0][2] + 1 = 3
   • 替换：dp[0][1]+1=2dp[0][1] + 1 = 2
     所以 dp[1][2]=2dp[1][2] = 2。

... 依此类推。

最终动态规划表填充完成后如下：

3. 结果

表格右下角的值 dp[10][8]=5dp[10][8] = 5，表示将 "i love you " 转换为 "love he " 需要 5次编辑操作。

4. 操作过程

通过回溯动态规划表，我们可以得到具体的编辑操作：

1. 删除 'i'（从 'i love you ' 中删除第一个字符）
2. 替换 'y' 为 'h'
3. 替换 'o' 为 'e'
4. 删除 ' '（去掉额外的空格）
5. 删除 'u'

最终，得到字符串 "love he "。