如何降低Python中行式相似度比较的计算与存储负担？

现有如下DataFrame：

message
0       ABC
1       abc
2       cba
3      abcd
4      dcsa
5      adcd
6      abcd
7       cba                   

需求是对每行文本执行相似度比较，最终基于相似度向量分组计算指标。当前采用暴力法：每行与所有行（含自身）比较，相似度达标记1，否则记0，生成长度为N的相似度向量，复杂度为O(N²)。该方法仅适用于小数据集，无法适配百万级规模数据（每行需存储百万级向量，存储和计算成本极高）。

现寻求以下两个问题的解决方案：

1. 如何降低O(N²)的计算复杂度？目前尝试对message列排序后缩小比较范围，但会导致各行列的相似度向量长度不一致，无法直接用于分组。
2. 是否有更高效的相似度信息存储方式？因分组需求必须保留关联信息，能否用其他方式替代全量相似度向量？

可复现最小示例 #

import pandas as pd
from difflib import SequenceMatcher

df = pd.DataFrame({'message': ['ABC', 'ABCD', 'DCBA', 'abcde', 'CBDA', 'abcde', 'edcba']})

def similarity_score(s1, s2):
    coef = SequenceMatcher(None, s1, s2).ratio()
    return 1 if coef >= 0.75 else 0

def similarity(x, df):
    sim_score = []
    for i in df['message']:
        sim_score.append(similarity_score(x, i))
    return sim_score

df['similarity'] = df['message'].apply(lambda x: similarity(x, df)).astype(str)

需求动机示例（含cnt字段分组汇总） #

代码实现 #

import pandas as pd
from difflib import SequenceMatcher

df = pd.DataFrame({'message': ['ABC','abc','cba','abcd','dcsa','adcd','abcd','cba'], 
                  'cnt': [1, 2, 3, 4, 5, 6, 7, 8]})

def similarity_score(s1, s2):
    coef = SequenceMatcher(None, s1, s2).ratio()
    return 1 if coef >= 0.80 else 0

def similarity(x,df):
    sim_score = []
    for i in df['message']:
        sim_score.append(similarity_score(x, i))
    return sim_score

df['similarity'] = df['message'].apply(lambda x: similarity(x, df)).astype(str)
df["group"] = pd.factorize(df["similarity"].astype(str))[0] + 1
print(df)

输出结果 #

message  cnt         similarity  group
0     ABC    1  [1, 0, 0, 0, 0, 0, 0, 0]      1
1     abc    2  [0, 1, 0, 1, 0, 0, 1, 0]      2
2     cba    3  [0, 0, 1, 0, 0, 0, 0, 1]      3
3    abcd    4  [0, 1, 0, 1, 0, 0, 1, 0]      2
4    dcsa    5  [0, 0, 0, 0, 1, 0, 0, 0]      4
5    adcd    6  [0, 0, 0, 0, 0, 1, 0, 0]      5
6    abcd    7  [0, 1, 0, 1, 0, 0, 1, 0]      2
7     cba    8  [0, 0, 1, 0, 0, 0, 0, 1]      3

按group汇总cnt #

df_final = df.groupby("group").sum("cnt")
print(df_final)

汇总输出 #

cnt
group     
1        1
2       13
3       11
4        5
5        6

解决方案 #

问题1：降低O(N²)复杂度 #

核心思路是避免全量两两比较，通过文本特征预分组+组内精细比较的方式减少计算量：

• 文本特征哈希/聚类前置：先对文本提取低维特征（如n-gram哈希、TF-IDF向量、Sentence-BERT嵌入），用近似最近邻（ANN）算法（如FAISS、Annoy）快速找到候选相似文本，仅与候选集比较，而非全量数据，复杂度可降至O(N*logN)。
• 基于文本属性过滤：先按文本长度分组，仅在相同/相近长度的组内做相似度比较（比如长度差≤2的文本才可能达到0.8以上的SequenceMatcher相似度），直接排除大量不可能达标的文本。
• 排序后滑动窗口比较：对文本按字典序排序后，仅在滑动窗口内（如前后100行）做比较，同时记录原始索引，最后映射回原数据生成统一长度的相似度向量（未比较的行标记为0）。

问题2：替代全量相似度向量的存储与分组方式 #

不需要存储全量0-1向量，可通过等价类分组直接实现相同的分组效果：

• 连通分量分组：将相似度达标（≥阈值）的文本对视为图中的边，文本作为节点，用Union-Find（并查集）算法找出所有连通分量，同一个连通分量的文本即为同一组。这种方式仅需记录每个节点的根节点，存储复杂度为O(N)，结合问题1的候选集优化可避免全量建边。
• 特征哈希分组：对文本提取稳定的相似特征（如归一化后的n-gram集合、去重排序后的字符序列），将相同特征的文本归为一组。比如把"abc"和"cba"转为小写后排序字符得到"abc"，直接按该特征分组。
• 聚类标签替代向量：用文本嵌入做聚类（如K-Means、DBSCAN），聚类标签直接作为分组依据，无需存储相似度向量。若需要更精细的分组，可在聚类簇内再做相似度过滤调整。

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