搜索引擎要处理的问题就是,在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表,这个列表包括三部分:标题,URL,描述或摘要。
现代的大规模搜索引擎一般采用三段式的工作流程,即:网页搜集、预处理、查询服务。
现在我对这三点简单的阐述下:
一、网页搜集
搜索引擎是通过爬虫去搜集互联网中的网页,放入数据库,但是这不可能是用户提交查询的时候才去抓取,而是预先就搜集好一批网页,可以把WEB上的网页集合看成是一个有向图,搜集过程从给定起始URL集合S开始,沿着这些网页中的链接,按照先深或先宽某种策略遍历,不停的从S中移除URL,下载相应的网页,解析出网页中的超链接URL,看是否已经访问过,或者有未访问过的那些URL加入集合S。我们这里可以是定期搜集,增量搜集,或者是用户自主提交的方式进行爬取。并且对这批网页进行维护。这种维护,是为了能及时发现网页的新特征,搜集新的网页,改变过的网页,或者已经不存在的网页。
二、预处理
预处理主要包括四个方面:关键词的提取、镜像网页或转载网页的消除、链接分析和网页重要程度的计算
1.关键词的提取
作为预处理阶段的一个基本任务,就是要提取出网页源文件的内容部分包括的关键词。对于中文来说,就是根据一个词典,用一个所谓的“切词软件”,从网页文字中切除词典所包含的词语来,在那之后,一篇网页主要是由一组词来代表,p={a,b,c,……d}.一般来讲,我们会得到很多词,同一个词可能在一篇网页中出现多次。然后我们要去掉”停用词“,例如”的,在,是”这一类的词语。再加以对这些词的词频(TF)和文档频率(DF)之类的计算统计,从而指示出词语在一篇文档中的相对重要性和某种内容的相关性。
2.镜像或者转载网页的消除
在WEB上,存在着大量的重复信息,这种信息对于搜索引擎来说可能是负面的,因为需要消耗机器时间和带宽资源,并且无意义的消耗了计算机显示屏资源,也可以带来用户的抱怨,这么多重复,给我一个就够了。所以搜索引擎对于消除这些重复信息也是预处理中一个很重要的任务。
3.链接分析
搜索引擎除了对内容进行分析外,并且最重要的还需要对链接进行分析,链接信息不仅给出了网页之间的关系,而且还对判断网页的内容起到很重要的作用。网页中的内部链接和外部链接对网站的排序起到了很大的影响。
4.网页重要程度的计算
搜索引擎返回给用户是一个和查询相关的结果列表,列表中的条目顺序是很重要的问题。因此搜索引擎必须提供一种统计意义上的排序结果给用户,但并不能给所有用户都能提供满意的结果。如何对网页权重进行评估,是搜索引擎最需要解决的问题,例如GOOGLE的pr算法,其中思路就是认为“被引用越多的就是重要的”,和HITS算法等等。这些算法,有些在预处理阶段计算,有些则在查询服务阶段进行计算,从而最终形成最优的排序结果。
三、查询服务
当从一个S集合开始,通过预处理后得到的就是S的一个子集元素的某种内部显示,至少包含几个方面:原始网页文档,URL和标题,编号,所含重要关键词的集合(包括出现位置)等其他的一些指标。而系统关键词的总体集合和编号一起构成了一个倒排文件结构,使得一旦得到一个关键词输入,就立刻能给出相文档编号的集合输出。这里主要有三方面的:查询方式和匹配,结果排序,文档摘要。
1.查询方式和匹配
用户一般查询都是“要什么就输入什么”,这对于搜索引擎来说,是一种模糊的说法,它可能不知道你真正想要的是什么,所以就是希望网页中包含有该词或者短语中的词,也就对用户查询的词语或短语进行分词,形成一个q,他的每一个元素都对应倒排文件中的一个倒排表,即文档编号的集合。从而实现了查询和文档的匹配。
2.结果排序
要想给用户提供最高质量的网页信息,必须对结果进行排序,例如GOOGLE的PageRank算法,Kleinberg的HITS算法等,是目前搜索引擎给出查询结果排序的主要方法。
3.文档摘要
搜索引擎给出的结果是一个有序的条目列表,每一个条目都包含标题,URL,摘要,其中的摘要需要从网页正文中生成,这里可以归纳为两种方法,一种是静态方式,从正文中提取中一些文字,如正文开头的512个字节,或者每段第一句拼凑起来等,但这种有个弊端是可能与查询的词语无关。所以第二种方式就是动态摘要,根据查询的词在文档中的位置,提取出周围的文字来,显示时将查询词标亮。这种方式是目前大多数搜索引擎采用的方式,为了保证查询效率,需要在预处理分词阶段记住每个关键词在文档中出现的位置。
本文来自www.hbdsz.com供稿,转载请注明出处!