基于flajolet-martin算法的基数估计
cardinality-cs110的Python项目详细描述
使用flajolet-martin算法进行基数估计
想象一下，如果你有数据并且你想知道它的基数（存在的唯一元素的数量），计算基数可以有多种用途，例如计算一个网站上的唯一访问者的数量。
您可以编写一个简单的算法来循环遍历数据集，并检查每个元素是否只出现一次，但如果您有一个巨大的数据集，其数据量达万亿字节，甚至无法放入计算机内存，则这是不可行的。为了解决这个问题，可以使用基数估计器，它以最小的内存使用量为代价，对数据集的基数进行非常接近的估计。
背后的想法
如果您有一个大型数据集，那么看到以x零结尾的散列项（转换为其二进制形式）的概率是2^x。例如，如果在末尾需要3个零，则概率为0.5 * 0.5 * 0.5 = 0.125，因为每个位要么是0，要么是1。因此，平均来说，在1/0.5^x个数的末尾有3个零，相当于2^x。这是估计基数的另一种简单方法，但是如果哈希值有太多的零，并且它的估计值是2（256、512、1024…）的幂，那么它可能会给出非常不准确的结果。此方法的一个改进是使用各种散列函数并平均给出的估计值，但是各种散列函数的计算代价很高。为了绕过这种计算限制，我们可以使用一种称为随机平均的方法，将单个散列函数的输出分成两部分。我们用^ {EM1}$MEEEM表示最多0个数的桶的数目和用来计算我们存储的最大桶数0的比特数，由^ {EM1}$KEEE>表示。这个算法的精度，根据它所基于的论文，可以归结为1.3/sqrt（m），其中m是桶的数量，因此根据您想要的精度，您可以改变m的值，但不能改变到非常大的值。原因是k的值（散列值中用于计算bucket索引的位数）是由log（m）决定的，您不想为k使用大量位，因为这会降低精度。例如，如果你有一个二进制值10000100000，你用M的值为1024，那么你只得到1作为0的最大数而不是5。
使用k作为2的二进制输入10010000的m/k值的示例将导致使用最左边的两个位来计算桶号（10对应于桶号2），并使用剩余的位来计算以0结尾的个数（在本例中是4），然后将以0结尾的个数存储在该桶中。
注：此算法产生可预测的更大估计；因此，为了校正偏差，最终输出乘以0.79402的常数，该常数由Mariannae Durand和Phillipie Flajolet通过统计分析得出
欢迎加入QQ群-->： 979659372
用法
importcardinality_cs110data=['sample data here']print(cardinality_cs110.flajolet_martin(data,k))'output is the estimated number of unique elements'
推荐PyPI第三方库
