algorithm - 使用 ElasticSearch 进行模糊重复搜索

Question

我有一个相当大的 N 文档数据集，其中只有不到 1% 的文档几乎是重复的，我想识别这些文档。我有很多数字字段和一些文本字段。我认为数据集中的两个文档关闭如果...

1. 除一个、两个或三个数据字段外，其他所有数据字段完全相同。
2. 两个文档的相应文本字段仅需少量编辑(即 ElasticSearch 使用的 Levensthein distance)。

您将如何应对使用 ElasticSearch 识别模糊重复的挑战？

我已经努力为第 (1) 部分编写一个(通用的)ElasticSearch 查询，它没有明确使用字段名称。我真的必须为以下模式构建一个巨大的查询，还是有更聪明的方法？

( SELECT * FROM MessyData AS T1
  JOIN MessyData AS T2
  WHERE T1.F1 != T1.F1 AND T1.F2 = T2.F2 AND T1.F3 = T2.F3 AND ... )
UNION ALL
( SELECT * FROM MessyData AS T1
  JOIN MessyData AS T2
  WHERE T1.F1 = T1.F1 AND T1.F2 != T2.F2 AND T1.F3 = T2.F3 AND ... )
UNION ALL
( SELECT * FROM MessyData AS T1
  JOIN MessyData AS T2
  WHERE T1.F1 = T1.F1 AND T1.F2 = T2.F2 AND T1.F3 != T2.F3 AND ... )
UNION ALL 
( ... )

注意:我使用 SQL 伪代码来说明我的意思是指除了一个字段之外的所有字段都相同的情况。 F 代表字段，T 代表表，但在 ElasticSearch 中是一个索引。

正在计算 dendrograms或使用另一种相似性度量来比较每个文档，每个文档都会给我 N·(N-1) 的计算量，因此不可行。

对于问题的第二部分，我正在考虑的方法是使用 m 测试文档(其中 m 比 N 小得多)来探测我的数据集)，将所有 m 查询的 ElasticSearch 得分相加。这将给我 O(m·N) 作为计算工作量，但我仍然必须对所有 N 分数总和进行排序，至少是部分排序，或即时排序。

除了 More Like This 或 Fuzzy Query 之外，是否还有其他算法可以解决这个问题？科学论文的链接也很受欢迎!

引用资料

• https://en.wikipedia.org/wiki/Data_deduplication作为介绍
• https://discuss.elastic.co/t/finding-documents--almost--the-same/66089/2
• https://discuss.elastic.co/t/using-fuzzy-query-to-find-near-duplicates/39075 - 论坛上的一个问题没有任何答案
• https://www.compose.com/articles/how-scoring-works-in-elasticsearch/
• https://betterexplained.com/articles/sorting-algorithms/对于order不同的标准搜索算法

Answer 1

我会建议将您的字段分为 4 组的快速而肮脏的方法。计算每组字段的散列。除非您在这四种度量中的一种上有相同的散列，否则您不可能是近乎重复的。

运气好的话，这个技巧意味着您只需要计算任何给定的文档以及相对较少的其他文档，这些文档在四分之一的字段上完全匹配。

如果“同一哈希上的匹配项”的 block 太大，您可以对不属于该 block 的字段重复该技巧，以期减少需要完成的工作量。