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

Question

我有一些名为tokens的元素.它们中的每一个都是某种类型的关联容器(不一定是std容器之一).我有一些存储令牌的容器存储(不一定是std容器之一).存储 是一组令牌.
我需要能够通过指定的比较器指定键对令牌值上的令牌(存储)集执行交集操作.作为该操作的结果,我想获得另一组令牌(另一个存储).

伪代码中的用例:

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

我正在寻找一种有效的算法.
注意:我有几十个令牌.
问题:
1)如何组织存储？
2)如何实现交叉口运营？

更新一些解释:
token是一组(键,值)对.存储是一组(键,值)对

我需要交叉(P1,K1,P2,K2,cmp)
P1 - 第一个存储
P2 - 第二个存储
K1 - 第一个存储的
密钥K2 - 第二个存储的密钥
cmp - 比较函数,如cmp(value,value),返回true或假

相交应该遍历P1的每个元素e1,并通过P2的每个元素e2并提取满足cmp的元素((键,值)对)(e1 [K1],e2 [K2])

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中找到[版权位于讲座首页]