如何执行高效的集合交集操作？

Question

我有一些名为“tokens”的元素。它们每一个都是某种关联容器（不一定是std容器）。我有一种存储器类型叫做“storage”，它存储tokens（不一定是std容器）。"storages"是"tokens"的集合。
我需要能够按指定键和指定比较器对令牌（"storage"）集合执行交集操作的能力。 作为该操作的结果，我希望得到另一个令牌集合（另一个"storage"）。

伪代码中的用例:

  if ( (storage0[key1]==storage1[key1])[key2]<storage1[key2] )
    ...

我正在寻找一种高效的算法来完成这个任务。
注意：我有几十个令牌。
问题：
1）如何组织存储？
2）如何实现交集操作？

更新一些解释：
令牌是一组（键，值）对。 存储是一组（键，值）对的集合

我需要intersect(P1，K1，P2，K2，cmp)
P1 - 第一个存储
P2 - 第二个存储
K1 - 第一个存储的键
K2 - 第二个存储的键
cmp - 比较函数，例如cmp（value，value），返回true或false

Intersect应该遍历P1的每个元素e1，以及P2的每个元素e2，并提取满足cmp（e1 [K1]，e2 [K2]）的那些元素（（键，值）对）

- 2r2w

---

这段代码：if ( (storage0[key1]==storage1[key1])[key2]<storage1[key2] ) 没有意义。 - fjardon

如果 ( ((storage0[key1]==storage1[key1])[key2]<storage1[key2]).size() ) . 更好吗？ @fjardon - 2r2w

(storage0[key1]==storage1[key1]) 是一个布尔值。那么 (storage0[key1]==storage1[key1])[key2] 是什么？ - fjardon

大多数人看到 == 时，会认为它是一个返回 true 或 false 的二元运算符。你是在进行一些返回布尔值集合的集合比较吗？还是在进行 lambda 演算？另外，首先 storage[key] 是什么？我以为 storage 只是一个集合，而不是某种 (key,set) 映射。key 是用于存储和令牌元素的相同类型的键吗？它们之间有什么关系？ - CygnusX1

storage[key] 是一组令牌值（token[key]）的集合，也就是说这个存储中有许多具有令牌的值。 - 2r2w

Answer 1

倒排索引 可以高效地处理交集，因此您可以执行类似的操作。

思路是：每个集合实际上都是一个列表，具有高效的 getFirstAfter(key) 函数 - 它返回 key之后的第一个标记。 对于每个集合 - 您需要检查相关元素是否在其中 - 如果不在 - 则前进到下一个在集合中的元素。

(*)注意，该算法中列举了标记

(*)假设T保存您要相交的所有列表[该算法有效地相交两个以上的列表]

伪代码：

lastTok <- 0 //the first token in the collection
currSet <- 0 //the first set 
while (lastTok != infinity):
  if (currSet > T.last): //if we have passed the last set
     insert lastTok into result
     currSet <- 0
     lastTok <- lastTok + 1
     continue
  currentToken<- T[currSet].getFirstAfter(lastTok-1)
  if (currentToken!= lastTok):
     lastTok<- currentToken
     currSet <- 0
  else: 
     currSet <- currSet + 1

这个算法假设有一个高效的getFirstAfter()函数，它可以给出第一个符合条件且docId大于指定参数的文档。如果没有符合条件的文档，则应返回无穷大。

如果将术语按照最稀有的术语排在前面进行排序，该算法将会最有效。

该算法保证最多执行#docs_matching_first_term * #terms次迭代，但实际上通常会迭代次数更少。

更多信息可以在这个讲义笔记的11-13页找到[讲义第一页版权所有]

- amit