教学参考-35

教学目标

• 了解倒排索引对搜索引擎的重要意义
• 了解Pagerank算法在评估网页重要性中的作用

教学内容

什么是搜索引擎

• 互联网上有海量资源，而且每天在以惊人的速度增长，没有谁能记住自己想要资源在什么地方。这就像一个宝藏丰富的大陆缺少藏宝地图，资源再多也没有意义。搜索引擎就是这个藏宝地图，它能帮助我们快速找到想要的资源。
• 最早的搜索引擎可能是 1990 年的 Archie 系统，这一系统是针对 FTP服务资源的搜索器。 1993 年，第一个面向网页的搜索引擎 World Wide Web Wanderer 出现。
• 1996 年， Larry Page 与 Sergey Brin 在斯坦福大学开始名为 BackRub的研究项目，这一项目成为 Google 的前身。 1998 年， Google 公司正式成立，成为搜索界乃至整个互联网时代毫无悬念的霸主。
• 2000 年，百度公司作为技术提供商上线，并很快成为国内搜索引擎的龙头。

搜索引擎的基本原理：倒排索引

• （ 搜索引擎要解决的第一个问题是如何在海量数据里搜索到相关的文章。例如，我们想要搜索和”谷歌地图”相关的文档。最直观的做法是把网上的文章一篇篇拿过来检查一下，看看是否包含“谷歌”和”地图”这两个词。显然，这种做法太慢了，而且随着网上文档的增长，搜索的速度会越来越慢。
• 人们提出了一种称为“倒排索引”的方案。

• 确定一批关键词，如“谷歌”, “地图”, “之父”等，为每个关键词建立一个空的索引项，称为倒排索引。
• 离线处理每篇文章，如果它包含某个关键词K，则把这篇文章加入到K的倒排索引中。处理完成后，每个关键词的倒排索引中就包含了所有与之相关的文档。右图是用5篇文档生成的一个倒排索引表。
• 处理搜索请求时，如“谷歌创始人”，首先查找“谷歌”和“创始人”的倒排索引，找到各自对应的文档。如果某个文档在两个关键词的倒排索引中都存在，则该文档被定位为与搜索请求相关。在右图的倒排索引中，文档3是最匹配的结果。

• 在实际搜索引擎中，倒排索引除了关键词所在的文章外，还记录了该关键词在该文章中的位置以及一些特别属性，比如是否在标题中、是否是高亮词、字体的大小等，这些属性可以用在相关性计算中，用以提高输出排序的合理性。

网页重要性评价

• 另一种方式是基于网页间的链接来判断网页的重要性。我们知道一个网页中往往会有一些超链接，用户点击这些链接会指向其他网页。如果一个网页被很多网页链接，那么有理由相信该网页比较重要。
• 如果我们将网页之间的链接关系表示成一张图，其中节点表示网页，节点间的边表示两个网页之间存在链接，边的方向代表链接指向。依前述讨论，如果某个节点被很多边链接，则该节点是一个重要节点，对应的网页比较重要。
• 按照外部链接个数来判断网页重要性并不完全准确，因为不同的链接本身的重要性是不一样的：来自重要网页的链接比来自普通网页的链接应更受重视。换句话说，如果当前网页被某个重要网页链接，说明这个网页自身也是重要的。基于这一思路，在计算网页重要性时可以将链接的重要性考虑在内，使得重要性的计算更合理。
• 谷歌的PageRank算法实现了这一思路。初始时，所有网页的重要性都是一样的，但每个网页都会向它链出的网页发送信息，网页根据它所接收的信息更新自身重要性。如果一个网页被很多网页链接，它会收到更多信息，重要性会增加。这样循环迭代更新，最后达到稳定状态时，每个网页的重要就可以计算出来了。