Web背后的秘密

web，全称为 world wide web，是 internet 上最重要和最为人们所熟知的应用之一。web 是指 internet 上所有基于 http 协议的 html 网页、图像、音频、视频等内容的集合。虽然 web 可能早已成你每天日常生活的一部分，但相信你对 web 背后的秘密仍然很感兴趣。本文向大家展示了关于 web 的一些通常不为人所知而又有趣的细节。

1. web的流量

虽然internet（包括其前身arpanet等）的历史比web要长的多，但直到 tim berners-lee爵士于1989年设计出web并在1991年开始实际运行之后，internet才逐渐大众化并开始流行。自1995年开始，web占据了整个 internet的大部分流量，而成为internet上最重要的一项应用（注意不是“之一”）。

这种影响一直延续到今天：在日常生活中，我们一般甚至不 区分“internet”和“web”，而“上网”这个词在很多情况下指的就是浏览web。web在流量上的主导地位自2000年起受到以napster为始祖的p2p的挑战。相比web来说，p2p在大型文件的传输上具有很大优势，因此虽然从广度来说web仍然是主导，但在流量上自2002年起被p2p应用超过。下图显示了自1993年到2004年internet上重要协议的流量变化。

但这种状况在2007年发生了逆转。随着网络带宽的增加，以 youtube为首的在线视频网站开始流行，使得web的流量迅速增长并重新超过了p2p流量，尽管这个“优势”很微弱。总结一下，仅从流量的角度看，目前的internet可以说是web和p2p各占半边天，而其余应用所占的比重是越来越小。关于web和p2p流量更详细的分析可以参考这篇文章。

2. web的规模

web的规模定义为web上包含的有效网页的数量。google最近宣称已经索引了1,000,000,000,000个网页， 不过google显然不敢宣称已经索引了web上全部或绝大部分的网页，可以预计，web的规模已经远远超过了上面这个数值。顺便提一句，“有效网页的数 量”严格来说其实是个伪命题，因为：1. 很多网站在被请求了不存在的页面时会返回一个友好的提示而非404错误（可以测试url：http://live.aulddays.com/后面跟上任意的文件名），理论上说它们仍然是“有效”的网页；2. 很多网页可以根据输入参数的不同而返回不同的结果（google目前正着手解决的 deep web就是属于这种情况）。从这个意义上说，说web的规模是无穷大的…

