600万行DataFrame高效计算Levenshtein编辑距离并去重

1. 换用高速编辑距离计算库 #

原代码里的纯Python实现Levenshtein速度极慢，直接换成RapidFuzz——这是个基于C++后端的模糊匹配库，单条计算速度能提几十上百倍，完全不是一个量级。
安装命令：pip install rapidfuzz

2. 用长度预判过滤无效计算 #

Levenshtein有个关键特性：两个字符串的编辑距离绝对不会小于它们长度差的绝对值。也就是说，如果两个句子长度差≥10，那它们的编辑距离肯定≥10，根本不用浪费时间计算。
先给数据加个长度列：

data_df["src_len"] = data_df["src_sents"].str.len()

3. 分组+单向遍历，避免重复计算 #

把句子按长度排序后，只在长度差小于10的范围内比较，而且只做单向遍历（比如只计算第i句和后面的句子，不回头算前面的），这样能把O(n²)的复杂度大幅降低。同时用集合记录要保留的索引，避免重复标记。

4. 可运行的优化代码 #

import pandas as pd
from rapidfuzz.distance import Levenshtein

# 设定编辑距离阈值
MAX_THRESHOLD = 10
# 新增句子长度列，用于快速过滤
data_df["src_len"] = data_df["src_sents"].str.len()
# 按长度排序，方便后续按长度范围筛选候选
data_df = data_df.sort_values("src_len").reset_index(drop=True)

# 初始化保留集合，默认保留所有行
keep_idx = set(data_df.index)

# 遍历每一行，只和后面符合长度条件的句子比较
for idx in range(len(data_df)):
    # 如果当前行已经被标记删除，直接跳过
    if idx not in keep_idx:
        continue
    
    current_sent = data_df.loc[idx, "src_sents"]
    current_len = data_df.loc[idx, "src_len"]
    
    # 筛选后续行中长度差小于阈值的句子
    len_mask = (data_df["src_len"] >= current_len - MAX_THRESHOLD) & (data_df["src_len"] <= current_len + MAX_THRESHOLD)
    candidates = data_df.loc[idx+1:, len_mask]
    
    if candidates.empty:
        continue
    
    # 批量计算当前句和所有候选句的编辑距离
    distances = [Levenshtein.distance(current_sent, sent) for sent in candidates["src_sents"]]
    # 找出距离≤阈值的候选行索引
    to_remove = candidates.index[pd.Series(distances) <= MAX_THRESHOLD]
    # 从保留集合中移除这些索引
    keep_idx.difference_update(to_remove)

# 生成去重后的最终DataFrame
filtered_df = data_df.loc[list(keep_idx)].drop(columns=["src_len"])

5. 进阶优化方向 #

如果600万行数据单进程处理还是慢，可以试试：

• 分块处理：把数据分成若干块，先在块内去重，再跨块比较
• 并行计算：用multiprocessing.Pool把候选句子分成多份，并行计算编辑距离

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