c++ - 查找要删除重复项的项目

Question

我有一个数据池 (X₁..X_N)，我想为它找到相等值的组。比较非常昂贵，我不能将所有数据都保存在内存中。

我需要的结果例如是:

X₁ equals X₃ and X₆
X₂ is unique
X₄ equals X₅

(行的顺序或行内的顺序无关紧要)。

我如何通过成对比较来实现它？

---

这是我目前所拥有的:

比较所有对 (X_i, X_k) 与 i < k, and 利用传递性:如果我已经找到 X₁==X₃ 和X₁==X₆，我不需要比较X ₃ 和 X₆。

所以我可以使用以下数据结构:

  map: index --> group
  multimap: group --> indices

组是任意分配的(例如输出中的“行号”)。

对于 (X_i, X_k) 和 i < k :

• 如果i和k都已经分配了一个组，则跳过

• 如果它们比较相等:

  • 如果我已经分配了一个组，则将 k 放入该组
  • 否则，为i新建一个组，将k放入其中

• 如果它们不相等:

  • 如果我还没有分配组，为我分配一个新组
  • k 也一样

如果我注意项目的顺序，那应该可以工作，但我想知道这是否是解决此问题的最佳/最不令人惊讶的方法，因为这个问题似乎有些普遍。

---

背景/更多信息:目的是对项目的存储进行重复数据删除。他们已经有一个散列，以防发生冲突，我们希望保证进行全面比较。所讨论数据的大小具有非常尖锐的长尾分布。

迭代算法(找到任何两个重复项，共享它们，重复直到没有重复项为止)可能更容易，但我们需要非修改诊断。代码库是 C++，与 STL/boost 容器或算法一起工作的东西会很好。

[edit] 关于散列:为了这个问题的目的，请假设一个不可替代的弱散列函数。

这是对现有数据进行一次性重复数据删除所必需的，并且需要处理哈希冲突。最初的选择是“fast hash, and compare on collision”，选择的哈希有点弱，但改变它会破坏向后兼容性。即便如此，我还是用一个简单的声明睡得更好:如果发生碰撞，你不会得到错误的数据。而不是写关于 wolf attacks 的博客。 .

Answer 1

这是另一个可能更简单的数据结构，用于利用传递性。做一个你需要做的比较队列。例如，如果有 4 个项目，它将是 [ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ] .还有一个数组用于您已经完成的比较。在每次比较之前，检查之前是否进行过该比较，每次找到匹配项时，遍历队列并将匹配项索引替换为其较低的索引等价物。

例如，假设我们弹出 (1,2)，比较，它们不相等，将 (1,2) 压入 already_visited 的数组并继续。接下来弹出(1,3)，发现它们相等。此时，遍历队列并将所有 3 替换为 1。队列将为 [(1,4), (2,1), (2,4), (1,4)]，依此类推。当我们到达(2,1)时，它已经被访问过，所以我们跳过它，(1,4)也是如此。

但我同意前面的回答。由于比较的计算成本很高，您可能希望首先计算一个快速、可靠的哈希表，然后才将此方法应用于冲突。