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

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

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

搜索引擎架构

。

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

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

查询输入

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

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

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

考虑以下查询。

"O pejskovi a kočičce"

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

。

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

没有实际的搜索结果排序，这个组件只是对大量的数据（通常是数以百万计的记录）进行快速的二进制运算，基本上只是对各个文件的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:

Kontakt