17万级字符串列表全组合相似度计算的线性时间实现问询

首先明确：如果需要计算所有两两元素的相似度得分，不可能做到严格线性时间复杂度——因为仅结果的数量就是O(n²)（17万元素对应2.89e10个组合），光存储这些结果就需要数百GB内存，完全不现实。你的原方案核心问题是O(n²)的计算量+纯Python实现的低效，下面给出针对性优化思路和替代方案：

一、大幅降低全量比对的计算耗时 #

如果确实需要全量结果（仅推荐小数据场景），可以通过以下手段压缩计算量：

1. 替换为RapidFuzz加速计算 #

FuzzyWuzzy是纯Python实现，速度极慢；RapidFuzz是其C++重写版本，速度提升50-100倍，API完全兼容。

2. 利用对称性减少重复计算 #

fuzz.partial_ratio是对称的（即partial_ratio(A,B) = partial_ratio(B,A)），只需计算上三角矩阵的结果，再复用给下三角，减少一半计算量。

3. 去重后计算，再映射回原列表 #

如果列表中有重复字符串，只计算一次唯一字符串的相似度，再批量赋值给原列表的重复实例，避免重复计算。

示例代码：

%%time
from rapidfuzz import fuzz
import pandas as pd

# 提取原列表并去重
lista = data_min.doc_std_name.to_list()
unique_strings = list(set(lista))
str_to_idx = {s: idx for idx, s in enumerate(unique_strings)}

# 预计算唯一字符串的两两相似度（利用对称性）
sim_matrix = {}
total_unique = len(unique_strings)
for i in range(total_unique):
    s1 = unique_strings[i]
    # 只计算i<=j的组合，复用结果给j<=i
    for j in range(i, total_unique):
        s2 = unique_strings[j]
        score = fuzz.partial_ratio(s1, s2)
        sim_matrix[(i, j)] = score
        sim_matrix[(j, i)] = score

# 映射回原列表的所有组合
fuzzy_match = {}
for s1 in lista:
    idx1 = str_to_idx[s1]
    for s2 in lista:
        idx2 = str_to_idx[s2]
        fuzzy_match[f"{s1}_vs_{s2}"] = sim_matrix[(idx1, idx2)]

二、更现实的替代方案：按需计算（而非全量比对） #

17万元素的全量比对完全不具备可行性，建议重新梳理需求，采用以下更高效的方案：

1. 只保留高相似度的组合 #

设置得分阈值，仅计算并存储相似度高于阈值的组合，避免无效计算：

%%time
from rapidfuzz import process, fuzz
import pandas as pd

lista = data_min.doc_std_name.to_list()
unique_strings = list(set(lista))
fuzzy_match_filtered = {}

# 只保留相似度>=80的组合
score_threshold = 80
for s1 in unique_strings:
    # 批量获取所有符合阈值的相似元素
    matches = process.extract(
        s1,
        unique_strings,
        scorer=fuzz.partial_ratio,
        score_cutoff=score_threshold,
        workers=-1  # 启用多CPU核心加速
    )
    for s2, score in matches:
        fuzzy_match_filtered[f"{s1}_vs_{s2}"] = score

2. 每个元素仅保留Top N相似元素 #

如果只需要每个元素的最相似k个结果，用process.extract_batch批量处理，时间复杂度接近O(n)（取决于候选数）：

%%time
from rapidfuzz import process, fuzz
import pandas as pd

lista = data_min.doc_std_name.to_list()
unique_strings = list(set(lista))

# 批量获取每个元素的Top5相似结果
top_n = 5
results = process.extract_batch(
    lista,
    unique_strings,
    scorer=fuzz.partial_ratio,
    limit=top_n,
    workers=-1
)

# 整理为字典格式
fuzzy_match_top = {}
for s, matches in zip(lista, results):
    fuzzy_match_top[s] = [(match, score) for match, score, _ in matches]

三、核心结论 #

• 全量两两比对的O(n²)复杂度无法规避，但可以通过去重、对称性、加速库将计算时间压缩到可接受范围（仅当n较小时）；
• 对于17万级别的数据，全量比对完全不现实，必须通过阈值过滤或Top N检索的方式减少计算量；
• RapidFuzz是提升计算速度的关键，务必替换FuzzyWuzzy。

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