我熟悉 SimHash 和 MinHash 的 LSH（Locality Sensitive Hashing）技术。SimHash 在实值数据上使用余弦相似度。MinHash 计算二进制向量的相似度。但我无法决定使用哪个更好。
我正在为网站创建一个后端系统，以查找几乎重复的半结构化文本数据。例如，每条记录都有标题、位置和简短的文本描述（<500 字）。
除了特定的语言实现之外，哪种算法最适合新建生产系统？
问问题
10475 次
2 回答
20
Simhash更快（非常快）并且通常需要更少的存储空间，但对两个文档的不同程度施加了严格的限制，并且仍然被检测为重复。如果您使用的是 64 位 simhash（常见选择），并且取决于您能够存储多少个置换表，您可能会被限制为低至 3 或可能高达 6 或 7 的汉明距离。那些是小汉明距离！您将仅限于检测大部分相同的文档，即使如此，您也可能需要仔细调整您选择进入 simhash 的哪些功能以及您赋予它们的权重。
simhashes 的生成已获得谷歌的专利，尽管在实践中它们似乎至少允许非商业用途。
Minhash使用更多内存，因为您通常会为每个文档存储 50-400 个哈希值，并且它的 CPU 效率不如 simhash，但它可以让您找到相当遥远的相似性，例如，如果您估计相似性低至 5%想。它也比 simhash 更容易理解，特别是在表的工作方式方面。实现起来非常简单，通常使用 shingling，并且不需要大量调整即可获得良好的结果。它没有（据我所知）获得专利。
如果您正在处理大数据，则 minhash 方法中 CPU 最密集的部分可能是在您为文档生成 minhash 之后，当您在表格中寻找其他共享它的一些文档时哈希。可能有数以万计或数十万个文档与其共享至少一个哈希值，并且您必须仔细检查所有这些文件以找到那些共享例如至少一半哈希值的少数文档。Simhash 在这里要快得多。
正如 Otmar 在下面的评论中指出的那样，minhash 有一些优化，可以让您在相似性估计上达到相同的精度，而每个文档的哈希值更少。这可以大大减少你必须做的除草量。
编辑：
我现在已经尝试过superminhash。它相当快，尽管我使用单个散列函数加上位转换来生成所有其他散列的 minhash 实现对于我的目的来说更快。它提供了更准确的 jaccard 估计，在我测试的某些情况下大约好 15%（尽管在其他情况下几乎没有区别）。这应该意味着您需要减少大约三分之一的哈希来达到相同的准确性。在表中存储更少的哈希意味着需要更少的“除草”来识别接近的重复项，从而显着提高速度。我不知道有关 superminhash 的任何专利。谢谢奥特马尔！
于 2017-09-25T23:27:57.107 回答
7
本文可能会给你一些关于这两种算法的想法。
于 2015-05-12T17:02:05.740 回答