如何高效删除Pandas DataFrame中Levenshtein距离过近的行？

原实现的问题分析 #

你原来的代码确实存在几个关键的效率问题：

• 双重iterrows()循环属于**O(n²)**时间复杂度，当DataFrame行数较多（比如上千条）时，速度会断崖式下降；
• 循环中直接用inplace=True修改DataFrame，会导致迭代过程中索引混乱，很容易出现漏删、误删的情况；
• 重复计算了大量相似度（比如text1和text2的相似度与text2和text1的相似度完全一致），做了很多无用功。

更高效的实现思路 #

核心方向是：避免重复计算，通过聚类/分组逻辑把相似度高的文本归为一组，每组仅保留一条（比如第一条或最具代表性的条目）。下面提供几种适配不同数据规模的方案：

方案1：用fuzzywuzzy结合聚类（适合中小规模数据）

fuzzywuzzy的process模块可以快速定位相似文本，搭配简单的聚类逻辑就能批量处理：

from fuzzywuzzy import fuzz, process
import pandas as pd

def remove_near_duplicates(df, text_col='text', threshold=90):
    # 先删除完全重复的文本，减少后续计算量
    df_unique = df.drop_duplicates(subset=text_col).reset_index(drop=True)
    texts = df_unique[text_col].tolist()
    
    keep_indices = []
    processed = set()
    
    for i, text in enumerate(texts):
        if i not in processed:
            # 找出所有相似度达标文本的索引
            matches = process.extract(text, texts, scorer=fuzz.ratio, limit=None)
            close_indices = [idx for idx, score, _ in matches if score >= threshold]
            # 保留当前条目，标记同组其他条目为已处理
            keep_indices.append(i)
            processed.update(close_indices)
    
    return df_unique.loc[keep_indices].reset_index(drop=True)

# 使用示例
cleaned_df = remove_near_duplicates(your_dataframe, threshold=90)

这个方案实现简单，不需要复杂的向量转换，适合数据量在1万条以内的场景。

方案2：用sklearn近邻算法+编辑距离（适合中等规模数据）

如果数据量更大，可以结合K近邻算法减少重复计算，只针对候选文本精确计算Levenshtein距离：

from sklearn.neighbors import NearestNeighbors
import numpy as np
import Levenshtein

def levenshtein_distance(x, y):
    # 转换为距离值（1 - 相似度），适配sklearn的近邻逻辑
    return 1 - Levenshtein.ratio(x, y)

def get_keep_indices(texts, threshold=0.1):
    # threshold=0.1 等价于 相似度>=0.9
    n = len(texts)
    # 用自定义编辑距离初始化近邻模型
    knn = NearestNeighbors(n_neighbors=n, metric=levenshtein_distance)
    knn.fit(np.arange(n).reshape(-1, 1))
    
    keep = []
    visited = set()
    
    for i in range(n):
        if i not in visited:
            distances, indices = knn.kneighbors([[i]])
            # 筛选出距离达标（相似度足够高）的条目索引
            close_indices = indices[0][distances[0] <= threshold]
            keep.append(i)
            visited.update(close_indices)
    
    return keep

# 使用示例
df_unique = df.drop_duplicates(subset='text').reset_index(drop=True)
keep_idx = get_keep_indices(df_unique['text'].tolist(), threshold=0.1)
cleaned_df = df_unique.loc[keep_idx].reset_index(drop=True)

这个方案通过KNN缩小了需要计算相似度的范围，适合数据量在1-10万条的场景。

方案3：用近似搜索库（适合大规模数据）

如果数据量超过10万条，推荐用annoy这类专门的近似搜索库，先通过字符n-gram向量快速定位候选文本，再精确验证Levenshtein相似度：

from annoy import AnnoyIndex
import numpy as np
from sklearn.feature_extraction.text import CountVectorizer
import Levenshtein

def ngram_vectorize(texts, ngram_range=(2,3)):
    # 把文本转换成字符n-gram向量，用于近似搜索
    vec = CountVectorizer(analyzer='char', ngram_range=ngram_range)
    return vec.fit_transform(texts).toarray()

def find_near_duplicates_annoy(texts, threshold=0.9, n_trees=10):
    vectors = ngram_vectorize(texts)
    dim = vectors.shape[1]
    
    # 构建Annoy索引
    idx = AnnoyIndex(dim, metric='angular')
    for i, vec in enumerate(vectors):
        idx.add_item(i, vec)
    idx.build(n_trees)
    
    keep = []
    visited = set()
    
    for i in range(len(texts)):
        if i not in visited:
            # 先通过Annoy快速找到候选相似文本，再精确计算Levenshtein相似度
            candidates = idx.get_nns_by_item(i, len(texts), include_distances=False)
            close_matches = [j for j in candidates if Levenshtein.ratio(texts[i], texts[j]) >= threshold]
            keep.append(i)
            visited.update(close_matches)
    
    return keep

# 使用示例
df_unique = df.drop_duplicates(subset='text').reset_index(drop=True)
keep_idx = find_near_duplicates_annoy(df_unique['text'].tolist(), threshold=0.9)
cleaned_df = df_unique.loc[keep_idx].reset_index(drop=True)

这个方案能大幅减少精确计算的次数，适合百万级别的大规模数据处理。

额外优化建议 #

1. 先做完全重复文本去重：用df.drop_duplicates(subset='text')先删掉完全一致的文本，直接减少后续计算量；
2. 过滤短文本：对长度过短的文本（比如小于3个字符）单独处理，因为Levenshtein相似度对短文本的判断容易出现偏差；
3. 灵活调整阈值：0.9是比较严格的标准，可以根据业务需求上下浮动（比如0.85或0.95）。

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