duplicates - 如何用 Simhash 算法比较文档的相似度？

Question

我目前正在创建一个程序，可以在文本文档(+5000 个文档)的语料库中计算近似重复的分数。我正在使用 Simhash 生成文档的 uniq 足迹(感谢 github repo)

我的数据是:

data = {
    1: u'Im testing simhash algorithm.',
    2: u'test of simhash algorithm',
    3: u'This is simhash test.',
}

这给了我 3 个这样的哈希:

001001101011101000111110001000100101010110010000011100001110010111001101010011011110101000100010110010110001100001001101010101

000010011100100000000110000010001100100010100001010100000011000001001000111001001100101000000100000001100010010101010000010p>

1000111010110000010010101000001001000101101000100000000010100010110000110010000011001100000001100100000000011000000100110p>

现在，如何比较这 3 个哈希值？我知道我必须将它们分成 block 但没有确切的方法？

我想要做的是输出所有重复文档 (>70%) 及其 ID 和重复文档的 ID。

有人可以帮忙吗？

Answer 1

在回答您的问题之前，请务必记住:

1. Simhash 非常有用，因为它可以检测附近的重复项。这意味着接近重复的结果将具有相同的哈希值。
2. 对于精确重复，您可以简单地使用任何一种方式，一致的散列机制(例如 md5)
3. 您在此处粘贴的示例太小，考虑到它们的大小，它们之间的差异很大。该算法专为处理大型 Web 文档而不是小句子而设计。

现在，我已经回复了您提出的关于 Github 问题的问题 here .

不过，作为引用，这里有一些示例代码，您可以使用它们在散列后打印最终的近乎重复的文档。

# assuming that you have a dictionary with document id as the key and the document as the value: 
# documents = { doc_id: doc } you can do:

from simhash import simhash

def split_hash(str, num):
    return [ str[start:start+num] for start in range(0, len(str), num) ]

hashes = {}
for doc_id, doc in documents.items():
    hash = simhash(doc)
    
    # you can either use the whole hash for higher precision or split into chunks for higher recall
    hash_chunks = split_hash(hash, 4)
    
    for chunk in hash_chunks:
        if chunk not in hashes:
            hashes[chunk] = []
        hashes[chunk].append(doc_id)

# now you can print the duplicate documents:
for hash, doc_list in hashes:
    if len(doc_list) > 1:  # if the length of doc is greater than 1
        print("Duplicates documents: ", doc_list)

如果有什么不清楚的地方请告诉我。