当我们在Google中搜索时(我几乎可以肯定Altavista做了同样的事情)，它会显示"结果1-10(共xxxx个)" ...

这总是让我感到惊讶..."约"是什么意思？
他们如何粗略计算？
我知道他们为什么不能在合理的时间内得出精确的数字，但是他们怎么能达到这个"近似"的数字呢？

我敢肯定我错过了很多理论背后的知识...

解决方案

与问题无关，但让我想起我的一个朋友在做一次简单的自我搜索时开的一个小玩笑(不要告诉我我们从未用Google搜索过名字)。他说了类似的话

"哇，仅0.22秒就能得到大约5,000个结果！现在，想象一下在一分钟，一小时，一天之内有多少个结果！"

返回准确数量的结果不值得进行准确计算的开销。由于知道有1,004,345个结果而不是"大约1,000,000个"，因此并没有太多的增值，因此从最终用户体验的角度来看，更重要的是更快地返回结果，而不是花费额外的时间来计算总数。

从Google本身：
"谷歌对搜索结果总数的计算是一个估计。我们知道一个重要的数字，并且通过提供一个估计而不是一个确切的帐户，我们可以更快地返回高质量的搜索结果。"

我想这个估计是根据统计数字得出的。他们不会计算所有相关的页面匹配，所以他们(我会做)是根据某种启发式方法，大致算出与查询匹配的页面百分比，然后将其用作计算的基础。

一种启发式方法可能是做一个样本计数，随机抽取1000个左右的页面作为样本，然后查看匹配的百分比。样本中不需要太多的内容就可以得出具有统计意义的答案。

它很可能类似于大多数SQL系统在其查询计划中使用的估计行数。表中的许多行(确切地知道上次收集统计信息的时间，但是通常不是最新的)，乘以估计的选择性(通常基于通过对一些小子集进行采样而计算出的统计分布模型)行)。

PostgreSQL手册中有一个关于计划者使用的统计信息的部分，该部分内容十分丰富，至少如果我们遵循指向pg_stats的链接以及其他各个部分的话。我敢肯定，这并不能真正描述google的功能，但是它至少显示了一个模型，我们可以在其中获得前N行，并估算出可能还有多少行。

尚未提及的一件事是重复数据删除。一些搜索引擎(我不确定确切地说Google到底是如何做到的)将使用试探法来尝试确定两个不同的URL是否包含相同(或者极其相似)的内容，从而得到重复的结果。

如果有156个唯一URL，但是其中9个已被标记为其他结果的重复，则说"大约150个结果"比" 156个结果包含147个唯一结果和9个重复"这样的说法更简单。