minhash - 在生产系统的SimHash和MinHash之间选择

Question

我熟悉SimHash和MinHash的LSH（局部敏感哈希）技术。 SimHash对实际值数据使用余弦相似度。 MinHash计算二进制矢量上的相似度相似度。但是我无法决定哪个更适合使用。

我正在为网站创建一个后端系统，以查找几乎重复的半结构化文本数据。例如，每条记录将具有标题，位置和简短的文本描述（少于500个字）。

除了特定的语言实现之外，哪种算法最适合未开发的生产系统？

Answer 1

Simhash速度更快（非常快），通常需要较少的存储空间，但对两个文档的异同程度以及仍然可以将其检测为重复项施加了严格限制。如果您使用的是64位simhash（通常的选择），并且取决于您能够存储多少个置换表，则可能会将汉明距离限制为低至3或高至6或7。小汉明距离！您将只能检测几乎相同的文档，即使如此，您可能仍需要对选择加入simhash的哪些功能以及赋予它们的权重进行一些仔细的调整。

simhashes的生成已获得Google的专利保护，尽管在实践中它们似乎至少允许非商业用途。

Minhash使用更多的内存，因为您通常每个文档存储50-400个哈希，并且CPU效率不如simhash，但是它可以让您找到相距甚远的相似之处，例如如果需要，估计相似度低至5％。比simhash还容易理解，特别是在表的工作方式方面。它的实现非常简单，通常使用混叠（shingling），不需要太多的调整即可获得良好的结果。 （据我所知）它没有专利。

如果要处理大数据，则minhash方法中CPU占用最大的部分可能是在为文档生成细化之后，即在遍历表以查找共享其某些内容的其他文档时哈希。可能有成千上万的文档与它共享至少一个散列，并且您必须仔细研究所有这些散列，以找到那些很少共享的散列，例如至少一半的哈希值。 Simhash在这里更快。

正如Otmar在下面的评论中所指出的那样，minhash的优化使您可以用更少的每个文档散列来实现相似度估计的相同精度。这样可以大大减少您必须除草的数量。

编辑：

我现在尝试了superminhash。尽管我实现的minhash using a single hash function plus bit-transformations to produce all the other hashes更快，但速度相当快。它提供了更准确的jaccard估算值，在我测试过的某些情况下大约提高了15％（尽管在其他情况下几乎没有区别）。这意味着您需要减少大约三分之一的哈希值才能达到相同的精度。在表中存储更少的哈希意味着更少的“除草”来识别几乎重复的数据，从而显着提高了速度。我不知道有关superminhash的任何专利。谢谢奥特玛！