ZAČÁTKYNÁVODYOOPDOKUMENTACE
教程/
互联网搜索引擎的算法

互联网搜索引擎的算法--几乎没有爬虫

11. 09. 2016

Obsah článku

在今天的课程中,我们将讨论数据桶、其结构、StopSlovas,最后我们将描述爬虫。

数据桶

这是一种特殊的数据类型,同时驻留在多个服务器上的多个副本中。通常,这些都是数据密集型文件,大小达数百GB,读取速度很慢(这就是为什么它们被分割成若干部分),而且几乎不可能编辑。如果我们想做哪怕是最小的改变,我们必须重新计算整个桶。例如,搜索引擎Seznam最多几天或几周就能重新计算一次数据桶,而谷歌则是几小时就重新计算一次(而且只是一些部分,从来没有一次全部计算过)。

桶中包含单词和它们在互联网上的出现情况。可以说这是尚未排序的搜索结果的原始数据(有时是按相对重要性进行部分排序),是事先准备好的。搜索本身早在用户提出搜索查询之前就发生了,所有的结果都是在这里准备的。搜索本身是不可能实时进行的,所以搜索引擎基本上是读取这里已经准备好的结果(搜索是由索引器组件完成的,这将在另一章讨论)。

这些桶包含了为互联网上出现的每一个词建立搜索结果所需的所有基本信息,因此在按顺序阅读时必须解决性能问题。在实践中,桶往往被分批存储在多个服务器上,也被存储在RAM中,以加快访问速度。例如,谷歌搜索引擎根本不从磁盘上读取木桶,而是将其完全保存在RAM中,只在磁盘上保留一份副本,以防RAM中的数据丢失。

拥有足够资源的大型搜索引擎也会保留所谓的 "黄金桶",其中包含互联网上最重要的网页,在搜索负荷大的情况下进行搜索。例如,如果几个搜索服务器崩溃,金桶就会暂时满足搜索的需要。搜索引擎可能不会找到所有的结果,但至少搜索不会完全中断,只是搜索的文件数量会暂时受到限制。还有必要定期更新桶,因为互联网上的网页数量在不断增加。由于桶的大小通常是以千兆字节为单位的,因此不可能进行增量维护,但有必要每隔设定时间重建一次。因此,搜索引擎保留了一个辅助桶,其中所有的数据都是以大表的形式建立的桶,例如,谷歌大约每12小时建立一次桶。最大的挑战恰恰是,这些桶必须至少部分排序,并反映互联网的实际状态。因此,在搜索引擎更新桶之前,用户不会找到新的网页。

桶状结构

在实践中,桶被存储为一个大的文本文件,其中包含搜索词出现的每个文档的ID和当前搜索词出现的位置。

一个非常小的木桶有三页的例子。

[1:5,8,12,27,30;5:1,3,6;12:4,8,10]

这个样本桶包含有标识符1512的页面。相关数字表示该词在文件中出现的位置。这样的筒子只捕捉到一个词的出现,所以互联网上的每个词都有自己的筒子。当搜索多个关键词时,有必要读取多个桶(每个词一个不同的桶),然后根据二叉树进行操作(更多内容见前面几章)。

交叉通常是通过翻阅其中一份文件和搜索另一份文件来完成。如果木桶很大,它们可能不会被完全读取,因此搜索引擎往往只能设法读取其中的一部分,然后不得不返回结果,因此至少对木桶进行部分排序是有意义的,这样最重要的页面(用户可能正在寻找的)就在木桶的开头,其他的都在木桶的结尾。

停止铅

你可能会想,对于某些词来说,桶可能真的很大,因此很难处理。例如,"a "字或 "1 "字在超过一半的文件中被发现,但它们对搜索者来说没有任何意义(因为它们很少被搜索到,需要更多的周边词)。这样的词被称为停止词。

StopWords的问题是,它们不能全部被搜索到,因此,搜索引擎只能显示搜索词在互联网上的实际情况,是一个扭曲的现实。

使用StopSlovy搜索的一个例子是查询 "布拉格1号"。

搜索引擎只给出了3,020,000条查询结果。然而,在现实中,这样的网站还有很多。然而,由于性能的原因,并不是所有的都被搜索到。

用StopSlovy搜索访问选项。

  • 根本不为它们编制索引,也不为它们制作木桶(小型搜索引擎会这样做)。
  • 对它们进行索引,但只在桶中存储相关的页面(例如,谷歌和Seznam就是这样做的)。
  • 将它们作为普通词进行索引,并创建完整的桶(这种解决方案有一个问题,即桶的大小很容易超过普通硬盘的大小,因此无法保存,并可能需要几秒钟的时间来阅读--因此这种解决方案在实践中并不使用,或者只用于小型和专门的搜索引擎。)

一般来说,没有普遍正确的方法,甚至谷歌也没有完美地使用它。这是一个巨大的问题,可能需要一生的时间来解决。然而,为了本文的目的,这种一般性的描述已经足够了。

爬行者(机器人,也是蜘蛛)。

爬虫是一个系统地抓取互联网的程序,并跟踪什么词出现在什么网页上,还收集辅助信息(也叫元信息)。爬虫通常在许多服务器上运行,因为抓取互联网对网络带宽的要求很高,因此必须同时抓取许多网页。谷歌估计,在任何时候都有多达3万个网页被同时抓取。

在打开一个页面之前,Crawler会查看一个数据库,了解它将来打算去哪些地址。如果它已经去过该地址,它只会更新其记录(它每隔几小时去一次主要网站,每隔几分钟去一次新闻网站,最多一个月去一次普通网站)。

如果机器人到达一个它不知道的新地址,它将查看包含的其他文件(页面)的链接。对于每个链接,它都会计算其重要性,如果它是一个重要的链接,它也会在后面的页面中出现。

例如,List只通过这种方式抓取每个网站的几层链接,而Google则试图抓取整个网站,包括不重要的文件,使其成为互联网上最全面的搜索引擎。 机器人在爬行过程中还试图对该网页进行排名,并计算其 "排名",这是一个数字,表示该网页在互联网上的重要性。在过去,谷歌使用PageRank,其范围从0到10。谷歌只为自己和诸如microsoft.com或w3c.org等网站计算PageRank 10。现在它的计算方式不同(人工智能和矢量数学)。

在捷克,PageRank最高的是Seznam.cz,数值为7。该排名对机器人访问该网页的频率和它在搜索结果中的排名有很大影响。排名的计算仅仅来自于指向所需页面的反向链接。

爬虫对数据不做任何其他处理,它只是从互联网上下载数据并将其存储在数据库中,等待索引过程。

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Související články

1.
3.