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

互联网搜索引擎的算法--树和StopLead

11. 09. 2016

Obsah článku

每秒钟都有500万个新网页被添加到互联网上,而且这个速度还在不断增加。为了给这个巨大的信息海洋提供一些秩序,并在其中找到一些东西,就有了搜索引擎。下面的工作旨在介绍搜索的问题,并解释从创建一个新网页到在搜索引擎中找到它的整个过程。

寻找和整理一组数十亿的文件的任务并不容易。仅谷歌就需要30万台网络服务器来处理这项任务,只需几个小时。事实上,在你提出问题之前,对你的询问的搜索就已经发生了。谷歌已经将你在未来几天要求的搜索结果储存在其内存中。

搜索引擎架构

用于多达5000万份文件的通用搜索引擎架构

一个正确设计的搜索引擎包含许多组件,其中有几百个组件的数量。这张图描述了一个搜索引擎至少必须包含的最基本元素,以便发挥作用。这是一个古老的、不再使用的架构,大约在2005年之前一直有效,当时网络上只有几百万个文档。这种结构不允许有 "无限 "的内容,也不允许搜索服务器(基础搜索)可能的停机。如果有一个组件发生故障,整个系统将停止运作,搜索引擎将无法使用。

对当前新架构设计的趋势的完整描述超出了本文的范围,因为这些通常是大公司的商业机密。本文的目的将是解释这个基本架构是如何工作的。各个组成部分将在以下章节中详细解释。

查询输入

即使对普通用户来说,最明显的组件也是查询输入,目前最常表现为一个文本框。输入栏位于一个特殊的页面上,通常只用于输入。

在下一阶段,用户输入搜索字符串并向搜索引擎服务器提交表格,从而启动与配药组件的通信,有时也称为主搜索。配药服务器是为处理来自用户的巨大负荷而建立的,必须能够同时处理所有的搜索者。

调度服务器的架构通常是一个简单的Apache服务器,具有基本的安装和出色的网络带宽。当一个查询进入服务器时,它通过回归决策树进行处理,并创建一个 "查询地图",捕捉到围绕其他含义的完整语义,以明确用户实际上在寻找什么。查询重写方法超出了本文的范围,所以我们只展示重写可以和不能的一般描述。

考虑以下查询。

"O pejskovi a kočičce"

这个查询将被转换为二进制树,以捕捉其语义本质。

符号解析树图

解析树的全部意义在于捕捉搜索引擎将如何看待搜索结果。这棵树和查询一起被送出到辅助搜索服务器(在本文中标记为基地搜索),在那里搜索各个关键词(索引读取),然后根据规则进行排序(通过操作)。

操作员 排序操作
AND Intersection
OR 总和
补码 不补码

没有实际的搜索结果排序,这个组件只是对大量的数据(通常是数以百万计的记录)进行快速的二进制运算,基本上只是对各个文件的ID进行比较。

结果页搜索结果的实际排序方式将在以下章节中讨论。输出服务器只是用来组合来自不同搜索服务器的大量数据,以提高整体性能和分散负载,然后将检测到的数值送入结果页面(这被称为 "网页"),包含来自几十个服务器的复合信息。

重写为二叉树

正如前一章所提到的,整个搜索是建立在二进制树上的,它告诉你结果会是什么样子,以及要寻找什么。搜索引擎的整个 "逻辑 "和 "智能 "直接取决于创建树的程序的质量 - 即描述符。

一个正确构建的树应该包含关于查询的所有必要的元信息,其形式即使在磁盘顺序读取的帮助下也可以很容易地处理,并且应该消除对内存的随机访问,因此它通常包含单个搜索词(来自用户)、它们的转录(和拼出的形式)以及最后但并非最不重要的词之间的链接,即它们在文本中的相对距离。

查询转录方法

转录查询的最基本方法是将其解析为单个单词(根据空格),这些单词将被进一步处理。第二步是搜索StopWords,并用一个变量指针取代它们(因为,正如我们将在后面展示的,搜索StopWords根本没有意义)。

我们有如下查询:"关于一只狗和一只猫",它的转录在最基本的状态下看起来像这样。

"O (and) pejskovi (and) a (and) kočičce"

第二步是消除与搜索无关的词语。当然,例如,"关于 "或 "和 "这个词对我们人类来说是有意义的,但对数据库搜索来说却没有意义,因为它可以被另一个词所取代,并列出结果。我们的目标不应该是找到与索引的字面匹配的查询,因为这将导致糟糕的结果,因为互联网上文本中的单词往往有不同的拼法,这种方法试图找到比我们从用户那里得到的结果更多的其他形式。因此,这是一个 "智能 "搜索引擎的第一个迹象。

这些无意义的词通常被称为 "止损词",每个搜索引擎都应该保留一个此类词的索引,并且这个索引应该经常更新(手动)。

["pejskovi (and) * (and) kočičce"]

在这一点上,我们正在寻找2个不同的词("狗 "和 "猫"),中间还有一个词(在内部,我们用星号标记)。

这种修改的目的不是为了提高搜索的质量,而是为了提高性能。这是因为当我们搜索一个过于频繁的词时,会有一个快速的负载,而这种修改有助于这个过程--特别是不搜索一个无论如何会在大多数文件中的那个位置出现的词。

还需要注意的是,我们不能总是进行这种调整(省略一个词),所以每个搜索引擎都应该保留一个单独的短语索引,以检查哪种调整能带来好的结果,哪种不能。然而,偶尔搜索引擎会做出这种调整,即使它的索引中没有这个短语--特别是当用户在搜索一个重要的词时,预计会有重要的页面出现在第一位置,这些页面会覆盖这个 "错误",因为用户通常无论如何都会请求它们。

最后一步是与英语合作,"清理 "查询中不必要的字符。例如,在查询 "洗衣机 "时,用户通常只期望得到 "洗衣机 "一词的结果,我们可以忽略逗号字符。

这个系统如何工作的确切方法并不为人所知,每个搜索引擎都有自己的方法。据认为,它主要只是一个统计模型,根据数据库中数十亿文本的知识来进行这些调整。

英语转录本身也是一门科学,所以这里也只做一个基本描述。在大多数情况下,只需将其连字符形式(根据字典)添加到每个词中,并与该词一起搜索,从而达到这样的效果:搜索引擎可以找到该词不仅以其基本形式(由用户输入)出现的文件,而且还可以找到转折的版本--这是一个非常有用的功能。这种方法的问题在于晦涩难懂和有问题的词的转折,也在于对短小的查询的转折(因此不可能从上下文中确定如何转折该词)。让 "游戏 "这个词成为一个有问题的转折点的例子。

给出一个英语查询,"我爱她",一个设计不良的转折器会将 "游戏 "这个词转折为,例如,"游戏,游戏,游戏室,......",所以也有必要将周围的词作为短语索引,只在熟悉的情况下进行转折,或者使用不同的程序(这就是语音算法经常出现的地方)。

最后一步是将完成的树发送到基地搜索服务器,在那里将进行实际的桶式搜索--这是下一章的主题。

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.