第 8 章：布尔代数和搜索引擎

搜索引擎：

• 自动下载尽可能多的网页——下载
• 建立快速有效的索引——索引
• 根据相关性对网页进行公平准确的排序——排序

1、布尔代数

2、索引

如何向你的奶奶解释搜索引擎？
每个网站就像图书馆里的一本书，我们不可能在图书馆书架上一本本地找，而是要通过搜索卡片找到它的位置，然后直接去书架上拿。

第 9 章：图轮和网络爬虫

如何自动下载互联网所有的网页呢？——图论中的遍历算法。

• 广度优先搜索
• 深度优先搜索
  面试：如何构建一个网络爬虫？
• 用 BFS 还是 DFS：“如何在有限的时间里最多地爬下最重要的网页”，显然 BFS 明显优于 DFS。调度系统，由它决定当一个网页下载完成后，接下来下载哪一个。
• 页面的分析和 URL 的提取
• 记录哪些网页已经下载过的小本本—— URL 表。

第 10 章 PageRank Google 的民主表决式网页排名技术

搜索结果的排名取决于两组信息：关于网页的质量信息，以及这个查询与每个网页的相关性信息。

PageRank

如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高，这就是 PageRank 的核心思想。考虑权重因此，即网页排名高的网站贡献的链接权重大。

image.png

先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。从理论上证明了不论初始值如何选取，这种算法都能保证网页排名的估计值收敛到排名的真实值，这种算法不需要任何人工干预。

第 11 章 如何确定网页和查询的相关性

对搜索相关性贡献最大是根据用户对常见搜索点击网页的结果得到的概率模型，除了用户的点击数据之外，归纳成下面四大类：

• 完备的索引
• 对网页质量的度量，如 PageRank
• 用户偏好
• 确定一个网页和某个查询相关性的方法
  如何度量网页和查询的相关性

搜索关键词权重的科学度量 TF-IDF

• 一个词预测主题的能力越强，权重越大，反之，权重越小。
• 停止词的权重为零。

第 12 章：有限状态机和动态规划——地图与本地搜索的核心技术

智能手机的定位和导航功能，其实只有三项关键技术：

• 利用卫星定位，这一点传统的导航仪都能做到
• 地址的识别
• 用户输入的起点和终点，在地图上规划最短路线或者最快路线

地址分析和有限状态机

有限状态机是一个特殊的有向图，它包括一些状态（节点）和连接这些状态的有向弧。

image.png
每一个有限状态机都有一个开始状态和一个终止状态，以及若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。
使用有限状态机识别地址，关键要解决两个问题：

• 通过一些有效地址建立状态机
• 给定一个有限状态机后，地址字串的匹配算法

2、全球导航和动态规划

第 18 章：谈谈搜索引擎反作弊问题和搜索结果的权威性问题

搜索引擎的反作弊

在通信中解决噪音干扰问题的基本思路有两条：

• 从信息源出发，加强通信（编码）自身的抗干扰能力
• 从传输来看，过滤掉噪音，还原信息。