技术专题

se的秘密(二)分析系统

2008年5月4日 阅读(144)

前面的一篇已经将网页的获取这一步完成了,下面要进行的一步便是对这些网页的分析以完成索引建立。当然,有的书里把分析这一步与索引结合到一块,也是有道理的,因为分析只是一个预处理的过程,其目的便是为后面的索引服务。不过呢,我还是把它单独列出来吧,毕竟后面的索引是最为复杂的一个,估计要花很多的文字去介绍,为减少复杂度,还是首先把分析这一步介绍完毕。

在这之前,还是先提供一点数字,以便对爬虫的工作效率有个大体的认识。以开源的Larbin为例,单个爬虫每小时大概可以抓取20万个网页,这样每天大概可以抓取500万,而互联网上的网页大概是以10亿为数量级的。这样1000个爬虫大概可以每天抓取50亿网页,当然实际随着爬虫数目的增加,会花费大量的通信开销,另外网页的更新是不受控的。所以以上数据只能做个定性的估计。

ok,开始进入分析系统的世界吧。。。

正如我们所知道的,爬虫抓取的网页是html文件,里面还有大量的冗余信息,我们所用浏览器看到的网页是经过解析之后的,选择浏览器工具栏:查看->页面源代码,你会发现html源文件,内部包含很多无用的语法关键字。另外网页中也会包含大量的广告等垃圾信息,而这些对于se来说是完全无用的,所以对网页进行分析,提取有用信息是必要的。

分析系统主要完成如下认为:网页信息提取,网页去重,分词以及pagerank计算。

网页信息提取,主要是根据html语言将网页进行结构化分析,即提取出网页的标题,正文。观察html的语法,可以发现它具有树形结构比如如下的语句:
<html>
    <title>
   </title>
    <td>
   </td>
</html>
实际上html标签组成树根,而td,title则同为它的孩子。
另外<td></td>这种成对组合的方式,决定了可以使用栈进行方便的分析。
这样使用栈,建立起html的语法树结构,就可以将其各部分文字提取出来。
但是这时还需要一种方法,来区别广告和真正的正文,采用投票算法,基本思想是:建立几个指标,比如文字个数,位置。根据这些指标给每个部分的文字打分,当分数太少时我们就把文字当作无用信息舍弃。

网页去重,爬虫收集来的网页,由于其数量巨大,重复不可避免,因此必须去除重复的网页。当然这不同于前面的url去重,考虑这样的情况,比如:转载。在这时,对于不同的url是完全可以具有内容相同的信息的。而网页去重的目的就在于处理这种情况。

其实,这种去重的技术早就存在了,考虑去重的目的,你是否联想到现实中那件事跟去重在做同样的事情呢?
对了,其实它源于作弊检测,比如考虑老师是如何判断两张试卷是互相抄袭的呢?于是自然而然的转化为一个文章相似性判断的问题。

很多著名的算法的思想总是如此简单,一目了然,因为它们源自生活。

两个简单的判断相似性的算法:
I-match:去掉两个网页中的高频词和低频词汇,然后计算它们的签名(比如计算它们的md5 hash值,或者对它们进行排序),如果签名相同则认定相似。

shingle算法:以定长抽取网页中的子串组成字符串集合,通过判断两个网页形成的字符串集合的相似性来确定是否相似。

比如: 设定长为3,下面两句话会形成如下字符串集合: “小小的月亮弯弯的船”和 “弯弯的月亮小小的船”形成字符串集合为{小小的,小的月,的月亮,月亮弯,弯弯的,弯的船}和{弯弯的,弯的月,的月亮,月亮小,亮小小,小小的,小的船}

分词:
其实这个很复杂,而且由于中文存在很复杂的语境和歧义,很难做到准确。举个简单的例子:日本在东方,可能具有以下分词方式:日本/在/东方 日/本在/东方
但是简单的分词过程比较容易理解,让计算机去做分词,相当于一个会查字典的人,但是他不认识字,给他一篇文章,让他把里面的词语找出来,他应该怎么做呢。
比如给他如下文字:%$&*#@%$
他会这样做,首先查%,观察这个字的组成的词,如果%$刚好是字典中写的组词,则开始查&,看它的组词方式,是否有以&*...开头的,计算机的分词就是这样的。

复杂的原因是%$,$&可能都是词,但是到底哪个理解才是正确的呢?这让计算机能够结合语境判断,就不是那么容易了。

现在主流的分词方法,都是基于字典的(使用前缀树或者后缀树构造),也有一些基于统计分析的,当然现实中总会有不断的词语诞生,这就是语言的演进吧,所以一个好的字典必须能够支持和及时添加新的词汇,比如现在的"计算机,电灯,博客",我想在1000年的中国是还未出现的吧...

pagerank计算:

这是google著名的排名算法,baidu采用竞价排名的方法,即排名跟付费挂钩,你多给点钱它就把你的网站在搜索结果中排的靠前。很明显搜索引擎对于用户查询的结果的排序是完全可以控制的,只是竞价排名可能会对结果的相关性和准确性造成一定的损害,当然这也是商业目的造成的。

其基本思想也是很生活,举个现实中的名人例子,名人是些什么样的人呢?他们一般具有如下特点,有很多人知道他们,就是有很多fans,但是他们却不认识这些人,名人一般经常被名人提到,而且跟名人认识的人一般也是名人。

pagerank就是这样的,他们这样评价一个网页的重要性:
如果有很多链接指向这个网页,则说明这个网页很重要。
如果这个网页很少链接,说明这个网页很重要。
那些很重要的网页指向的网页,通常也是很重要的。

计算公式如下:
rank(T(n)) = 1-d + d*(sum(Ci(n-1)/M))
有两部分组成,第一部分是假设所有网页都被访问的几率相同,第二部分则来源于那些指向该网页的网页的pagerank值。T(n):网页T在第n次跌代的pagerank值。 Ci(n-1)表示指向网页T的网页在n-1次跌代的pagerank值,M表示指向T的网页总数。

pagerank的值是收敛的,即随着跌代的进行,网页pagerank值趋于稳定。具体的分析和计算需要参考更深入的理论。

pagerank算法目前已公布,当然搜索引擎的排名算法一旦公布,必然会迎来巨大的压力,很多网站为了提高排名,会根据算法原理进行作弊,比如增加大量的垃圾页面全部链向自己的网站,以提高pagerank的值。而现在的SEO行业也是针对此进行了,其目标均是尽量提高网页被搜索引擎索引的重要性,当然这个行业加上了合法化的光环。

分析系统就是完成以上的工作,其中对单个网页完成信息提取,去重和分词后的结果将立即送到索引系统进行索引的建立,这个过程是在内存中进行的。

而最为费时的pagerank计算,必须等待网页规模达到一定程度后才能进行计算,然后每隔一段时间进行一次计算。而panerank的计算结果将作为网页重要性的一个依据在以后查询结果的排序时进行筛选或者参与最终的排序。

ok,当网页的分析完成之后,下面应该进入最为重要,也是搜索引擎之所以可以如此快速的在数十亿网页快速查询的关键原因。其中将涉及到索引,倒排索引,大数据量排序,数据压缩等方面的内容,也是搜索引擎实现中最关键最有特色的部分:索引部分。

。。。

You Might Also Like