作者|代码海
编辑| hxdxn/p
前言
我们每天都在使用谷歌、百度这些搜索引擎。 那么，你有没有想过搜索引擎是如何实现的？ 看似简单的搜索其实技术细节非常复杂，可以毫不夸张地说搜索引擎是IT皇冠的明珠。 今天我们来简单看看搜索引擎的原理，看看它是如何工作的。 当然搜索引擎博大精深，不可能用一篇文章完全介绍。 我们只介绍其中最重要的几个步骤，万变不离其宗，搜索引擎离不开这些关键步骤，剩下的只是在上面添砖加瓦，所以要掌握这些“关键路径”
本文从以下几个部分介绍了搜索引擎，深入分析了搜索引擎的工作原理以及其中使用的一些经典数据结构和算法，相信大家看到后一定会有收获。
搜索引擎系统体系结构图
详细解析搜索引擎的工作原理
搜索引擎系统架构图整个搜索引擎的架构图大致分为采集、预处理、索引、查询四个步骤，每一步的技术细节较多，下面将详细分析每一步的工作原理
http://www.Sina.com/http://www.Sina.com /
爬虫类一开始不知道该从哪里开始，所以制作了新浪主页、腾讯主页等知名且在Alexa排行榜上也排名靠前的优质种子页面的链接，以广度优先遍历这些页面，获取页面内容，其中的莉莉.
当然，仅有爬行动物是不够的，还可以启动多种爬行动物并行攀登。 那样的话，速度会变得快很多。
搜索引擎工作原理详细剖析
爬网的url可以放入Redis中，保证了高性能。 注意，Redis将打开持久化功能，以支持断点的连续爬网。 如果Redis锁定，重新启动后将具有永久功能，因此可以从上一个要爬网的url重新爬网。
一、搜集
如何避免网页重复？ 需要重新操作url。 如何实现再操作？ 有些人可能会使用哈希表将每个捕获的url保存在哈希表中，并在每次添加捕获的url时确定是否使用此哈希表进行了爬网，但这确实没有问题。 但是，这需要花费很大的空间成本，需要注意的是需要多大。 如果你简单计算一下，假设你有10亿个url (
假设每个网页的url平均长度为64字节，则10亿个url需要大约60 G的内存。 如果用散列表实现，则散列表中需要较小的加载因子以避免过多的冲突，因此，如果假设将10个元素加载到散列表中以避免散列冲突，则实际上为避免散列冲突分配20个元素的空间)要保存指针，两者加起来所需的内存可能超过100 G。 此外，冲突时需要在链表中比较字符串，在性能上也是损失。 当然，100 G对大型搜索引擎来说不是大问题，但实际上也有方案可以实现远远小于100 G的内存。 是布隆过滤器。
对于10亿个url，我们分配了100亿个bit，约1.2 G，比100 G的内存提高了近百倍！ 可见，技术方案的合理选择可以很好地达到降本增效的效果。
可能会出现这样的问题：如果判断某个值在布隆过滤器中不存在，布隆过滤器就一定不存在，但如果判断在布隆过滤器中存在，就一定不存在布隆过滤器。 在这种情况下，可以通过调整布隆过滤器的哈希函数和下面的位图的大小来尽量降低误判的概率，但是如果发生了误判，用这样的url是爬不上去的。 因为互联网上有很多网页
1、待爬取的 url 实现
爬上网页后，网页该怎么保存呢？ 有人说，在一个网页上保存文件不就行了吗？如果是这样的话，每10亿页就保存10亿个文件。 由于典型的文件系统不支持，因此通常将网页内容保存到一个文件(假设为doc_raw.bin )中。 如下所示
当然，典型的文件系统对单个文件的大小也有限制。 例如，如果是1 G的话，在文件超过1 G后再创建新的文件就可以了。
图中的网页id是如何生成的，显然是ur
l 对应一个网页 id，所以我们可以增加一个发号器，每爬取完一个网页，发号器给它分配一个 id，将网页 id 与 url 存储在一个文件里，假设命名为 doc_id.bin,如下二、预处理
爬取完一个网页后我们需要对其进行预处理，我们拿到的是网页的 html 代码，需要把 <script>,<style>,<option> 这些无用的标签及标签包含的内容给去掉，怎么查找是个学问，可能有人会说用 BF ，KMP 等算法，这些算法确实可以，不过这些算法属于单模式串匹配算法，查询单个字段串效率确实不错，但我们想要一次性查出<script>,<style>,<option>这些字段串，有啥好的方法不，答案是用AC 自动机多模式串匹配算法，可以高效一次性找出几个待查找的字段串，有多高效，时间复杂度接近 0(n)！关于 AC 自动机多模式匹配算法的原理不展开介绍，大家可以去网上搜搜看， 这里只是给大家介绍一下思路。
找到这些标签的起始位置后，剩下的就简单了，接下来对每个这些标签都查找其截止标签 </script>,</style>,</option>，找到之后，把起始终止标签及其中的内容全部去掉即可。
做完以上步骤后，我们也要把其它的 html 标签去掉（标签里的内容保留），因为我们最终要处理的是纯内容（内容里面包含用户要搜索的关键词）
三、分词并创建倒排索引
拿到上述步骤处理过的内容后，我们需要将这些内容进行分词，啥叫分词呢，就是将一段文本切分成一个个的词。比如 「I am a chinese」分词后，就有 「I」,「am」,「a」,「chinese」这四个词,从中也可以看到，英文分词相对比较简单，每个单词基本是用空格隔开的，只要以空格为分隔符切割字符串基本可达到分词效果，但是中文不一样，词与词之类没有空格等字符串分割，比较难以分割。以「我来到北京清华大学」为例，不同的模式产生的分词结果不一样，以 github 上有名的 jieba 分词开源库为例，它有如下几种分词模式
【全模式】: 我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学【精确模式】: 我/ 来到/ 北京/ 清华大学【新词识别】：他, 来到, 了, 网易, 杭研, 大厦【搜索引擎模式】： 淡淡的萝莉, 硕士, 毕业, 于, 中国, 科学, 学院, 科学院, 中国科学院, 计算, 计算所, 后, 在, 日本, 京都, 大学, 日本京都大学, 深造分词一般是根据现成的词库来进行匹配，比如词库中有「中国」这个词，用处理过的网页文本进行匹配即可。当然在分词之前我们要把一些无意义的停止词如「的」,「地」,「得」先给去掉。
经过分词之后我们得到了每个分词与其文本的关系，如下
细心的你一定发现了，不同的网页内容有可能出现同样的分词，所以我们把具有相同分词的网页归在一起，如下所示
这样我们在搜「大学」的时候找到「大学」对应的行，就能找到所有包含有「大学」的文档 id 了。
看到以上「分词」+「倒排索引」的处理流程，大家想到了什么？没错，这不就是 ElasticSearch 搜索引擎干的事吗，也是 ES 能达到毫秒级响应的关键！
这里还有一个问题，根据某个词语获取得了一组网页的 id 之后，在结果展示上，哪些网页应该排在最前面呢，为啥我们在 Google 上搜索一般在第一页的前几条就能找到我们想要的答案。这就涉及到搜索引擎涉及到的另一个重要的算法: PageRank，它是 Google 对网页排名进行排名的一种算法，它以网页之间的超链接个数和质量作为主要因素粗略地分析网页重要性以便对其进行打分。我们一般在搜问题的时候，前面一两个基本上都是 stackoverflow 网页，说明 Google 认为这个网页的权重很高，因为这个网页被全世界几乎所有的程序员使用着，也就是说有无数个网页指向此网站的链接，根据 PageRank 算法，自然此网站权重就啦，恩，可以简单地这么认为，实际上 PageRank 的计算需要用到大量的数学知识，毕竟此算法是 Google 的立身之本，大家如果有兴趣，可以去网上多多了解一下。
完成以上步骤，搜索引擎对网页的处理就完了，那么用户输入关键词搜索引擎又是怎么给我们展示出结果的呢。
四、查询
用户输入关键词后，首先肯定是要经过分词器的处理。比如我输入「中国人民」，假设分词器分将其分为「中国」,「人民」两个词，接下来就用这个两词去倒排索引里查相应的文档
得到网页 id 后，我们分别去 doc_id.bin，doc_raw.bin 里提取出网页的链接和内容，按权重从大到小排列即可。
这里的权重除了和上文说的 PageRank 算法有关外，还与另外一个「 TF-IDF 」（https://zh.wikipedia.org/wiki/Tf-idf）算法有关，大家可以去了解一下。
另外相信大家在搜索框输入搜索词的时候，都会注意到底下会出现一串搜索提示词，
如图示：输入 chin 这四个字母后，底下会出现一列提示词。
如何实现的，这就不得不提到一种树形结构：Trie 树。Trie 树又叫字典树、前缀树（Prefix Tree）、单词查找树，是一种多叉树结构，如下图所示：
这颗多叉树表示了关键字集合 ["to"，"tea"，"ted"，"ten"，"a"，"i"，"in", "inn"]。从中可以看出 Trie 树具有以下性质：
根节点不包含字符，除根节点外的每一个子节点都包含一个字符
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符互不相同
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。
另外我们不难发现一个规律，具有公共前缀的关键字（单词），它们前缀部分在 Trie 树中是相同的，这也是 Trie 树被称为前缀树的原因，有了这个思路，我们不难设计出上文所述搜索时展示一串搜索提示词的思路：
一般搜索引擎会维护一个词库，假设这个词库由所有搜索次数大于某个阈值（如 1000）的字符串组成，我们就可以用这个词库构建一颗 Trie 树，这样当用户输入字母的时候，就可以以这个字母作为前缀去 Trie 树中查找，以上文中提到的 Trie 树为例，则我们输入「te」时，由于以「te」为前缀的单词有 ["tea"，"ted"，"ted"，"ten"]，则在搜索引擎的搜索提示框中就可以展示这几个字符串以供用户选择。
五、寻找热门搜索字符串
Trie 树除了作为前缀树来实现搜索提示词的功能外，还可以用来辅助寻找热门搜索字符串，只要对 Trie 树稍加改造即可。假设我们要寻找最热门的 10 个搜索字符串，则具体实现思路如下:
一般搜索引擎都会有专门的日志来记录用户的搜索词，我们用用户的这些搜索词来构建一颗 Trie 树，但要稍微对 Trie 树进行一下改造，上文提到，Trie 树实现的时候，可以在节点中设置一个标志，用来标记该结点处是否构成一个单词，也可以把这个标志改成以节点为终止字符的搜索字符串个数，每个搜索字符串在 Trie 树遍历，在遍历的最后一个结点上把字符串个数加 1，即可统计出每个字符串被搜索了多少次（根节点到结点经过的路径即为搜索字符串），然后我们再维护一个有 10 个节点的小顶堆（堆顶元素比所有其他元素值都小，如下图示）
如图示：小顶堆中堆顶元素比其他任何元素都小
依次遍历 Trie 树的节点，将节点（字符串+次数）传给小顶堆，根据搜索次数不断调整小顶堆，这样遍历完 Trie 树的节点后，小顶堆里的 10 个节点即是最热门的搜索字符串。
总结
本文简述了搜索引擎的工作原理，相信大家看完后对其工作原理应该有了比较清醒的认识，我们可以看到，搜索引擎中用到了很多经典的数据结构和算法，所以现在大家应该能明白为啥 Google, 百度这些公司对候选人的算法要求这么高了。
本文只是介绍了搜索引擎的基本工作原理，要深入了解还需多查资料了解哦。
更多精彩推荐☞中国开启开源新纪元！☞港中文用 Zoom 考试，中途遭黑客入侵传播不可描述内容☞360金融新任首席科学家：别指望AI Lab做成中台☞AI图像智能修复老照片，效果惊艳到我了☞程序员内功修炼系列：10 张图解谈 Linux 物理内存和虚拟内存☞当 DeFi 遇上 Rollup，将擦出怎样的火花？你点的每个“在看”，我都认真当成了喜欢