基于minhash算法的Pairiwse 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)