TAG:
|
搜索引擎组成： 蜘蛛若干
预处理机若干：
关键词提取
镜像网页或转载网页的消除
链接分析
网页重要程度的计算
查询服务器一台：
原始网页文档
URL和标题
编号
所含的重要关键词的集合（以及它们在文档中出现的位置信息）
其他一些指标（例如重要程度，分类代码等）
对服务子系统一个
查询方式
结果排序
文档摘要
上面就是一个搜索引擎的模型，从理论上讲，具备上述条件的实体和google没有什么本质上的区别。
为了更好的进行下一步的实验，我需要通过对于搜索引擎的学习，掌握一些制作spider的方法。
万维网以及网页分析
如果将万维网看做是一个有向的连通图，万维网的形状就像一个蝴蝶结。
蝴蝶结中部：彼此联通，任意去掉有限个网页不会影响连通度。从统计角度看采用正反向遍历可以遍历占全部网页的3/4。
蝴蝶结右部：被中心部分指向，是权威性网页。表示其认可度高。采用正向遍历的方法只能遍历有限的网页；采用反向遍历的方法可以遍历占全部网页3/4的网页。
蝴蝶结触须：从左部链出到到其他的网页，或者其他网页链入右部或从左部直接链入右部，以及少部分与中部、左部或右部都没有链接。无论采用什么办法，只能遍历到有限的网页。
万维网的直径大约17，及平均点击17次就可以从一个页面到达想到的任何一个页面。
这决定了采用宽度遍历的方法更加的合适。
网页抓取策略：
1. 宽度优先搜索
l 重要网页往往离种子距离近。
l 万维网的深度很浅，但是宽度却很大。
l 宽度优先策略有利于多个爬虫合作抓取。
2. 不抓取重复的网页
可以采用哈希序列处理方式。
3. 重要性网页优先策略
反向链接数、链接重要程度、平均连接深度
4. 网页重访策略
网页的更新过程近似符合柏松分布
网页更新的时间间隔符合指数分布
对于不同类型的网页采用不同的更新策略
5. Robots协议
Robots协议是需要遵守的礼貌性的协议。
根据网络的流量来制定爬去网页的速度。
网页库
网页的存储需要：
可伸缩性（将大规模网页平滑的分布在一组计算机硬盘中）
双访问性即随机访问模式和顺序访问模式
大规模的更新
网页的存储结构
日志结构
将磁盘看做是一个连续的存储介质。因为要支持索引，所以必须要支持B+-树结构。每次的存取操作需要进行两次读盘操作。这种结构不适于进行随机访问。
基于哈希的结构
通过建立哈希桶的集合实现，这样做利于随机查找，但是对于频繁更新的网页效率较低
哈希日志结构
就是将前两种结构融合在一起，通过哈希函数找到日志，再通过日志的B树对于结构进行查找。
网页重查机制
I-Match:两篇文档中特别高频和低频的词汇往往不能反映出这篇文档的质量。该算法将高频与低频的词汇去掉，然后得到一个频率的字符串，采用签名的方式之后，进行比较。
Shingle算法：计算字符串集合的相似性。
Pagerank
网页重要性的一种评价：
认可度越高的网页越重要，即反链接越多的网页越重要。
反向链接的源网页质量越高，被这些高质量网页的连接指向的网页越重要
链接数越少的网页越重要
对于下载的文档需要编号，编号需要满足下面的条件：
任何文档在其生命周期内仅有一个编号
任何两个不同的文档的编号不同
编号在计算中尽可能高效，并且为了便于存储，要越短越好
最为直接的方法就是通过URL的MD5签名进行编号，1个32位的整型就可以存储40亿量级的数。两个整型即可表达足够多的网页数量。8B*40亿*40亿=6×10^19B
这里介绍了一种将编码进行压缩的方式，对于大规模数据的处理将是这里的一个关键性问题。
倒排索引：
全文索引的检索是通过关键词来进行检索。按关键词创建的索引称为“倒排索引”，这里关键词被称为“索引词”，所以并不是所有的关键词都会创建索引。
命中（hit）表示索引词在文章中的位置和字体等信息。
正排索引（forward index）是创建倒排索引的基础，具有以下的字段。
Localld(Lid):表示一个文档的局部编号
Worded：表示文档分词后的编号，也称为“索引词编号”
NHits：表示某个索引词在文档中出现的次数
HitList：表示某个索引词在文档中出现的位置，即相对于正文的偏移量。
正排索引以文档编号为索引词，但是全文索引是通过关键词来进行索引的，所以正排索引不能满足需求。但这却能为倒排索引的建立提供方便条件，是不可缺少的一环。
倒排索引分为两个部分：
由不同的索引词组成的“字典”。其中保留了各种中文的词汇，以及这些词汇的一些统计信息，这些统计信息用于各种的排名算法。
由每个索引词出现过的文档集合，以及命中位置等信息构成。
倒排序文档如何存放：
分块按照pagerank降序，块内按照docId升序存放。
(jacky) |