搜索引擎的背后（粗糙入门）
搜索引擎架构
搜索引擎大概可分为4步：
- 搜集
- 预处理
- 索引
- 查询
搜集
利用爬虫搜集信息，初始可以从一些优质网页，然后通过广度优先遍历，不断提取出网页内容和其中的链接，并将链接加入到待爬取队列中，不断迭代爬取更多的网页；
问题一：这么多的网页，必然存在重复爬取的网页，如何避免重复爬取？
答：利用布隆过滤器。假如有10亿个url，每个URL平均长度为64字节，则10亿个至少需要
- 1 KB = 1024 字节（Byte），所以需要 1 * 10^9 * 64 / 2^30 = 60 G 内存，使用普通存储的话
而布隆过滤器利用 每 bit 上的数字是 0 还是 1，将每个URL通过哈希函数 映射到 每 bit 上，如果该 bit
上数字为 1 ，则表明已访问过，0 表示未访问过。但也肯定会存在误判，可以通过适当调节哈希函数来减少误判。最终只需要 1.2 G的空间。
预处理
- 比如 去掉爬到的网页中的无用字符
可以使用 BF、KMP等字符串匹配算法，但这些算法属于单模式串匹配，对于单个字符串效果很好，但如果要一次性查询多个字符串，效率不如 AC自动机多模式串匹配算法，时间复杂度接近O（N）；
分词创建索引
对网页中内容进行分词，也就是把文本切分成一个个词，英文分词可以直接按照空格隔开，但中文就不行，不同的分词模式可能会产生不同的结果。
分词 一般是根据现有的词库进行匹配，当然在匹配之前需要清除一些无意义的，比如：的、得。分词后，就得到了每个分词与其文本的关系。因此在搜索的时候，输入某个词语，就可以直接得到对应一些网页的唯一ID，但这些网页的展示先后顺序，就涉及到另一个重要的算法：PageRank；
PageRank：也叫佩奇排名，是Google的拉里·佩奇和谢尔盖·布林提出的链接分析算法，是Google用来衡量一个网站重要性的标准，级别从0到10，越高代表网页越受欢迎，重要性越高。
PageRank的计算主要依靠两个假设：
- 数量假设：如果一个页面接收到的来自其他页面的指向越多，就是有越多的页面都指向它，说明它的重要性越高；
- 质量假设：越是质量高的页面指向的页面，那么被指向的页面也就越重要。
也就是说，一个页面A的重要性，不仅看有多少页面指向了A，还要看这些指向A的页面本身的重要性如何，两者结合才能得出A的重要性程度。
基本计算：
- 如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)。
其中PR（T）为T的PageRank值，L(T)为T的出链数 则A的PageRank值为一系列类似于T的页面重要性得分值的累加。
当然，PageRank的计算远不止这么简单，详细可见https://blog.csdn.net/hguisu/article/details/7996185
查询
用户输入关键词后，首先肯定需要经过分词器的处理，然后查找索引，得到网页ID，再去提取网页的链接的内容，并按照权重大小排序。这里的权重不仅与PageRank 算法有关，还涉及到另一个TF-IDF 算法。
而在搜索的时候，搜索框输入几个字符后，下面就会出现一列相关的搜索提示词，
要实现这个，就要提到另一种树形结构：Trie树，也叫字典树、前缀树（prefix Tree）、单词查找树，是一种多叉树，它具有以下性质：
- 根节点不包含字符，除根节点外的每一个子节点都包含一个字符
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符互不相同
此外，前缀树还可以用来寻找热门搜索字符串，在结构中，可以在每个节点处添加一个标志，用来记录有多少个字符串到达过此处，即它被搜索过多少次。然后维护一个固定大小的小顶堆，将每个节点的字符串和搜索次数传到小跟堆中，不断更新维护，就得到了最热门的若干搜索字符串。
参考文献：