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

Question

lst_train 中大约有 98,000 句话（长度在 5 - 100 个单词之间），lst_test 中则有约 1000 句话（长度在 5 - 100 个单词之间）。对于 lst_test 中的每个句子，我想找出它是否从 lst_train 中的某个句子剽窃而来。如果被剽窃，我应该返回在 lst_train 中的 id，否则返回 null。

现在，我想计算每个 lst_test 中的句子与 lst_train 中的每个句子之间的 Jaccard 相似度。下面是我的代码，其中 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中抄袭的问题吗？

- tktktk0711

---

基于文本的相似度度量非常缓慢。尝试将文本数据向量化并使用余弦相似度度量或一些基于它的方法。 - CrazyElf

嗨，@CrazyElf，感谢您的评论。现在我正在使用word2vec来做这件事。 - tktktk0711

Answer 1

更改方法可能会更好。Jaccard相似性并不是非常计算密集，但如果您必须对数据集中的每个元素进行计算，则任何非平凡的相似度计算都会变慢。

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

请注意，对于许多应用程序，将句子向量化并在向量空间中搜索接近的句子是有效的。然而，这是有效的，因为它能够理解同义词-由于您正在寻找抄袭，您正在寻找完全相同的副本，因此基于单词向量的方法可能会适得其反。

- polm23

---

感谢您的评论，我已经发送了电子邮件，请查收。 - tktktk0711

Answer 2

正如polm23所建议的，datasektch库非常适合您的任务。

GitHub repo显示了一个示例，其中使用datasketch提供的LSH实现计算文本文档之间的Jaccard相似度。

- Aviral