如何高效检测百万级字符串列表中编辑距离≤5的重复项？

针对60万条字符串找字符差异≤5的相似对问题，暴力组合比对完全不可行，以下是落地性极强的优化思路和实现：

1. 预处理：按长度快速过滤无效对 #

如果两个字符串长度差超过5，它们的字符差异数必然大于5（比如长度差6时，仅多出来的6个字符就会让差异数达标）。先按字符串长度分组，后续只在同长度组或长度差≤5的组内比对，直接砍掉90%以上的无效组合：

from collections import defaultdict

# 按字符串长度分组
str_by_len = defaultdict(list)
hash_list = df.hash.unique().tolist()
for s in hash_list:
    str_by_len[len(s)].append(s)

2. 先处理完全重复的字符串 #

用普通哈希表快速归并完全相同的字符串，这部分不需要计算差异，效率极高：

# 收集完全重复的字符串组
exact_duplicates = defaultdict(list)
for s in hash_list:
    exact_duplicates[s].append(s)

# 提取长度>1的重复组（即存在重复的字符串）
exact_groups = [group for group in exact_duplicates.values() if len(group) > 1]

3. 核心优化：分块倒排索引找候选对 #

利用鸽巢原理：两个差异≤5的字符串，若拆成6个块（差异阈值+1），则至少有一个块完全相同。基于这个逻辑，我们可以大幅减少需要比对的字符串数量：

• 把每个字符串拆成6个近似等长的块
• 为每个块建立倒排索引（键是块内容，值是包含该块的字符串集合）
• 对每个字符串，仅和共享任意一个块的候选字符串计算差异数

代码实现：

def split_into_blocks(s, num_blocks=6):
    """将字符串拆分为指定数量的近似等长块"""
    block_size = len(s) // num_blocks
    blocks = []
    for i in range(num_blocks):
        start = i * block_size
        # 最后一个块包含剩余所有字符，避免短字符串拆分出空块
        end = start + block_size if i != num_blocks - 1 else len(s)
        blocks.append(s[start:end])
    return blocks

# 构建块的倒排索引
block_index = defaultdict(set)
for s in hash_list:
    blocks = split_into_blocks(s)
    for block in blocks:
        block_index[block].add(s)

# 查找符合条件的相似对，自动去重
similar_pairs = set()
processed = set()

for s in hash_list:
    if s in processed:
        continue
    # 获取所有可能的候选字符串
    candidates = set()
    blocks = split_into_blocks(s)
    for block in blocks:
        candidates.update(block_index[block])
    # 移除自身和已处理过的字符串，避免重复比对
    candidates.discard(s)
    candidates -= processed
    # 对候选计算差异数，提前终止优化
    for candidate in candidates:
        len_diff = abs(len(s) - len(candidate))
        if len_diff > 5:
            continue
        diff_count = 0
        # 比对相同长度部分，差异超过5直接终止
        for a, b in zip(s, candidate):
            if a != b:
                diff_count += 1
                if diff_count > 5:
                    break
        diff_count += len_diff
        if diff_count <= 5:
            # 按字典序存储对，避免重复（如(s1,s2)和(s2,s1)只存一次）
            pair = tuple(sorted((s, candidate)))
            similar_pairs.add(pair)
    processed.add(s)

# 将完全重复的组转换为成对格式（按需调整）
for group in exact_groups:
    for i in range(len(group)):
        for j in range(i + 1, len(group)):
            pair = tuple(sorted((group[i], group[j])))
            similar_pairs.add(pair)

4. 进一步性能提升技巧 #

• 提前终止比对：计算差异数时，一旦超过5立刻停止遍历字符，节省时间
• 并行处理：将分组后的字符串列表拆分，用多进程并行处理候选对比对
• 快速差异计算：用numpy加速字节级比对，替代循环：

  import numpy as np
  
  def fast_diff_count(s1, s2):
      len_diff = abs(len(s1) - len(s2))
      if len_diff > 5:
          return float('inf')
      arr1 = np.frombuffer(s1.encode('utf-8'), dtype=np.uint8)
      arr2 = np.frombuffer(s2.encode('utf-8'), dtype=np.uint8)
      min_len = min(len(arr1), len(arr2))
      diff = np.sum(arr1[:min_len] != arr2[:min_len]) + len_diff
      return diff
  

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