performance - 使用 minhash 算法的 Piriwse Jaccard 相似度

Question

我正在处理 200k 个句子，我想使用 minhash 算法找到 Jaccard 相似度。但由于两个 for 循环，它变得非常慢。有人可以建议我一些好的实施吗？

以下是我当前的代码

from datasketch.minhash import MinHash

def eg1(data1, data2):
    m1 = MinHash()
    m2 = MinHash(enter code here)
    for d in data1:
        m1.update(d.encode('utf8'))
    for d in data2:
        m2.update(d.encode('utf8'))
    return m1.jaccard(m2)

jac_sim = []
for i_doc in range(len(shingles)-1):
    for j_doc in range(i_doc + 1, len(shingles)):
        jaccard_similarity = eg1(shingles[i_doc], shingles[j_doc])
        jac_sim.append(jaccard_similarity)

Answer 1

问题是 MinHash 会为相同的输入计算多次。通过只计算一次 MinHash 签名，您应该能够节省大量时间：

signatures = []
for i_doc in range(len(shingles)):
    m = MinHash()
    for d in shingles[i_doc]:
        m.update(d.encode('utf8'))
    signatures.append(m)

jac_sim = []    
for i_doc in range(len(shingles)-1):
    for j_doc in range(i_doc + 1, len(shingles)):
        jaccard_similarity = signatures[i_doc].jaccard(signatures[j_doc])
        jac_sim.append(jaccard_similarity)