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

Question

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

我的数据是：

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

这给了我 3 个像这样的散列：

0010011010111010001111100010001001010101100100000111000011100101110011010100110111101010001000101100101100011000011010[11210]

0000100111001000000001100000100011001000101000010101000000110000010010001110010011001010000010000000110001001010110=00210[0020]

10001110101100000100101010000010010001011010001000000000101000101100001100100000110011000000011001000000000110000000=0102000=010010

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

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

有人可以帮忙吗？

Answer 1

在我回答你的问题之前，请务必记住：

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

现在，我已经回复了你关于 here 提出的 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 doc_list > 1:
        print("Duplicates documents: ", doc_list)

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

Answer 2

根据Memos的回答，如果你想检测>=70%的相似度，你不能使用simhash。 Simhash 只允许检测非常小的汉明距离，一次最多大约 6 或 7 位差异，具体取决于语料库的大小。对于 70% 的相似性，您必须允许 19 位差异，这在任何正常情况下都是不可能的。您应该改为查看 minhash。

如果您有兴趣，这里有一份详尽的 explanation of simhash。

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

How to compare the similarity of documents with Simhash algorithm?

duplicates

simhash