1

我有大型 postgresql 数据库，包含文档。每个文档都表示为表中的一行。当新文档添加到数据库中时，我需要检查重复项。但我不能只select用来找到完全匹配。两个文档可能略有不同，但仍然可以被视为重复，例如，如果一些次要字段不同而所有其他字段都相同。

我研究这个问题并找到解决这个问题的方法。可以MinHash为每个文档计算签名并构建倒排索引，从数据库中查询相似的文档。但我不明白如何映射MinHash到关系数据库。

据我了解，MinHash签名是 N 个哈希的列表，其中 N 是许多属性。相似度计算如下：

# Given 2 signatures Sa and Sb containing N hashes.
# Calculate number of equal hashes Neq.
number_of_equal_hashes = 0
for ix in range(0, N):
    if Sa[ix] == Sb[ix]:
        number_of_equal_hashes += 1
similarity = float(number_of_equal_hashes)/N

如果您已经有两个签名，这很简单，问题是在数据库中找到相似度小于或等于某个值的所有文档（具有相应签名）。

例如，我可以创建具有多个列的表，如下所示：

| minhash0 | minhash1 | minhash3 | docid |

每minhashX列对应于文档属性之一的 minhash，并且docid是文档的标识符。我可以这样查询类似的记录：

select * from invidx
where ((case when minhash0=minhash2search0 then 1 else 0 end) +
       (case when minhash1=minhash2search1 then 1 else 0 end) +
       (case when minhash2=minhash2search2 then 1 else 0 end))/N > THRESHOLD

其中minhash2searchX是新文档的 minhashes，而 THRESHOLD 是最小相似性。但是这种方法需要全扫描。有什么方法可以加速这个算法吗？

4

2 回答 2

2

要使用倒排索引的优势，我建议您使用全文搜索引擎，例如Lucene或Solr（基于 Lucene）

您可以构建“文档”（就 Lucene 而言），其中包含与您的文档（数据库记录）的 MinHashes 相关联的字段。请注意，您也可以索引数字字段（您只需要在方案中描述字段类型）。此外，您必须存储每个文档的主键，以便将 Lucene“文档”映射到数据库中的记录上。

索引整个文档集合。

要查找与给定文档相似的文档 - 您必须计算每个字段的 MinHashes，并查询Lucene 以获取相似文档：

field1:MinHash1 OR field2:MinHash2 OR ...

随着更多字段匹配文档 - 它将具有更高的排名。所以，你可以拿一些最高级别的文件，然后做出决定——如果它们在你的情况下真的很相似

此外，提升字段可能对您有用

于 2012-12-05T12:43:05.140 回答
1

您的哈希表应包含两列：

| minhash | docid |

它应该在 minhash 上建立索引。

当一个新文档到达时，您依次搜索其每个 minhash，查询表以查找共享该 minhash 的先前文档。您建立这些先前文档共享多少 minhashes 的计数，然后丢弃所有那些共享的 minhashes 少于（例如）50% 的那些。这有效地产生了至少（估计）50% 相似的所有文档集。

最后，您为每个新文档的 minhashes 插入新行。

使用 Lucene 或 Solr 是一个糟糕的解决方案。它将需要更多的存储空间，实现起来更复杂，效率也大大降低。是的，您可以让 Lucene 索引您的 minhashes 并按照 stemm 的建议运行查询。这将返回甚至共享一个 minhash 的每个文档，这可能是数万或数十万，具体取决于您的数据大小。然后，您必须使用“相似性”功能将这些中的每一个与您传入的文档进行单独比较，这将非常慢。

Lucene 确实提供了一个“MoreLikeThis”功能来查找共享某些关键字的文档，但这会丢失许多 minhash 方法可以找到的类似文档。

于 2019-02-13T02:34:49.333 回答