2019-01-28思考题 1:
因为搜索引擎要优先爬取权重较高的页面，离种子网页越近，较大可能权重更高，广度优先更合适。
思考题 2:
摘要信息：
增加 summary.bin 和 summary_offset.bin。在抽取网页文本信息后，取出前 80-160 个字作为摘要，写入到 summary.bin，并将偏移位置写入到 summary_offset.bin。
summary.bin 格式：
doc_id \t summary_size \t summary \r\n\r\n
summary_offset.bin 格式：
doc_id \t offset \r\n
Google 搜索结果中显示的摘要是搜索词附近的文本。如果要实现这种效果，可以保存全部网页文本，构建搜索结果时，在网页文本中查找搜索词位置，截取搜索词附近文本。
网页快照：
可以把 doc_raw.bin 当作快照，增加 doc_raw_offset.bin 记录 doc_id 在 doc_raw.bin 中的偏移位置。
doc_raw_offset.bin 格式：
doc_id \t offset \r\n展开 45
2019-01-28倒排索引中记录了每个单词以及包含它的网页列表，想问一下“倒排索引”这个名字是怎么来的？其中的“倒排”体现在哪里呢？作者回复: 正排-》文档包含哪些单词
倒排-》单词被哪些文档包含 38
2019-07-15感谢争哥的分享，我按照你这个思路，使用java语言，将这个搜索引擎的代码实现了出来，现在我也分享给大家，希望对那些希望实现搜索引擎，遇到了问题，却又不知道如何解决的童鞋，有所帮助，我的github地址: https://github.com/kkzfl22/searchEngine.git 28
2019-01-28搜集：将广度优先搜索的优先队列存储在磁盘文件links.bin（如何解析网页内的链接？），有布隆过滤器判重并定期写入磁盘文件bloom_filter.bin，将访问到的原始网页数据存入磁盘文件doc_raw.bin，计数分配网页编号并与其链接对应关系存入磁盘文件doc_id.bin。
分析：首先抽取网页文本信息，依据HTML语法规范，通过AC自动机多模式串匹配算法，去除网页中格式化部分，提取文本内容。然后分词并创建临时索引，分词的目的是找到能够标识网页文本“身份”的特征，可借助词库（通过Trie树实现）搜索文本中与词库匹配的最长词语，因为一般情况下越长信息越多，越剧有表征能力（为什么英文简单？）。分词完成后得到一组用于表征网页的单词列表，与其对应的网页编号存入磁盘文件tmp_index.bin作为临时索引，为节省空间单词是以单词编号的形式写入，单词文本与编号的对应关系写入磁盘文本term_id.bin。
索引：通过临时索引构建倒排索引文件index.bin。倒排索引其实是以单词为主键，将临时索引中的多个相同单词行合并为一行。通过以单词为主键的排序算法，可以将相同单词的行连续排列在一起，之后只要将单词相同的连续行合并为一行即可。由于数据量大，应采用分治策略。最后建立所有单词在倒排索引文件中位置的索引文件term_offset.bin，以方便快速查找。
查询：先对搜索条件文本做分词处理，然后去term_id.bin查单词们的编号，再查term_offset.bin找到单词们在倒排索引中的位置，到index.bin找到每个单词对应的网页编号，通过网页出现次数、预评权重和统计算法（如pagerank、tf-idf）计算网页的优先次序并输出。最后在doc_in.bin中找到网页链接按序输出显示给用户。
这样理解对不？展开作者回复: 赞
12
2019-01-30经过深入研究了一把，第一题终于有了比较清晰的答案：
从时间复杂度这个维度来考虑，BFS和DFS爬取互联网上所有的内容所需的时间是一样的。但是，我们设计爬虫系统的时候，不可能想着一次性爬完所有的网页，因为「量」太大了。所以，必须有一个优先级，不难想到：每一个网站的首页优先级最高，所以，我们肯定要先爬取每个网站的首页。从这一点出发，我们肯定要选取BFS。
但是，这里还有另外一个问题：如果我们爬完一个网站的首页之后，再爬取另外一个网站的首页，每次和不同网站服务器都要建立网络连接(TCP三次握手、HTTPs网站还要建立SSL握手等）都要花费大量的时间。如果总是按照BFS的策略来爬取，这中间花费的时间成本又太大了。所以，我想，中间肯定也是需要用DFS的。
我想到，可以使用一个优先级队列来维护需要爬取的网页。剩下的问题就是：该如何评估所需要爬取的网页的优先级呢？ 这个问题想了很久，依然不知道该如何计算机网页的优先级，难道这里也用PageRank类似的算法？展开 1 8
2019-08-27毕业设计就是做的搜索引擎，十万个本地文档构建的倒排索引，不过我的倒排索引直接用单词了，没有编号，用开源库分词，实现了tf-idf和文档之间相似度的计算，用动态规划来实现文本纠错，可以纠正用户的搜索框的错误输入，用到的数据结构不多，主要是哈希表和vector，用内存缓存查询结果，不知道算不算快照，哈，离老师讲的似乎只有分布式爬虫和临时索引的合并没有实现，
https://github.com/chawlau/search_engine，其他人看了不要喷我 7
2019-01-28作者讲的基本和elasticsearch原理查不多，可见有了算法基础以后了解一些中间件原理会容易很多，我最开始看es原理时一脸懵逼。 5
2019-01-28有没有代码实现的例子？作者回复: 木有。等我有空了可以写下分享出来。
4- 2019-10-21老师好 看了这篇之后我也想实现一个搜索引擎 现在很多公司里应该都用的cpp吧 我也想用cpp实现一个 请问下有没有可参考的代码 怕写到一半写不下去😂
作者回复: 我写过一个5万行的搜索引擎，cpp实现的，还有对应的几十页的文档，等过一整子整理一下放到公号众里：小争哥
3 
2019-03-14王老师，很惭愧在前一阵子落下了这门课程，平心而论您的课程真的是太优秀了，从我的角度来说真的极大地提升的见世面与知识基础。虽然停滞了很长一段时间没有学习，但我很相信这门课程是可以陪伴我很久然后学习两遍到三遍的，已经关注老师的公众号， 希望继续产出高质量的内容，祝好~ 3
2019-01-29可以讲讲到排序索引和普通索引区别？作者回复: 啥事排序索引和普通索引呢？我文中好像没讲到呢
2
2019-12-02‘带宽是 10MB，那下载 100GB 的网页，大约需要 10000 秒’
要是这样采集，十分钟之后就被封IP了。之前做爬虫都是采集一个页面休眠3-5秒，再采集下一个页面 1
2019-10-17不得了，我要写搜索引擎了！ 1
2019-08-02elasticsearch 1
2019-04-17爬虫按照广度优先的策略，不停地从队列中取出链接，然后“取“ -> “去“ 爬取对应的网页，解析出网页里包含的其他网页链接，再将解析出来的链接添加到队列中。
上面这段话里面有个词不是很通， 不知道后面还能修正么。作者回复: 编辑，麻烦修改下错别字，多谢。
1
2019-01-29问题1， 爬取网页时，如果采用深度优先算法，很有可能导致，栈溢出的现象把，所以一般不用深度优先算法 1
2019-01-29思考题1:深度优化借助栈这种数据结构，网页的深度是不可预测的，如果很深，栈大小会很大，内存可能会爆掉。 1
2019-01-28王老师，字典使用最长匹配？那例子中的”中国“”中国人“不就无法匹配到了吗作者回复: 在这个例子中是的。“中国人好样的”这个句子分词就可以匹配到“中国人”
1
2020-02-09整体系统介绍搜索引擎可以分为四个部分：搜集、分析、索引、查询。
* 搜集：就是利用爬虫爬取网页
* 分析：主要负责网页内容抽取、分词，构建临时索引，计算 PageRank 值这几部分工作
* 索引：主要负责通过分析阶段得到的临时索引，构建倒排索引
* 查询：主要负责响应用户的请求，根据倒排索引获取相关网页，计算网页排名，返回查询结果给用户
搜集
* 搜索引擎把整个互联网看作数据结构中的有向图，把每个页面看作一个顶点。如果某个页面中包含另外一个页面的链接，就在两个顶点之间连一条有向边。可以利用图的遍历搜索算法，来遍历整个互联网中的网页。
* 搜索引擎采用的是广度优先搜索策略。
* 权重比较高的链接，作为种子网页链接，放入到队列中
* 爬虫按照广度优先的策略，不停地从队列中取出链接，取爬取对应的网页，解析出网页里包含的其他网页链接，再将解析出来的链接添加到队列中。
1. 待爬取网页链接文件：links.bin
* 在爬取页面的过程中，爬虫会不停地解析页面链接，将其放到队列中
* 队列中的链接存储在磁盘中的文件（links.bin）。爬虫从 links.bin 文件中，取出链接去爬取对应的页面。等爬取到网页之后，将解析出来的链接，直接存储到 links.bin 文件中。
* 文件来存储支持断点续爬
2. 网页判重文件：bloom_filter.bin
* 使用布隆过滤器，可以快速且非常节省内存地实现网页的判重，避免重复爬取相同的网页
* 要定期地将布隆过滤器持久化存储到磁盘bloom_filter.bin 文件中，避免机器重启后，布隆过滤器被清空
* 当机器重启之后，重新读取磁盘中的 bloom_filter.bin 文件，将其恢复到内存中
3. 原始网页存储文件：doc_raw.bin
* 爬取到网页之后，需要将其存储下来，以备后面离线分析、索引之用
* 把多个网页存储在一个文件中，每个网页之间，通过一定的标识进行分隔，方便后续读取
* 每个文件的大小不能超过一定的值（比如 1GB），因为文件系统对文件的大小也有限制。
4. 网页链接及其编号的对应文件：doc_id.bin
* 网页编号是给每个网页分配一个唯一的 ID，方便后续对网页进行分析、索引
* 每爬取到一个网页之后，就从一个中心的计数器中拿一个号码，分配给这个网页
* 在存储网页的同时，将网页链接跟编号之间的对应关系，存储在一个 doc_id.bin 文件中
分析
分析阶段两个步骤（1）抽取网页文本信息，（2）分词并创建临时索引
1. 抽取网页文本信息
* 网页是半结构化数据，要从半结构化的网页中，抽取出搜索引擎关系的文本信息
这个抽取的过程分为两步
（1）去掉 JavaScript 代码、CSS 格式以及下拉框中的内容
* 利用 AC 自动机这种多模式串匹配算法将<style>, <script>, <option>标签包裹的字符删除
（2）去掉所有 HTML 标签，这过程跟第一步类似
2. 分词并创建临时索引
* 从网页中抽取出了文本信息，要对文本信息进行分词，并且创建临时索引
* 中文分词比较复杂太多了，可以基于字典和规则的分词方法
字典也叫词库，里面包含大量常用的词语。借助词库并采用最长匹配规则，来对文本进行分词。所谓最长匹配，也就是匹配尽可能长的词语。
* 具体到实现层面，将词库中的单词，构建成 Trie 树结构，然后拿网页文本在 Trie 树中匹配
* 网页的文本信息在分词完成后，得到一组单词列表。把单词与网页之间的对应关系，写入到一个临时索引文件中（tmp_Index.bin），这个临时索引文件用来构建倒排索引文件
*临时索引文件中存储的是单词编号，这样做是为了节省存储的空间。给单词编号的方式，跟给网页编号类似
*这个过程中使用散列表记录已经编过号的单词。对分词的先到散列表中查找，如果找到那就直接使用；如果没有找到，再去计数器中拿号码，并将这个新单词以及编号添加到散列表中
当所有的网页处理（分词及写入临时索引）完成之后，再将单词跟编号之间的对应关系写入到磁盘文件中，并命名为 term_id.bin
索引
索引阶段主要负责将分析阶段产生的临时索引，构建成倒排索引
倒排索引（ Inverted index）中记录了每个单词以及包含它的网页列表
那如何通过临时索引文件，构建出倒排索引文件？
考虑到临时索引文件很大，无法一次性加载到内存中，搜索引擎一般会选择使用多路归并排序的方法来实现
先对临时索引文件，按照单词编号的大小进行排序
因为临时索引很大，可以用归并排序的处理思想，将其分割成多个小文件，先对每个小文件独立排序，最后再合并在一起展开- 2020-01-17打卡