
HyperLogLog 算法如何用抛硬币的方式估算互联网独立访客数
来源标题:The coin-flipping trick that counts the Internet
HyperLogLog 算法通过类似抛硬币的概率方法,用极小内存估算海量数据中的独立元素数量,而无需存储完整 ID 列表。该算法广泛用于统计网站独立读者、社交媒体帖子受众和广告曝光人数等场景。相比精确记录每个访客 ID,它能在数据量剧增时大幅节省存储空间。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
抛硬币的 trick,如何数清互联网
这里讲讲无处不在的 HyperLogLog 算法是如何工作的
假设我想知道有多少人在《科学美国人》网站上读了我的某篇文章。统计页面被打开的次数很简单:网站可以维护一个持续累加的计数器,每当有人加载页面就加一。这个计数只是一个数字,占用的内存极小。但页面加载次数不等于人数。也许你早餐时开始阅读,中途分心,午餐后又回来读完。简单的计数会把你算两次。要精确统计独立访客,网站必须记录每一位读者,并在每次有人加载页面时对照名单进行检查。统计总浏览量只需要一个数字,而统计独立访客似乎需要一份和受众规模一样大的 ID 列表。现在,把打开一篇文章的 ID 数量乘以每篇文章、社交媒体平台上的每个帖子(也许是为了衡量趋势)或网站上的每个广告(为了满足广告商的配额),每一个都有自己可能包含数百万 ID 的名单。这些名单堆积成数据大山,全都为了回答一个简单的问题:“有多少人看到了这个?”
HyperLogLog 算法登场了。它接受近似估算而非精确计数,作为交换,它使用的内存只是完整 ID 列表所需内存的一小部分。这个算法值得了解,至少有两个原因。第一,它无处不在。Google Analytics 追踪着近半数网站的流量,它依赖该算法的一个增强版本来估算访客指标。如果你曾经查看过个人博客的访客数,你很可能已经见识过它的杰作。除了 Google,许多领域,包括基因组学和网络安全,也依赖它。第二,HyperLogLog 优雅得令人难以置信。
要理解这个算法的核心思想,我们先从一个游戏开始。我反复抛一枚硬币,直到它正面朝上,然后记下在此之前出现了多少次反面。这算作一轮。我重复很多轮,只追踪一个数字:在第一次出现正面之前最长的连续反面次数。现在假设我告诉你,我抛了一下午硬币后的纪录是连续 10 次反面。你的任务是猜我玩了多少轮。
你可以做出一个不错的猜测。连续 10 次反面大约每 1,000 轮才出现一次。这是因为单次抛掷出现正面的概率是 50%。第一次是反面的概率为 1/2;前两次都是反面的概率为 1/4;前三次都是反面的概率为 1/8,以此类推,分母不断翻倍,直到连续 10 次反面出现在每 1,024 轮中一次。如果我仅仅玩了十几轮,那么长的连续反面会是一个令人惊讶的巧合。如果我玩了100万轮,我几乎肯定会看到更长的连续反面。我的纪录是一个千分之一的事件,所以一个好的猜测是大约 1,000 轮左右。
HyperLogLog 玩的是同样的游戏,但每一轮对应一位访客。从高层来看,想象每位访客抛一堆硬币,记下结果,并在每次访问时展示给网站。就像知道我最多的连续反面次数能让你估算总轮数一样,网站只需要追踪所有访客中最长的连续反面次数,就能估算受众规模。
假设有 10 个人访问。其中两人的硬币序列以反面(T)、正面(H)开始,即 TTTH 开头,而另外八人的序列以 H、TH 或 TTH 开头。网站只记住数字三,即它见过的最长开头连续反面次数。这足以进行粗略估算:2³,也就是大约八位访客——与真实的 10 相差不远。如果后来有人带着更长的连续反面出现,纪录就会提高。而如果原来 10 人中的某一位再次访问,网站不需要知道他们是重复访客:他们带来相同的抛掷序列,所以估算的访客数不会改变。
注意网站需要记住的东西多么少。1,000 人的受众最可能在 10 轮左右产生最长的连续反面。100 万人应该预期在 20 轮左右出现纪录连续反面。10 亿之后,这个数字增长到 30。即使地球上每个人都访问了,纪录连续反面也很可能出现在 30 出头。我们从必须存储数十亿 ID 来精确统计独立访客,变成了只需存储一个两位数来进行估算。
还有两个重要问题:我们究竟如何让每位访客抛硬币并记住结果?如果有人碰巧得到一段异常长的连续反面,导致估算出现偏差,又该怎么办?
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。