本章关键词
搜索引擎、数据结构、算法
这一章节会简要介绍搜索引擎的设计方法，包括常用的数据结构、算法和设计思路。
搜索引擎的设计是非常复杂的工程，在这里我们只简要介绍其中的几个关键结点，通过这几个结点，我们就可以制作出一个可以使用的搜索引擎了。
整体系统介绍
搜索引擎大致可以分为四个部分：搜索、分析、索引、查询：
- 搜索：利用爬虫爬取网页
- 分析：负责网页内容的分析
- 索引：为网页构建索引
- 查询：响应用户的请求
1.搜集
搜索引擎把整个互联网当做数据结构中的有向图，把每个页面看作一个顶点。在网页中的超链接，就是各个顶点之间的边。我们可以通过图的遍历搜索算法（在这里选择广度优先遍历）获取整个互联网中的网页。
基本的原理就是这么简单，在工程层面，还有许多技术细节需要我们注意，这里，借助搜索涉及的几个重要文件，像你解释这些细节：
1.1待爬取网页链接文件：links.bin
在广度优先搜索爬取页面的过程中，需要维护一个爬取网页的 url 队列。
这个队列会占用大量内存，所以我们要将它保存到硬盘中（即 links.bin 文件）。一方面，这可以减轻内存的压力，另一方面，这样可以支持断点续爬。
1.2网页判重文件：bloom_filter.bin
爬取网页中一定会涉及到重复网页的问题，这个问题在之前的位图那一节已经讲过了，这里直接说思路：
- 使用布隆过滤器对网页 url 进行判重
- 定时将这个过滤器存入硬盘（即 bloom_filter.bin 文件），以支持断点续爬
1.3原始网页存储文件：doc_raw.bin
对爬取到到网页，我们要将它存储下来，以备之后使用。那么该如何存储这样海量的原始网页数据呢？
- 如果我们单独保存每个文件，文件的数量就会非常多，这对文件系统是不友好的。
-
我们可以将许多网页打包存储，可以如下图所示（其中的网页编号稍后会讲解）：
文件保存.jpg
- 当然，每个文件不能太大，我们可以为文件设置一个阈值，比如 1GB 。
1.4网页链接和网页编号的对应文件：doc_id.bin
正常来说，我们可以使用网页的 url 作为其唯一标识，但是这样会浪费较多的存储空间，也会降低之后的操作性能。所以，我们需要为网页设置编号：
- 我们可以设置一个计数器，每爬取一个新网页，就使用计数器为网页设置分配一个唯一 ID 。
- 我们将这样的对应关系，存储在 doc_id.bin 中。
在“搜集”这一过程中，涉及到了四个重要文件，前两个文件是爬虫自身使用，后两个文件作为阶段性成果，为之后的分析、索引、查询过程提供支持
2.分析
在获取网页之后，我们需要对网页进行离线分析。这一阶段主要有两个步骤：抽取网页文本信息 和 创建临时索引。
2.1抽取网页文本信息
在网页中，有各种标签、JS代码、CSS样式等，这些信息对搜索引擎来说并不重要，所以我们可以将它过滤出去：
- 去除 JS、CSS、下拉框中的内容，也就是<style></style>，<script></script>，<option></option>这三组标签之间的内容。
- 我们可以使用 AC自动机 对网页进行进行匹配和删除。
- 去除 HTML 标签，这一步和上面的方法类似。
2.2分词并创建临时索引
通过上面的处理，我们从网页中提取了文本信息，下面我们要对文本进行分词，并进行创建临时索引。
- 相比英文来说，中文的分词更加复杂，这里用一种比较简单的思路，基于字典和规则的分词方法。
- 字典也叫词库，其中包含了大量常用词语。我们借助词库采用最长匹配规则，对文本进行分词。
- 用 Trie树 进行查询比较高效。
- 分词完成之后，我们将单词和网页对应的索引关系写入临时索引文件（tmp_Index.bin）中，其格式如下：
临时索引文件.jpg
- 对单词进行编号，可以使用对网页编号的相同思路。
- 对单词进行编号，需要使用散列表，记录单词和编号之间的映射关系，且防止重复编号。在分析完成之后，我们将这个映射关系写入硬盘，命名为 term_id.bin。
在分析阶段，我们得到了两个重要文件：临时索引文件(tmp_Index.bin) 和 单词编号文件(term_id.bin)。
3.索引
在上一阶段，我们得到了临时索引文件（网页->关键词），在这一阶段，我们要使用临时索引构建倒排索引（关键词 -> 搜索网页）。倒排索引(index.bin)的结构如下：
倒排索引.jpg
构建倒排索引的方法很多。由于临时索引的文件很大，无法一次性加载，搜索引擎会选择使用多路归并排序的方法实现。
- 先对临时文件，按照单词大小进行排序。由于临时索引很大，所以我们采用分治的思想，将其分割成多个小文件，依次处理这些小文件。
- 排序完成，我们只需要顺序遍历临时索引文件，就可以将每个单词对应的网页编号找出，然后把他们存在倒排索引文件中。
-
具体过程可以看下面的图：
构建倒排索引.jpg
索引偏移.jpg
经过这一阶段处理，我们得到了两个文件：倒排索引文件（index.bin），和索引偏移位置文件（term_offset.bin）
4.查询
有了前三个阶段的铺垫，我们就可以利用之前产生的文件来实现用户的搜索功能了，这里要用到以下四个文件：
- doc_id.bin：记录网页链接和编号之间的对应关系。
- term_id.bin：记录单词和编号之间的对应关系。
- index.bin：倒排索引文件，记录每个单词编号以及对应包含它的网页编号列表。
- term_offsert.bin：记录每个单词编号在倒排索引文件中的偏移位置。
下面直接借用作者的话描述整个搜索过程：
这四个文件中，除了倒排索引文件（index.bin）比较大之外，其他的都比较小。为了方便快速查找数据，我们将其他三个文件都加载到内存中，并且组织成散列表这种数据结构。
当用户在搜索框中，输入某个查询文本的时候，我们先对用户输入的文本进行分词处理。假设分分词之后，我们得到 k 个单词。
我们拿这 k 个单词，去 term_id.bin 对应的散列表中，查找对应的单词编号。经过这个查询之后，我们得到了这 k 个单词对应的单词编号。
我们拿这 k 个单词编号，去 term_offset.bin 对应的散列表中，查找每个单词编号在倒排索引文件中的偏移位置。经过这个查询之后，我们得到了 k 个偏移位置。
我们拿这 k 个偏移位置，去倒排索引（index.bin）中，查找 k 个单词对应的包含它的网页编号列表。经过这一步查询之后，我们得到了 k 个网页编号列表。
我们针对这 k 个网页编号列表，统计每个网页编号出现的次数。具体到实现层面，我们可以借助散列表来进行统计。统计得到的结果，我们按照出现次数的多少，从小到大排序。出现次数越多，说明包含越多的用户查询单词（用户输入的搜索文本，经过分词之后的单词）。
经过这一系列查询，我们就得到了一组排好序的网页编号。我们拿着网页编号，去 doc_id.bin 文件中查找对应的网页链接，分页显示给用户就可以了。
总结
这是一个比较简单的搜索引擎设计速路，很多设计细节都没有涉及。
在这个设计中，我们涉及到了很多数据结构和算法：图、散列表、Trie 树、布隆过滤器、单模式字符串匹配算法、AC 自动机、广度优先遍历、归并排序等。
如果有机会，建议自己将这个引擎设计出来。
以上就是本节的全部内容，希望可以了解到数据结构和算法的妙用
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论