你能否用一个文本纠错案例展示编辑距离算法的应用

访客自然语言处理 2026-06-05 00:22:49 1

本文目录导读：

示例
输出: [('kitten', 1), ('sitting', 2), ('fitting', 2)]

我来用一个具体的文本纠错案例来展示编辑距离（Levenshtein Distance）算法的应用。

案例场景

假设用户输入了错误的单词 "kitten"（正确应为 "sitting"），我们想计算编辑距离,了解它们有多相似。

编辑距离定义

从一个字符串转换为另一个字符串所需的最少编辑操作次数,操作包括：

插入：插入一个字符
删除：删除一个字符
替换：替换一个字符

案例演示

# 计算 "kitten" 到 "sitting" 的编辑距离
原始词：kitten  (长度6)
目标词：sitting (长度7)
编辑操作步骤：
1. 将 'k' 替换为 's'  →  sitten
2. 将 'e' 替换为 'i'  →  sittin
3. 在末尾插入 'g'     →  sitting
编辑距离 = 3 次操作

Python代码实现

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    # 创建DP表
    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
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i-1] == s2[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]
# 测试
word1 = "kitten"
word2 = "sitting"
distance = levenshtein_distance(word1, word2)
print(f"'{word1}' 到 '{word2}' 的编辑距离: {distance}")

DP表可视化

        ''  s  i  t  t  i  n  g
    ''   0  1  2  3  4  5  6  7
    k    1  1  2  3  4  5  6  7
    i    2  2  1  2  3  4  5  6
    t    3  3  2  1  2  3  4  5
    t    4  4  3  2  1  2  3  4
    e    5  5  4  3  2  2  3  4
    n    6  6  5  4  3  3  2  3

实际应用场景

拼写检查器

def spell_check(word, dictionary):
 suggestions = []
 for correct_word in dictionary:
     distance = levenshtein_distance(word.lower(), correct_word.lower())
     if distance <= 2:  # 只建议编辑距离<=2的单词
         suggestions.append((correct_word, distance))
 # 按编辑距离排序
 suggestions.sort(key=lambda x: x[1])
 return suggestions[:5]  # 返回最相似的5个

示例

dictionary = ["sitting", "kitten", "bitten", "mittens", "fitting"] result = spell_check("kittin", dictionary) print("拼写建议:", result)

输出: [('kitten', 1), ('sitting', 2), ('fitting', 2)]


2. **自动纠错系统**
```python
def auto_correct(input_word, dictionary):
    if input_word in dictionary:
        return input_word  # 正确拼写
    suggestions = spell_check(input_word, dictionary)
    if suggestions:
        return suggestions[0][0]  # 返回最佳建议
    return input_word
# 测试
print(auto_correct("kittin", dictionary))  # 输出: kitten
print(auto_correct("sitten", dictionary))  # 输出: sitting

这个案例展示了编辑距离算法在文本纠错中的核心应用：