有效的(恒定空间或司额空间)找出(((a相互)b)联合c)相交d)的基数

Question

我当前正在使用超置logog来估计集合的基数（唯一项目的＃）

计算2组联合的基数和2组相交的基数（|A intersect B| = |A| + |B| - |A union B|）

非常微不足道

，但我找不到将联合和交集的操作员链接在一起的方法（注意：仅允许计算基数而不是相交的超置logog的方法，也就是说，可以通过A union B获得新的Hyperloglog但不是A intersect B）。

是否有替代算法可以估计连锁联合和交叉点结果的基数？

Answer 1

用布尔代数的顽强使用会解决问题，尽管如果选择性很低，您可能对质量不满意。

|((A n B) u C) n D| =
|(A n B) u C| + |D| - |(A n B) u C u D| =
|(A u C) n (B u C)| + |D| - |(A u C u D) n (B u C u D)| =
|A u C| + |B u C| - |A u B u C| + |D| - |A u C u D| - |B u C u D| + |A u B u C u D|

您可能应该仔细检查我的数学。