如何通过Python标准库difflib.ndiff正确计算Levenshtein编辑距离？

你的代码只统计了difflib.ndiff输出中的删除操作（-），完全忽略了插入（+）和替换操作的正确计数逻辑，这是结果错误的核心原因。以下是两种基于Python标准库的可靠实现：

方案1：正确解析ndiff输出 #

ndiff的输出中，连续的-和+对应字符替换（应计1次编辑），单独的-是删除、单独的+是插入（各计1次）。遍历结果时需成对处理替换操作：

import difflib

def calculate_edit_distance(a, b):
    diff_list = list(difflib.ndiff(a, b))
    distance = 0
    idx = 0
    while idx < len(diff_list):
        current_op = diff_list[idx]
        if current_op[0] == '-':
            # 检查是否是替换操作（下一个为+）
            if idx + 1 < len(diff_list) and diff_list[idx+1][0] == '+':
                distance += 1
                idx += 2
            else:
                distance += 1
                idx += 1
        elif current_op[0] == '+':
            distance += 1
            idx += 1
        else:
            # 匹配的字符（空格开头），跳过
            idx += 1
    return distance

# 测试示例
print(calculate_edit_distance("split", "sitting"))  # 输出6

方案2：使用SequenceMatcher.get_opcodes（推荐） #

SequenceMatcher的get_opcodes()方法直接返回结构化的匹配操作序列，无需手动解析文本格式，逻辑更清晰，适合批量处理：

import difflib

def levenshtein_distance(a, b):
    matcher = difflib.SequenceMatcher(None, a, b)
    total_distance = 0
    for tag, i_start, i_end, j_start, j_end in matcher.get_opcodes():
        if tag == 'replace':
            # 替换操作：取两个子串的最大长度，对应替换+插入/删除的组合
            total_distance += max(i_end - i_start, j_end - j_start)
        elif tag == 'delete':
            total_distance += i_end - i_start
        elif tag == 'insert':
            total_distance += j_end - j_start
        # 'equal'操作不产生编辑距离，直接跳过
    return total_distance

# 测试示例
print(levenshtein_distance("split", "sitting"))  # 输出6

方案2的优势在于操作类型明确，无需处理ndiff的文本格式细节，运行效率和准确性更有保障，适合你大量字符串对比的场景。

内容的提问来源于stack exchange，提问作者sudoer