该表显示,我们统计这些单词只用了512 bytes,而误差在3%以内。相比之下,HashMap的计数准确度最高,但需要近10MB的空间,你可以很容易地看到为什么基数估计是有用的。在实际应用中准确性并不是很重要的,这是事实,在大多数网络规模和网络计算的情况下,用概率计数器会节省巨大的空间。
线性概率计数器
线性概率计数器是高效的使用空间,并且允许实现者指定所需的精度水平。该算法在注重空间效率时是很有用的,但你需要能够控制结果的误差。该算法分两步运行:第一步,首先在内存中分配一个初始化为都为0的Bit-map,然后使用哈希函数对输入数据中的每个条目进行hash计算,哈希函数运算的结果是将每条记录(或者是元素)映射到Bit-map的一个Bit位上,该Bit位被置为1;第二步,算法计算空的bit位数量,并使用这个数输入到下面的公式来进行估算:
n=-m ln Vn
在公式中,m是 Bit-map的大小,Vn是空bit位和map的大小的比率。需要重点注意的是原始Bit-map的大小,可以远小于预期的最大基数。到底小多少取决于你可以承受误差的大小。因为Bit-map的大小m小于不同元素的总数将会产生碰撞。虽然碰撞可以节省空间,但同时也造成了估算结果出现误差。所以通过控制原始map的大小,我们可以估算碰撞的次数,以致我们将在最终结果中看到误差有多大。
(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/fuwuqi/)Hyper LogLog
顾名思义,Hyper LogLog计数器就是估算Nmax为基数的数据集仅需使用loglog(Nmax)+O(1) bits就可以。如线性计数器的Hyper LogLog计数器允许设计人员指定所需的精度值,在Hyper LogLog的情况下,这是通过定义所需的相对标准差和预期要计数的最大基数。大部分计数器通过一个输入数据流M,并应用一个哈希函数设置h(M)来工作。这将产生一个S = h(M) of {0,1}^∞字符串的可观测结果。通过分割哈希输入流成m个子字符串,并对每个子输入流保持m的值可观测 ,这就是相当一个新Hyper LogLog(一个子m就是一个新的Hyper LogLog)。利用额外的观测值的平均值,产生一个计数器,其精度随着m的增长而提高,这只需要对输入集合中的每个元素执行几步操作就可以完成。其结果是,这个计数器可以仅使用1.5 kb的空间计算精度为2%的十亿个不同的数据元素。与执行 HashSet所需的120 兆字节进行比较,这种算法的效率很明显。
合并分布式计数器
我们已经证明了使用上面描述的计数器我们可以估算大集合的基数。但是,如果你的原始输入数据集不适合于单台机器,将怎么做呢?这正是我们在Clearspring所面临的问题。我们的数据分散在数百台服务器上,并且每个服务器只包含整个数据集子集的一部分。这事实上我们能合并一组分布式计数器的内容是至关重要的。这个想法有点令人费解,但如果你花费一些时间去思考这个问题,就会发现其与基本的基数估计值相比并没有太大的不同。因为这个计数器表示映射中的位作为基数,我们可以采取两个兼容计数器并将他们bit位合并到单一的map上。这个算法已经处理碰撞,所以我们可以得到一个基数估计所需的精密,即使我们从来没有把所有的输入数据到一台机器。这是非常有用的,节省了我们在网络中移动数据的大量时间和精力。
Next Steps
(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/fuwuqi/)希望这篇文章能帮助你更好地理解这个概念和概率计数器的应用。如果估算大集合的基数是一个问题,而你又碰巧使用一个基于JVM的语言,那么你应该使用stream-lib项目它提供了其他几个流处理工具以及上文所述的算法的实现。