乐趣区

读书笔记这就是搜索引擎

作者:LogM

本文原载于 https://segmentfault.com/u/logm/articles,不允许转载~

本文是《这就是搜索引擎》的读书笔记

1. 概述

1.2 搜索引擎技术发展史

  • 第一代:文本检索。关键词与网页内容的相关程度。
  • 第二代:链接分析。PageRank。
  • 第三代:用户中心。理解用户需求。

2. 爬虫

2.1 通用爬虫框架

2.3 爬虫质量的评价标准

  • 抓取网页覆盖率、抓取网页时新性、抓取网页重要性
  • 为了同时满足上述 3 个标准,google 用了多套不同的爬虫,一些关注时新性,一些关注覆盖率。

2.4 抓取策略

  • 宽度优先遍历:暴力但有效
  • 非完全 PageRank:因为 PageRank 需要拿到所有的页面计算才是准确的,爬虫抓取的时候没有看到所有页面,所以叫 ” 非完全 ”
  • OPIC:改进 PageRank,实时计算
  • 大站优先

2.5 更新策略

  • 历史参考策略:历史上变动比较快的,抓取频繁一点,一般用泊松过程建模
  • 用户体验策略:保存网页的多个历史版本,查看不同历史版本对用户点击的影响。所以用户点击不到的页面,即使更新快,也不用抓取。
  • 聚类抽样策略:更新快的页面有一些类似的特征

2.6 暗网抓取

  • 抓取常规网页链接不到的信息

2.7 分布式爬虫

  • 一致性哈希确定每个爬虫负责哪些 url 的抓取

3. 索引

3.1 倒排索引的结构

  • 单词字典 + 倒排列表

3.4 建立索引

  • 两遍文档遍历法:完全在内存中构建
  • 排序法:内存满时,对中间文件排序后存到磁盘,最后再合并所有的中间文件。整个过程,整个字典都在内存里,字典有可能过大。
  • 归并法:每个中间文件都是一套倒排索引(含各自的字典),最后再把所有的倒排索引合并。

3.6 动态索引与索引更新

  • 完全重建策略:临时索引与老索引的文档全部取出重新建索引,重建的代价高,但主流搜索引擎都采用该方式
  • 再合并策略:临时索引与老索引进行索引合并(不是文档取出重新建索引,而是合并)
  • 原地更新策略:再合并策略的升级,临时索引追加到老索引

3.7 查询

  • 一次一文档:每个文档对 query 中所有词计算相似度
  • 一次一单词:对 query 中每个词计算文档相似度,每个文档累加每个 query 词的相似度
  • 跳跃指针:因为倒排索引一般是压缩保存的,跳跃指针帮助快速定位需要的文档

3.8 多字段索引

有时候需要区分不同的字段来索引,比如 ” 标题 ”、” 正文 ”、” 摘要 ” 等字段。

  • 多索引方式:为每个字段都建立一份倒排索引
  • 倒排列表方式:在每个倒排列表的后面追加一个字段,表示该关键词是在哪个字段出现
  • 扩展列表方式:用扩展列表标明每个字段的开始和结尾位置,结合倒排列表中关键词的位置,可以知道关键词在哪个字段。实际使用常用这个方法

3.9 短语查询

  • 位置信息索引:利用倒排列表中关键词的位置信息判断是否组成短语
  • 双词索引:” 首词 ” 的倒排索引中有指向 ” 下词 ” 的指针,” 下词 ” 又有指针指向倒排列表
  • 短语索引:会导致字典急剧膨胀,一般只用于热门短语

3.10 分布式索引

索引体积大,一台服务器存不下

  • 按文档划分:按文档对索引文件进行切分。扩展性、容错性、对查询方式的支持都较好
  • 按单词划分:按单词字典对索引文件进行切分

4. 索引压缩


5. 检索与排序

把与用户搜索词最相关的结果排在前面

  • 布尔模型
  • 向量空间模型:TF-IDF + cosine 距离
  • 概率检索模型:BM25
  • 语言模型:从文档生成用户搜索的概率多大
  • 机器学习排序
  • 评价标准:准召、P@10、MAP

6. 链接分析

6.2 重要的概念模型

  • 随机游走模型:模拟用户的浏览行为,PageRank
  • 子集传播模型:从一个特殊子集出发,将权重传递到其他网页,HINTS

7. 云计算与云存储


8. 网页反作弊

8.1 内容作弊

  • 关键词堆砌、热门关键词、标题作弊、meta 信息作弊……
  • 内容农场:雇人写垃圾文章,比机器作弊更难被判定

8.2 链接作弊

  • 链接农场、购买链接、购买域名……

8.3 页面隐藏作弊

  • IP Cloaking、User Agent Cloacking、页面重定向、页面隐藏……

8.4 web2.0 作弊

  • 博客作弊、点评作弊、Tag 作弊、个人 Profile 作弊……

8.5 反作弊的通用思路

  • 子集传播模型:信任传播模型(如 TrustRank)、不信任传播模型(如 BadRank)
  • 异常发现模型(如 SpamRank)

9. 查询意图分析


10. 网页去重


11. 搜索引擎的发展趋势


退出移动版