如何计算100万条文章标题两两间的Levenshtein距离？

你的核心问题在于直接生成笛卡尔积会产生1万亿行数据，完全超出个人电脑的承载能力。下面给出几个可行的优化方案，从计算效率、内存占用两方面解决问题：

一、利用距离对称性减少计算量 #

Levenshtein距离满足对称性（即distance(a,b)=distance(b,a)），且自身与自身的距离为0。如果不需要重复存储对称结果，可只计算i < j的组合，将计算量从1e12降至约5e11，但这个量级对个人电脑依然压力巨大，需结合高效计算库和分块处理。

二、使用高效计算库替代纯Python实现 #

优先选择rapidfuzz（带C加速的模糊匹配库），它的Levenshtein计算速度比普通python-Levenshtein快数倍，且支持批量矩阵计算。

先安装依赖：

pip install rapidfuzz pandas scipy

三、分块处理+稀疏矩阵存储（推荐） #

如果你的需求是保留所有距离结果，直接存储1e6×1e6的密集矩阵需要约4TB内存（按每个int4字节计算），这显然不现实。改用稀疏矩阵只存储非零或符合阈值的结果，能大幅降低内存占用。

代码示例：分块计算+稀疏矩阵存储 #

import pandas as pd
from rapidfuzz.distance import Levenshtein
from scipy.sparse import lil_matrix
import numpy as np

# 读取数据
df = pd.read_csv('titles_dates_links.csv')
titles = df['title'].tolist()
total_titles = len(titles)

# 配置参数
chunk_size = 1000  # 每次处理的标题块大小，可根据内存调整
threshold = 3  # 可根据需求设置：只保留距离小于该值的结果（若要全部，设为极大值）

# 初始化稀疏矩阵
sparse_dist_matrix = lil_matrix((total_titles, total_titles), dtype=int)

# 分块遍历计算
for start_idx in range(0, total_titles, chunk_size):
    end_idx = min(start_idx + chunk_size, total_titles)
    current_chunk = titles[start_idx:end_idx]
    chunk_indices = np.arange(start_idx, end_idx)
    
    # 计算当前块与所有标题的Levenshtein距离矩阵
    dist_matrix = Levenshtein.distance_matrix(current_chunk, titles)
    
    # 筛选符合阈值的结果，填充稀疏矩阵
    for row_in_chunk, global_row_idx in enumerate(chunk_indices):
        # 找到当前行中距离小于阈值的列索引
        valid_cols = np.where(dist_matrix[row_in_chunk] < threshold)[0]
        sparse_dist_matrix[global_row_idx, valid_cols] = dist_matrix[row_in_chunk, valid_cols]
    
    print(f"完成块 {start_idx//chunk_size + 1} / {total_titles//chunk_size + 1}")

# 保存稀疏矩阵到文件（后续可通过scipy.sparse.load_npz加载）
sparse_dist_matrix.save('levenshtein_distances.npz')

四、如果仅需相似标题匹配（无需全量距离） #

若你的真实需求是找相似标题而非计算所有组合的距离，可先用近似最近邻算法快速缩小候选范围，再计算精确Levenshtein距离，计算量会骤降：

from annoy import AnnoyIndex
import numpy as np
from rapidfuzz.distance import Levenshtein

# 先将标题转换为向量（这里用简单的字符编码，也可使用预训练文本向量）
def title_to_vector(title):
    # 示例：取前100个字符的ASCII编码，不足补0
    vec = [ord(c) for c in title[:100]]
    return vec + [0]*(100 - len(vec))

title_vectors = np.array([title_to_vector(t) for t in titles])

# 构建Annoy索引
dim = 100
annoy_index = AnnoyIndex(dim, 'manhattan')
for i, vec in enumerate(title_vectors):
    annoy_index.add_item(i, vec)
annoy_index.build(10)  # 10棵树，平衡速度和精度

# 为每个标题找Top10相似候选
similar_pairs = set()
for i in range(total_titles):
    candidates = annoy_index.get_nns_by_item(i, 11)[1:]  # 排除自身
    for j in candidates:
        if i < j:  # 避免重复
            dist = Levenshtein.distance(titles[i], titles[j])
            similar_pairs.add((i, j, dist))

# 转换为DataFrame
similar_df = pd.DataFrame(similar_pairs, columns=['title_idx1', 'title_idx2', 'levenshtein_distance'])

关键注意事项 #

1. 预处理标题：先统一小写、去除标点、过滤停用词，能减少无效计算量。
2. 硬件优化：rapidfuzz默认支持多线程，可充分利用CPU多核。
3. 计算时间：即使分块，1e6条标题的全量计算仍需数十小时，需做好耗时准备。

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