Python：如何更快地计算 Jaccard 相似度

Question

中大约有 98,000 个句子（长度从 5 - 100 个单词）lst_train，而 中大约有 1000 个句子（长度从 5 - 100 个单词）lst_test。对于 中的每个句子，lst_test我想查找它是否抄袭了 中的句子lst_train。如果这个句子是抄袭的，我应该返回 lst_train 中的 id，否则返回 null。

现在我想计算 中每个句子相lst_test对于 中每个句子的杰卡德相似度lst_train。这是我的代码，b.JaccardSim 计算两个句子的 jaccard 相似度：

lst_all_p = []
for i in range(len(lst_test)):
    print('i:', i)
    lst_p = []
    for j in range(len(lst_train)):
        b = textSimilarity.TextSimilarity(lst_test[i], lst_train[j])
        lst_p.append(b.JaccardSim(b.str_a,b.str_b))
    lst_all_p.append(lst_p)

但我发现lst_train中每一句话计算一次的时间都超过1分钟。由于大约有1000个句子，所以可能需要大约1000分钟才能完成。太长了。

你们知道如何使计算速度更快或更好的方法来解决检测 lst_train 中句子抄袭的问题吗？

Answer 1

改变你的方法可能会更好。Jaccard 相似度的计算量并不是很大，但如果您必须对数据集中的每个元素都执行此操作，那么任何重要的相似度计算都会很慢。

如果您想发现抄袭，您应该研究近重复检测和局部敏感哈希。 MinHash和SimHash是很好的起点，datasketch库也可能有帮助。

请注意，对于许多应用程序来说，向量化句子并在向量空间中搜索接近的句子是有效的。然而，这是有效的，因为它能够理解同义词 - 因为您正在寻找抄袭，所以您正在寻找精确的副本，因此基于词向量的方法最终可能会违背您的目标。