关于搜索引擎：搜集、分析、索引、查询。

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

要点

搜索引擎大致可以分为四个部分：搜集、分析、索引、查询。
搜集，就是我们常说的利用爬虫爬取网页。
分析，主要负责网页内容抽取、分词，构建临时索引，计算 PageRank 值这几部分工作。
索引，主要负责通过分析阶段得到的临时索引，构建倒排索引。
查询，主要负责响应用户的请求，根据倒排索引获取相关网页，计算网页排名，返回查询结果给用户。

搜集：将广度优先搜索的优先队列存储在磁盘文件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中找到网页链接按序输出显示给用户。

• doc_id.bin：记录网页链接和编号之间的对应关系。

• term_id.bin：记录单词和编号之间的对应关系。

• index.bin：倒排索引文件，记录每个单词编号以及对应包含它的网页编号列表。

• term_offsert.bin：记录每个单词编号在倒排索引文件中的偏移位置。