建立搜索引擎的步骤
建立一个搜索引擎需要通过三步：
- 下载：自动下载尽可能多的网页
- 索引：建立快速有效的索引
- 排序：根据相关性对网页进行公平准确的排序
爬虫
-
什么是爬虫
可以从任何一个网页出发，用图的遍历算法，自动访问到每一个网页并把它们存起来，这就是爬虫（其中，使用
哈希表来记录网页是否下载过） -
构建爬虫的工程要点
1／用BFS还是DFS
-
“如何在有限时间里最多的爬下最重要的网页”，首页通常是最重要的，所以BFS优于DFS
-
实际上，在搜索引擎的爬虫里，不是简单的BFS，但是先爬哪个网页，后爬哪个网页的调度程序，原理基本上是BFS
-
爬虫下载网页的次序，由一个相对复杂的下载优先级排序的算法来决定，管理这个优先级排序的子系统称为调度系统（在调度系统中，需要存储那些已经发现但尚未下载的网页的URL，它们存在一个
优先级队列里）
2／页面的分析和URL的提取
-
当一个网页下载完，需从这个网页提取其中的URL，把它们加入到下载队列中
-
现在，很多URL的提取并不那么直接，因为很多网页如今是用一些脚本语言生成的，打开网页源代码，URL并不是直接可见的文本，而是运行一段脚本后才能得到
3／记录哪些网页已经下载过－－URL表
-
采用
哈希表来记录哪些网页已经下载过。哈希表的优势是，判断一个网页的URL是否在表中，平均只需一次查找 -
在一台服务器上维护一张哈希表并不困难，但如果同时有上千台服务器一起下载网页，维护一张统一的哈希表就不容易了
- 首先，这张哈希表会大到一台服务器存不下
- 其次，由于每台服务器在开始下载前和完成下载后都需要访问这张表，以免不同服务器做重复的工作，这个存储哈希表的服务器的通信就成了整个爬虫系统的瓶颈
- 最后，如何解决这个瓶颈？
- 首先，明确每台服务器的分工，即在调度时一看到某个URl就知道要交给哪台服务器去下载，以避免很多服务器对同一个URL做出是否需要下载的判断
- 然后，在明确分工的基础上，判断URL是否下载就可以批处理了，比如，每次向哈希表（一组独立的服务器）发送一大批询问，或者每次更新一大批哈希表的内容
-
索引
-
搜索引擎会自动把用户的查询语句转换成布尔运算的算式，如”原子能 AND 应用 AND (NOT原子弹)”
-
最简单的索引的结构是用一个很长的二进制数表示一个关键字是否出现在每个网页中
有多少个网页，就有多少个位数，每一位对应一个网页（1表示相应文献有这个关键字，0表示没有）
于是，搜索引擎的索引就是一张大表，表的每一行对应一个关键字，每个关键字后跟着一组数字
假设互联网上有100亿个有意义的网页，词汇表大小是30万，则索引大小至少是100亿X30万＝3000万亿
-
为了网页排名方便，索引中还需要存有大量附加信息，如每个词出现的位置 次数等，索引非常大，并非一台机器的内存能存下，因此，索引需要通过分布式的方式存到不同的服务器上
普通做法是，根据网页的序号将索引分成很多份，分别存储在不同的服务器中
每当接受一个查询，这个查询就被分到许多服务器中，这些服务器同时并行处理用户请求，并把结果送到主服务器进行合并
PageRank
-
对于一个特定查询，搜索结果的排名取决于
- 关于网页的质量信息（Quality）
- 这个查询与每个网页的相关信息(Relevance)
-
PageRank算法原理
PageRank核心思想是民主表决：在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍认可，那么它的排名就高
网页排名高的网站贡献的链接权重大
-
例如
一个网页Y的排名应该来自于所有指向这个网页的其它网页X1,X2,X3…Xn的权重之和
假设X1,X2,X3,X4都指向Y，且X1,X2,X3,X4的权重分别是0.001,0.01,0.02,0.05
则Y的网页排名pagerank = 0.001 + 0.01 + 0.02 + 0.05 = 0.081
而最开始如何确定网页的排名？－－先假定所有网页的排名是相同的，并根据这个初始值，算出各个网页的第一次迭代排名，再根据第一次迭代排名算第二次的排名，以此类推，直到某两次迭代之间的差异非常小，停止迭代运算
-
确定网页和查询的相关性
-
关键词频率／单文本词频 (TF) ＝ 关键词出现的次数／网页的总字数 -
应对汉语中的每个词都赋予一个权重，这个权重须满足以下2个条件：
-
一个词预测主题的能力越强，权重越大
假定一个关键词w在Dw个网页中出现过，那么Dw越大，w的权重就越小
逆文本频率指数 (IDF) = log(D/Dw) -
停止词（如：“的”“是”“和”“中”等几十个）的权重为0
-
-
关键词与网页的相关性度量
TF-IDF = TF1*IDF1 + TF2*IDF2 + ... + TFn*IDFn
-