退而求其次，我们可以来估计一下有多少网页是google没有索引到的：假设我们知道了两个不同的搜索引擎 a 和 b，它们索引的网页数量分别是 s(a) 和 s(b)，a&b为两个搜索引擎的交集，那么根据容斥原理，所有被它们（中至少一个）索引的网页数量就是 s=s(a)+s(b)-s(a&b)；这个公式还可以推广到多个搜索引擎的情况，则此时s会越来越靠近真实的 web 的规模。不过很遗憾，这个公式很不实用:-( 虽然 google 不久前迫于 cuil的压力公布了自己的索引量，但其他几大搜索引擎仍习惯于对这个数据秘而不宣；更糟的是，google 或是 yahoo! 显然不可能把自己的索引库共享给对手以求得 s(a&b) 这项。不过，bharat 和 broder在1998年基于统计学原理提出了一个很巧妙并且很著名的解决方法：记 pr(a) 为某个元素属于集合 a 的概率，pr(a&b|a) 为已知一个元素属于 a 时而它同时属于两个集合的条件概率。 则可以推出：pr(a&b|a)≈s(a&b)/s(a)，pr(a&b|b)≈s(a&b)/s(b)，即得 s(a)/s(b)≈pr(a&b|b)/pr(a&b|a)。而 pr(a&b|b)、pr(a&b|a) 都可以用随机采样的方法根据一系列精巧构造的搜索用例通过实际的搜索实验估计出来，从这两个值还可以用来估算出 s(a&b) 的大小。再进一步，从语言学模型中可以估计出之前构造的搜索用例在整个语言文本中出现的概率，从而估计出 s(a) 和 s(b) 具体的大小。

现在的问题就集中在3点：搜索用例的独立性、搜索用例的覆盖性、和结果检验的完整性（搜索结果集可能很大，如果只看靠前的部分，通常这部分的 rank 会比较高，因而被同时索引的概率也会偏高，参考下面的web的结构一 节）。bharat 和 broder 构造的方法着重解决了前两个问题，他们报告当时（1997年底）的几大搜索引擎hotbot, altavista, excite, infoseek (其时 google 还未正式发布) 的索引覆盖率 (占整个已被索引的 web) 分别为：48%, 62%, 20%, 和 17%，而 web 的总规模约为 220,000,000。值得注意的是，他们的结果还显示各引擎的重合率 (即 s(a&b)) 很低，平均只有 1.4%，可见当时的索引水平也还处于较低的阶段。到了 2005 年，gulli 和 signorini改进了结果检验完整性的问题并在新的搜索巨头 google, yahoo!, ask/teoma, msn 上进行了测试，结果它们各自的覆盖度分别为 76%, 69%, 58%, 62%，web的总规模达到了约 11,500,000,000。2006 年 bar-yossef 和 gurevich进一步优化了随机采样的理论，根据他们的结果，当时 google, yahoo!, msn 的覆盖率大约为：64%, 65%, 50%，重合率平均为 44%，比1997年有很大提高。他们并没有给出估计的web总规模，不过这组覆盖率数值应该比较接近目前的水平，因此结合上面 google 最新的索引数量，相信大家不难估计出当前 web 的总规模。

3. web的结构

上面讨论了web的规模。我们知道，web的特点是各个网页之间由超链接互相连接而形成的网状结构，那么这么大的一张网具有什么样的特点呢？

andrei broder等人在2000年比较早的研究了这个问题，他们的研究基于两个web爬虫各自爬取的超过2亿个网页和15亿个超链接，他们认为这些网页具有一种类似“领结（bow tie）”的结构。领结的形状大致是中间一个大的“结”以及两边各一个三角形的“花”，在每个“花”上面附着了一些穗状的“花边”，而两个花之间还有一条长的“项圈 ”让领结可以套在脖子上。中间的“结”是由约5600万网页组成的scc（strong connected component，强连接组件），左边和右边的花分别是in组件和out组件，分别包含4400万网页。剩下的4400万网页则是花上的穗状物 （tendril组件）。在scc组件中，任意两个网页都可以通过很短的有向链接路径到达彼此，它们是整个web的核心部分。in组件里的网页可以链入 scc，但无法从scc链回来，这些一般是比较新的网页还没有被大家所发现并链接到。out组件则是可以从scc链入但不包含链回scc的链接，这些可能 是一些只包含内部链接的企业网站。tendril组件则是和in或out组件相连但并不和scc组件有较直接联系的网页，有趣的是，tendril组件中 的一小部分可以联系in和out组件而形成的“项圈”部分。还有很少一部分的网页是不被链接到的，不属于以上任何一个组件。这项结果中最令人惊奇的部分是 它显示scc部分（整个 web 中相互链接最稠密的部分，因而通常也是最经常浏览的部分，参考 pagerank的基本原理，它们通常具有较高的 rank 值）的大小只占整个 web 的一小部分，这暗示web上可能大量充斥的是那些没多少“价值”的网页。

当然上面的是2000年的情况，在最近几年中web的结构可能发生了变化，因此一些新的理论也被提了出来。2005年 debora donato 等人研究后认为，web的结构已逐渐转变成一个类似“菊花”的形状：在 in 和 out 组件内部出现了很多符合 in-out-scc 关系的细微结构，因而 in 和 out 可以进一步被细分而形成围绕在 scc “花心”周围一圈大小不一的“花瓣”。不过在他们的结果中，scc 的比例有所扩大，在部分数据集上甚至达到了 72.3%，这也让后来的研究者对他们的数据集覆盖性产生了一些怀疑，或许有一些较深的弱链接网页没有被他们索引到。另外，他们的结果还显示，不同语言的 web 子集其结构有相当大的区别，其中最突出的特点是英语的页面无疑是 web 的核心，其他语言的网页有很多指向英语网页的链接，而反过来的情况则相当的少。最后是中文 web 的情况，今年 jonathan j. h. zhu 等的分析将中文 web 形容为“茶壶”的结构：相比 in 组件，out 组件的变小了很多，因而在 scc 两侧构成了一大一小形如“把手”和“壶嘴”的结构，而游离的 tendril 组件则很像壶中滴下的水滴。