每月一次

Question

我想使用MinHash LSH将大量文档放入类似文档的桶中（Jaccard相似性）。在

在不知道另一个散列的情况下，是否可能计算出另一个散列的minstrong>？在

我只能理解“强制”的哈希。所以这应该是可能的？在

我发现一个非常令人满意的实现是datasketch。在知道所有文档的MinHash之后，我可以查询LSH中与给定文档类似的文档。然而，在了解其他文档之前，我看不到任何一个文档的存储桶。 https://ekzhu.github.io/datasketch/index.html

Answer 1

LSH不存储整个文档，也不存储单个minhash。更确切地说，它是一堆杂碎。在

LSH既可以减少每个文档存储的散列数，也可以减少使用这些散列搜索相似文档时的命中数。它通过将多个minhash组合成一个散列来实现这一点。因此，例如，不必为每个文档存储200个minhash，而是可以将它们组合成4个带段，从而生成50个对位置敏感的哈希。在

每个频带的散列由其组成的minhash使用诸如FNV-1a这样的廉价散列函数来计算。这会丢失一些信息，这就是为什么LSH被称为减少数据的维数。得到的哈希就是bucket。在

因此，计算文档中每个minhash波段的bucket时，不需要了解任何其他波段或任何其他文档。在

使用LSH哈希来查找相似的文档很简单：假设您想查找与文档A相似的文档。首先为文档A生成（例如）50个LSH哈希。然后在哈希字典中查找共享一个或多个哈希的所有其他文档。共享的散列越多，估计的jaccard相似性就越高（尽管这不是线性关系，就像使用普通minhash时一样）。在

每个文档存储的哈希总数越少，估计的jaccard相似性的错误就越大，丢失类似文档的可能性也就越大。在

这是a good explanation of LSH。在