5

我有一个数据池（X 1 ..X N），我想为它找到相等值的组。比较非常昂贵，我无法将所有数据都保存在内存中。

我需要的结果是，例如：

X 1等于 X 3并且 X 6
X 2是唯一的
X 4等于 X 5

（行的顺序或行内的顺序无关紧要）。

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

这是我到目前为止所拥有的：

比较所有对 (X i , X k ) 与 i < k，并利用传递性：如果我已经找到 X 1 ==X 3和 X 1 ==X 6，我不需要比较 X 3和 X 6。

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

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

其中组是任意分配的（例如输出中的“行号”）。

对于i < k的一对 (X i , X k )：

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

  • 如果它们比较相等：

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

  • 如果它们不相等：

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

如果我对项目的顺序很小心，那应该可以，但我想知道这是否是解决这个问题的最好/最不令人惊讶的方法，因为这个问题似乎有点普遍。

背景/更多信息：目的是对项目的存储进行重复数据删除。他们已经有一个哈希值，如果发生冲突，我们希望保证完全比较。相关数据的大小具有非常尖锐的长尾分布。

迭代算法（找到任何两个重复项，共享它们，重复直到没有重复项）可能更容易，但我们需要非修改诊断。代码库是 C++，适用于 STL / boost 容器或算法的东西会很好。

[编辑]关于散列：出于这个问题的目的，请假设一个无法替换的弱散列函数。

这是对现有数据进行一次性重复数据删除的必要条件，并且需要处理哈希冲突。最初的选择是“快速散列，并在碰撞时比较”，选择的散列有点弱，但改变它会破坏向后兼容性。即便如此，我还是用一个简单的陈述睡得更好：万一发生碰撞，您不会得到错误的数据。而不是写关于狼袭击的博客。

4

4 回答 4

1

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

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

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

于 2013-07-22T21:56:02.847 回答
1

对每个项目进行哈希处理。列出pair<hash,item_index>. 您可以通过按哈希排序此列表或将其放入std::multimap.

当您输出组列表时，您需要比较项目的哈希冲突。因此，对于每个项目，您将进行一次哈希计算和一次比较。和哈希列表的排序。

于 2013-07-22T15:13:58.680 回答
1

所以......你已经有一个哈希？这个怎么样：

  • 对哈希进行排序和分组
  • 将所有大小为 1 的组打印为唯一的
  • 比较碰撞

比较 colisions 的提示：为什么不使用不同的算法重新哈希它们？冲洗，重复。

（我假设您在此处存储文件/blob/图像并具有它们的哈希值，并且您可以将哈希值放入内存中，而且哈希值类似于 sha1/md5 等，因此不太可能发生冲突）

（另外，我假设两种不同的散列算法不会在不同的数据上发生冲突，但这可能是安全的假设......）

于 2013-07-22T15:25:15.823 回答
0

我同意使用第二个（希望改进的）散列函数的想法，这样您就可以解决一些弱散列的冲突，而无需进行昂贵的成对比较。既然您说您遇到内存限制问题，希望您可以将整个哈希表（带有辅助键）放入内存中，对于表中的每个条目，您存储磁盘上与该键对应的记录的记录索引列表一对。那么问题是对于每个密钥对，您是否可以将所有记录加载到具有该密钥对的内存中。如果是这样，那么您可以迭代密钥对；对于每个密钥对，释放内存中前一个密钥对的所有记录，并为当前密钥对加载内存中的记录，然后像您已经概述的那样在这些记录之间进行比较。如果你有一个密钥对，你可以'

于 2013-07-22T18:06:39.543 回答