algorithm - 找出（（A相交B）联合C）相交D）的基数的有效（恒定空间或次线性空间）方法？

Question

我目前正在使用 hyperloglog 来估计集合的基数（唯一项目的数量）

计算 2 个集合的并集的基数和 2 个集合的交集的基数 ( |A intersect B| = |A| + |B| - |A union B|)非常简单

但是我找不到一种方法将联合和交集的运算符链接在一起（注意：只允许计算基数而不是交集的超对数的方法，即可以通过A union B而不是得到一个新的超对数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|

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