搜索引擎背后的经典数据结构和算法( 二 ) _搜索引擎

文章插图

二、预处理爬取完一个网页后我们需要对其进行预处理，我们拿到的是网页的 html 代码，需要把 ,,，找到之后，把起始终止标签及其中的内容全部去掉即可。
做完以上步骤后，我们也要把其它的 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）算法有关，大家可以去了解一下。
另外相信大家在搜索框输入搜索词的时候，都会注意到底下会出现一串搜索提示词，