搜索引擎的工作原理
Introduction
搜索引擎大致分为4个基础部分：
- 蜘蛛爬虫系统
- 数据分析系统
- 索引系统
- 查询系统
蜘蛛爬虫系统
发现一个连接 $\rightarrow$下载该网页$\rightarrow$加入临时库$\rightarrow$提取网页中连接$\rightarrow$再下载网页$\rightarrow$循环
蜘蛛爬虫抓取网页策略1：深度优先
蜘蛛到达一个页面后，发现一个锚文本链接，就是爬进去另个一页面，然后又在另一个页面发现另一个锚文本链接，接着往里面爬，直到最后爬完这个网站。
蜘蛛爬虫抓取网页策略2：广度优先
蜘蛛到达一个页面后，发现锚文本不是直接进去，而是把整个页面所有都爬行完毕，再一起进入所有锚文本的另一个页面，直到整个网站爬行完毕。
蜘蛛爬虫抓取网页策略3：权重优先
结合深度优先与广度优先，参照链接的权重，如果这条权重较高，采用深度优先，如果权重较低，采用广度优先。
权重判别方式
- 层次的多与少
- 该链接的外链多少与质量
蜘蛛爬虫抓取网页策略4：重访抓取
用于网页更新后重新抓取，分为两种
- 全部重复：指定间隔时间，全部重新访问抓取一次
- 单个重复：对于更新频率较快的网页，指定较短间隔时间重新访问抓取
数据分析系统
对爬虫抓取的网页进行分析，分为：
- 页面结构化：删除HTML代码，提取内容
- 消噪：保留网页主题内容，删除无用内容如版权
- 查重：
- 分词：将内容分为N个词语，排列，存入索引库
- 链接分析：查询内链、外链、权重
索引系统
索引系统中的索引包含3个概念：命中（Hit）、正排索引（Forward Index）和倒排索引（Inverted Index）。
命中
名字表示索引词在文章中的位置（position）和字体等信息。
正排索引
是创建倒排索引的基础,包括4个字段： LocalID(Lid), WordID, NHits, HitList. 存放方式如下图所示，其中null结束符。
##倒排索引
按关键词创建的索引称为”倒排索引”。这里关键词成为“索引词”。并不是所有关键词会创建索引。分为两部分
- 词典(lexicon),由不同索引词(index term)组成的索引表。如下图左所示
- 记录列表(posting list),又每个索引词出现过的文档集合和命中位置等信息组成，如下图右所示。
正排表与倒排表合并
查询系统
查询词：用户提交给查询系统的关键词
检索词：查询词分词后，提交给检索代理
检索模型
- 布尔模型
- 向量空间模型
主要用到的算法为：余弦相似度(Cosine similarity)和 TF-IDF (term frequency–inverse document frequency)
检索过程如下：
其中求交过程可用最佳归并树算法或其他归并算法
堆排序采用HEAPSORT算法
总结
未涉及自动摘要，生成搜索结果页，根据搜索日志推测用户意图。
一些附加功能
- 推测用户查询意图，包括查询纠错、查询推荐及相关搜索。
- 某领域内细分，垂直搜索及分类搜索
- 查询结果优化，相似结果聚类、垃圾网页及病毒网页甄别
- 个性化服务，保存用户的个性化信息并给出可指定的服务，列如可定制搜索服务
Reference
潘雪峰. 走进搜索引擎[M]. 电子工业出版社, 2011.