织梦CMS - 轻松建站从此开始!

罗索实验室

当前位置: 主页 > 行业动态 > 『互联网』 >

搜索引擎原理读书笔记

jackyhwei 发布于 2010-03-01 17:16 点击:次 
一个搜索引擎的模型,从理论上讲,具备上述条件的实体和google没有什么本质上的区别。为了更好的进行下一步的实验,我需要通过对于搜索引擎的学习,掌握一些制作spider的方法。
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
网页重要性的一种评价:
认可度越高的网页越重要,即反链接越多的网页越重要。
反向链接的源网页质量越高,被这些高质量网页的连接指向的网页越重要
链接数越少的网页越重要
 
对于下载的文档需要编号,编号需要满足下面的条件:
任何文档在其生命周期内仅有一个编号
任何两个不同的文档的编号不同
编号在计算中尽可能高效,并且为了便于存储,要越短越好
最为直接的方法就是通过URLMD5签名进行编号,132位的整型就可以存储40亿量级的数。两个整型即可表达足够多的网页数量。8B*40亿*40亿=6×10^19B
 
这里介绍了一种将编码进行压缩的方式,对于大规模数据的处理将是这里的一个关键性问题。
 
倒排索引:
全文索引的检索是通过关键词来进行检索。按关键词创建的索引称为“倒排索引”,这里关键词被称为“索引词”,所以并不是所有的关键词都会创建索引。
 
命中(hit)表示索引词在文章中的位置和字体等信息。
正排索引(forward index)是创建倒排索引的基础,具有以下的字段。
Localld(Lid):表示一个文档的局部编号
Worded:表示文档分词后的编号,也称为“索引词编号”
NHits:表示某个索引词在文档中出现的次数
HitList:表示某个索引词在文档中出现的位置,即相对于正文的偏移量。
正排索引以文档编号为索引词,但是全文索引是通过关键词来进行索引的,所以正排索引不能满足需求。但这却能为倒排索引的建立提供方便条件,是不可缺少的一环。
 
倒排索引分为两个部分:
由不同的索引词组成的“字典”。其中保留了各种中文的词汇,以及这些词汇的一些统计信息,这些统计信息用于各种的排名算法。
由每个索引词出现过的文档集合,以及命中位置等信息构成。
倒排序文档如何存放:
分块按照pagerank降序,块内按照docId升序存放。
(jacky)
本站文章除注明转载外,均为本站原创或编译欢迎任何形式的转载,但请务必注明出处,尊重他人劳动,同学习共成长。转载请注明:文章转载自:罗索实验室 [http://www1.rosoo.net/a/201003/8624.html]
本文出处:网络博客 作者:jacky
顶一下
(2)
100%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
栏目列表
将本文分享到微信
织梦二维码生成器
推荐内容