用Python实战Levenshtein距离：从算法到拼写纠错工具

在文本处理的世界里，两个字符串有多"相似"是个常见问题。无论是搜索引擎的"你是不是要找..."提示，还是手机键盘输入时的自动修正，背后都藏着一个优雅的算法——Levenshtein距离。作为编辑距离的一种，它量化了将一个字符串变成另一个所需的最少单字符编辑操作次数（插入、删除或替换）。不同于死记硬背动态规划的理论，我们将用Python一步步构建可运行的Levenshtein计算器，并最终打造一个迷你拼写建议系统。

1. Levenshtein距离的核心思想

想象你在打字时不小心把"kitten"输成了"sitting"。计算它们的Levenshtein距离，就是找出最少需要多少步操作能把"sitting"变成"kitten"：

1. s itting → k itting（替换's'为'k'）
2. kitt i ng → kitt e ng（替换'i'为'e'）
3. kitte n g → kitte n （删除最后的'g'）

总共3次操作，因此这两个词的Levenshtein距离为3。这种直观的理解正是动态规划解法的基础——将大问题分解为更小的子问题。

1.1 动态规划矩阵解析

我们用一个二维矩阵 dp 来表示状态，其中 dp[i][j] 表示字符串A的前i个字符和字符串B的前j个字符之间的编辑距离。矩阵的填充规则如下：

初始化：
dp[i][0] = i  # 将A前i个字符变为空串需要i次删除
dp[0][j] = j  # 将空串变为B前j个字符需要j次插入

状态转移方程：
if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1]  # 字符相同，无需操作
else:
    dp[i][j] = min(
        dp[i-1][j] + 1,    # 删除A[i]
        dp[i][j-1] + 1,    # 插入B[j]
        dp[i-1][j-1] + 1   # 替换A[i]为B[j]
    )

以"cat"和"cars"为例，其DP矩阵的构建过程如下：

	''	c	a	r	s
''	0	1	2	3	4
c	1	0	1	2	3
a	2	1	0	1	2
t	3	2	1	1	2

注意：矩阵右下角的值2即为最终编辑距离。路径显示最优操作为：替换't'→'s'，插入'r'。

2. Python实现基础版本

让我们从最直接的实现开始，逐步优化。这个基础版本清晰地反映了算法逻辑：

def levenshtein_distance(str1, str2):
    m, n = len(str1), len(str2)
    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):
            if str1[i-1] == str2[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]

# 测试用例
print(levenshtein_distance("kitten", "sitting"))  # 输出: 3
print(levenshtein_distance("flaw", "lawn"))      # 输出: 2

2.1 空间复杂度优化

基础版本需要O(m*n)的空间，当处理长文本时可能成为瓶颈。观察发现，我们其实只需要前一行和当前行的数据：

def levenshtein_distance_optimized(str1, str2):
    if len(str1) < len(str2):
        return levenshtein_distance_optimized(str2, str1)
    
    m, n = len(str1), len(str2)
    previous_row = list(range(n + 1))
    
    for i, ch1 in enumerate(str1, 1):
        current_row = [i]
        for j, ch2 in enumerate(str2, 1):
            cost = 0 if ch1 == ch2 else 1
            current_row.append(min(
                previous_row[j] + 1,
                current_row[j-1] + 1,
                previous_row[j-1] + cost
            ))
        previous_row = current_row
    
    return previous_row[-1]

这种优化将空间复杂度降到了O(min(m,n))，在处理类似DNA序列等长字符串时尤其重要。

3. 构建拼写纠错系统

有了核心算法，我们可以创建一个简单的拼写建议系统。系统工作流程如下：

1. 加载词典（英文单词列表）
2. 对于输入的错误单词，计算与词典中所有单词的Levenshtein距离
3. 返回距离最小的N个单词作为建议

from collections import defaultdict
import heapq

