如何将文档相似度与Simhash算法进行比较？

Question

我目前正在创建一个程序，它可以在文本文档(+5000文档)的语料库中计算近乎重复的分数。我使用Simhash生成文档的uniq足迹(多亏了这个github回购)

我的数据是：

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

这给了我3个像这样的哈希：

00100110101110100011111000100010010101011001000001110000111001011100110101001101111010100010001011001011000110000100110101100110

00001001110010000000011000001000110010001010000101010000001100000100100011100100110010100000010000000110001001010110000010000100

10001110101100000100101010000010010001011010001000000000101000101100001100100000110011000000011001000000000110000000100110000000

现在，如何比较这三个哈希呢？我知道我必须把它们分成几块，但没有确切的方法？

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

有人能帮忙吗？

Answer 1

在回答你的问题之前，重要的是要记住：

1. Sim散列是有用的，因为它检测到接近重复。这意味着，几乎重复的项将以相同的散列结束。
2. 对于精确的复制，您可以使用任何一种方式，一致的散列机制(例如。md5)
3. 你贴在这里的例子太小了，考虑到它们的大小，它们的差别是很大的。该算法是为处理大的Web文档而不是小句子而定制的。

现在，我已经回答了您提出的这里关于Github问题的问题。

不过，作为参考，下面是一些示例代码，您可以使用这些代码在散列后打印最终的接近重复的文档。

# 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)

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

Answer 2

至于备忘录的答案，如果你想要检测>=70%的相似性，你不能使用simhash。西姆哈希只允许很小的汉明距离被检测，多达6或7位的差异，在一个拉伸，取决于你的语料库的大小。对于70%的相似性，您必须允许19位差异，这在任何正常情况下都是不可能的。相反，您应该查看minhash。

如果您感兴趣，这里有一个广泛的simhash解释。