class SpellChecker:
    def __init__(self, dictionary_file="words.txt"):
        with open(dictionary_file) as f:
            self.words = [word.strip().lower() for word in f]
    
    def get_suggestions(self, word, k=5):
        """返回前k个最接近的正确拼写"""
        word = word.lower()
        suggestions = []
        
        for correct_word in self.words:
            distance = levenshtein_distance_optimized(word, correct_word)
            heapq.heappush(suggestions, (distance, correct_word))
        
        return [word for (dist, word) in heapq.nsmallest(k, suggestions)]

# 使用示例
checker = SpellChecker()
print(checker.get_suggestions("acomodate"))  
# 可能输出: ['accommodate', 'accommodated', 'accommodates', 'commodate', 'accompanied']

3.1 性能优化技巧

直接计算与所有词典单词的距离效率低下，我们可以采用以下优化：

1. 预先计算单词长度 ：只计算与输入单词长度相差不超过δ的单词
2. BK树数据结构 ：专门为编辑距离搜索设计的数据结构
3. 多线程处理 ：并行计算不同单词区间的距离

优化后的版本可能如下：

from bisect import bisect_left

class OptimizedSpellChecker(SpellChecker):
    def __init__(self, dictionary_file="words.txt"):
        super().__init__(dictionary_file)
        self.length_index = defaultdict(list)
        for word in self.words:
            self.length_index[len(word)].append(word)
        # 对每个长度列表排序以便二分查找
        for length in self.length_index:
            self.length_index[length].sort()
    
    def get_suggestions(self, word, k=5, delta=2):
        word = word.lower()
        n = len(word)
        candidates = []
        
        # 只检查长度在[n-delta, n+delta]范围内的单词
        for length in range(max(1, n - delta), n + delta + 1):
            if length in self.length_index:
                candidates.extend(self.length_index[length])
        
        suggestions = []
        for correct_word in candidates:
            distance = levenshtein_distance_optimized(word, correct_word)
            if len(suggestions) < k:
                heapq.heappush(suggestions, (-distance, correct_word))
            else:
                heapq.heappushpop(suggestions, (-distance, correct_word))
        
        return [word for (neg_dist, word) in sorted(suggestions, reverse=True)]

4. 进阶应用与扩展

Levenshtein距离的应用远不止拼写检查：

4.1 模糊字符串匹配

在数据清洗中，经常需要处理拼写不一致的记录：

def fuzzy_match(query, choices, threshold=2):
    """返回所有编辑距离小于threshold的选项"""
    return [choice for choice in choices 
            if levenshtein_distance_optimized(query, choice) <= threshold]

company_names = ["Microsoft", "Microsft", "Apple", "Aple", "Google", "Googl"]
print(fuzzy_match("Microsft", company_names))
# 输出: ['Microsoft', 'Microsft']

4.2 加权编辑距离

不同编辑操作可以赋予不同权重，例如：

• 键盘相邻键的替换代价更低
• 元音字母间的替换代价更低

def weighted_levenshtein(str1, str2, insertion_cost=1, deletion_cost=1, substitution_cost=1):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i * deletion_cost
    for j in range(n + 1):
        dp[0][j] = j * insertion_cost
    
    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] + deletion_cost,
                    dp[i][j-1] + insertion_cost,
                    dp[i-1][j-1] + substitution_cost
                )
    
    return dp[m][n]

# 示例：认为元音替换代价更低
def vowel_aware_cost(a, b):
    vowels = {'a', 'e', 'i', 'o', 'u'}
    if a != b and {a.lower(), b.lower()}.issubset(vowels):
        return 0.5  # 元音间替换代价更低
    return 1

print(weighted_levenshtein("color", "colour", substitution_cost=0.8))  # 输出: 0.8

4.3 相似度百分比

将编辑距离转换为更直观的相似度评分：

def similarity_percentage(str1, str2):
    distance = levenshtein_distance_optimized(str1, str2)
    max_len = max(len(str1), len(str2))
    if max_len == 0:
        return 100.0
    return (1 - distance / max_len) * 100

print(f"{similarity_percentage('kitten', 'sitting'):.1f}%")  # 输出: 57.1%

在实际项目中，将这些技术组合使用往往能获得最佳效果。比如在构建搜索引擎时，可以先用拼写纠正处理查询词，再用模糊匹配扩展搜索结果，最后按相似度排序返回给用户。