Search Engines: Information Retrieval in Practice – 第3章

本章介绍了关于搜索原信息获取的问题,数据源除了Web、Feed之外,还有邮件、文档等各种可能的内网资源。

1、web的采集系统称为web crawler。两个最大的挑战:
(1)Web规模巨大,消耗巨大带宽、存储、CPU资源
(2) 不可控情况,很多网页会阻止你采集(加访问权限),有的Form表单无法采集,会产生数百万的组合结果(这种情况下,最好放弃form表单的采集)。

2、web上的每一个资源通过URL(Uniform resource locator)表示。分为scheme(如http)、hostname(如www.baidu.com)、resource(如/news)三部分。这个用过Python的urlparse的都应该很明白了。

3、Web Crawler的工作流程:
(1) DNS服务将hostname转化为服务器的IP地址
(2)client向服务器IP发送HTTP请求(GET)
(3)服务器server将数据返回给client
client也可以发起POST请求,用于表单模拟的情景。

4、web crawler的流程:
(1)下载页面
(2)页面下载完成后,解析其HTML,发现新页面(的url)

新的URL被加入到crawler的请求队列frontier中。这个队列可以是FIFO,更多的是优先级队列,重要的页面被移动到前面。

整个流程直到磁盘空间满或者所有有用的URL都被加入到队列中为止。

5、由于Web上页面数量巨大,且很多步骤都是I/O密集型任务。因此,一般同时使用上百个线程同时爬取网页。

6、但上百个并发连接同时爬取,有可能导致目标网站瘫痪,这是很不礼貌的行为。一个合理“礼貌”的策略是:
(1)在同一个时刻内,只能从一个web服务器(一个网站)上采集一个页面。
(2)一个页面采集完成后,需要间隔若干秒后,才能再开始采集下一个页面。

上述礼貌的策略实际上,将web网页按照domain分成若干个队列。即,每个domain一个队列,且每个队列有锁,一次只能处理队列首部的第一个url。

7、在上面的“礼貌策略”限制下,由于每个队列的并发只能是1,所以必须同时有很多队列,才能取得很好的效果。

8、除了礼貌外,还要遵守/robots.txt里面的限定,如果不让你爬就别怕。。虽然解析这个文件也麻烦的。。

9、新鲜度:web cralwer需要不断的爬取这个网页,以获取它的最近更新,保证页面是“新鲜的”。

10、HTTP协议提供了HEAD命令,可以仅获取头信息,其中包含Last-Modified,可以通过这个值判断一个页面是否被修改过。

11、对于页面更新的问题,web crawler需要决定“多久”去重复爬取一次。

一种定义“新鲜度”的方法为:已爬取网页中,最新的页面所占的比例。

另外一种定义,比较科学:使用age,页面未更新之前,age都为0。从更新页面后,age呈指数增加。具体公式见39页,这是一个泊松分布。

按照后面这种定义,有人做了较大规模的统计,在一周结束后,页面的E(age)=2.6天。

也就是说,在通用采集下,如果对所有页面采取平均的重采集时间,3-4天比较合适。

12、Focused Crawler/vertical search,又称为垂直搜索、主题搜索。即只爬取和所关心主题最密切相关的爬虫方法,在搜索引擎的早期(资源有限)用的比较多。

主题搜索的核心思想:一个主题网页的链出,一般也是同主题的。构造一个文本判断分类器。当seed页面(目标主题)下载完成后,用分类器决定是否为同一主题。
(1)如果是同一主题,将新页面所有链出URL加入 queue中
(2)不是同一主题,丢弃这个网页。

此外,锚文本、页面描述等信息也可以辅助文本分类器来综合判断。

13、Deep Web:网页中的信息孤岛,很难通过其他网页的链接找到这些Deep Web。 据估计,Deep Web的大小是已知Web大小的几百倍。
Deep Web主要有:
(1)私人站点,加访问控制了,不希望你爬到
(2)表单结果,因为很难正确填写,所以无法爬取
(3)Javascript、Flash脚本,需要模拟执行。

关于Deep Web的一个误区: 认为动态网页比静态网页难爬取。而实际上,很多动态网页(PHP等)生成和静态网页一样的HTML。相反,很多静态网页,大量使用了Javascript输出结果,让其内容很难被爬取到。

这就需要Web Crawler能够运行Javascript结果。这些技术都是可以实现的。

最难处理的应该是表单的情况。

14、Sitemaps,有时候,站长希望把自己的URL信息主动暴露给搜索引擎。Sitemaps就是这样一种方法,它包含了站点的URL链接、权重、更新频率(chengefreq)等信息。把sitemaps再加入到robots.txt中,可以更好的让搜索引擎发现URL。

15、分布式爬虫:理由很多
(1),Web太大,单机很难完全处理、存储、Domains队列也很难通过单机处理完成。
(2)把同一个site的网页分配到同一个机器上爬取。
(3)减少同一个机器上,必须记忆的队列大小
(4)爬虫需要消耗很多资源、CPU、带宽。分布式爬虫可以水平拓展,而无需垂直拓展(一直升级机器)

一般,分布式爬虫通过将URL Hash后,mod N,划分到N个机器上面。

16、 在桌面/局域网搜索中,文档主要来自本机、局域网和Email。

挑战:
(1)文档要求可以实时检索到,不能让用户反复手动去建定时的索引,而是来一个新文档就在内存中实时索引掉它。一般的文件系统,都提供Notifier,以事件监听模式通知app新文件的到来。
(2) 磁盘空间有限,索引要压缩再压缩。
(3)各种文件格式很多很复杂,一般都要支持上百种文档格式。
(4)数据是有隐私的,用户A不希望它的EMail被用户B搜索到。

17、不是所有Web资源都需要通过Web Crawler的采集,来发现新URL的。最典型的是Blog,在发布时会更新RSS。通过不断检查RSS的更新,来发现新的Post。一般是采用Pull的方式。

RSS的优势是,提供了结构化的数据结构表示,便于解析、分析每个数据域。并且提供了直接的URL汇编,不需要再去通过爬去的方式逐个获取URL。

18、文档格式很多:RTF、HTML、XML、WORD、ODF、PDF等。可以使用转换工具将他们转换成统一的中间格式,如XML或HTML。这样便于统一的建索引。不要转成Raw Text,这样会失去很多语义,比如粗体、标题等。

19、编码也是需要注意的问题,如UTF-8、GBK等。需要将他们转化为统一的格式。

20、文档的存储是必要的,一是为了建索引,二来后续处理时,做Snippet时也需要再次访问这个文档。

传统RDBMS是一个存储文档的很好的选择。支持网络接口,好用的SQL语句。但是它很难支撑海量数据存储,可拓展性等也有问题。

如果我们要设计一个新的系统需要支持以下特性:
(1)随机访问,因为检索回来的文档,本身就是很随机的。最简单的方法是Hash,定位后直接fseek到对应的offset,B-Tree也可以次优的完成这个功能。
(2)支持大文件和压缩,文件大小在X00MB左右比较适宜。此外,要支持压缩,对块压缩要比一个Doc一个Doc压缩效果好,但是不要把整个文件一起压缩!典型的算法如Deflate(gzip)、LZW。
(3)支持Update更新……

21、BigTable,Google的分布式存储系统,特点:
(1)将随机写转化为顺序写,
(2)将大表转化为tablets
(3)写入后就是不可变的了,所有更新单独放在内存中,定期Merge回去。
(4)以行为组织单位,无固定Schema。这样的话,同一个页面的各个属性都会放在同一行,方便处理。
(5)以牺牲关系数据库中丰富的特性为代价,换取高性能。

22、对网页的去重具有重要意义:在WWW上,约30%的网页都是重复的(含近似重复)。且去除这些无更多有用信息的页面,如spam和plagiarism(抄袭),能显著提升检索效果。

23、完全重复(Duplicate):直接copy;近似重复(Near-Duplicate):内容在一定程度上相似。

24、对于完全重复Duplicate,可采用Checksum:将文档切词,逐个累加或CRC(可识别乱换序)计算文章中的Checksums,相同的则为Duplicate。

25、对于部分重复Near-Duplicate,我们定义,假设文档的相似度达到阈值,如90%,则为Near-Duplicate。

26、Near-Duplicate的基本指纹算法:
(1)将文档分词,用n-grams处理词,构成词组,如2-gram的hello who are you为hello who, who are, are you。
(2)选取上述若干个n-grams表示这篇文档。
(3)对每篇文档,用选出的n-grams计算Hash值

本算法的关键在于(2)中如何选取合适的n-grams,随机并不会取得很好的效果。一种方法是0 mod p,即将所有hash值mod p为0的,选为代表n-grams。具体例子见书62页。

对于正规应用来说,n-grams的n选5-10,hash的长度为64bits。

尽管Cosine计算每两篇文档,所有词的相似度(类似于VSM模型)会很精确,但这种方法存在严重的性能问题。

27、Near-Duplicate的simhash算法:

这是2002几年新提出的算法,其构造一种特殊函数HashFunc,相似的文档在HashFunc后,值是相近似的。于是用两个hash values的不同bit位的数量,表示文档相似程度。
一个构造这种Hash函数的方法是:
(1)给每个词分配权重,如tf。
(2)给每个词计算Hash值,只要是b bit的、无重复就行,无其他要求。
(3)构造一个b-维度的向量V,对于每个维度(b个位之一),遍历所有的词,如果词在这个位上为1,就把这个词的权重加到向量的这个维度上,否则(0),把词的权重减掉到向量的这个维度上。
(4)完成上述向量V后,如果第i位>0,则标记最终b bits的Hash值Hash Final的这个位为1,否则为0。

至此,对于每个文档,生成上面这个Hash Final,都能保证是:相似文档获得相似的Hash值。在实际中,有人用384bits的上述fingerprinters,统计后发现,只要372bit相似,就可认为其Near-Duplicate。

28、Web检索中,我们一般只对正文区域感兴趣。而正文一般只占页面的20%左右。其余区域都被广告、Banner、图像、不相关的链接等占据。

而传统的检索模型中,基本是以词的出现来判断网页的相关性。此时,大量出现的非主题相关单词,会让检索效果大打折扣。

上述问题成为去噪Noise。去噪可分为主动和被动的。主动即自动化处理,被动就不用说了,根据content匹配正则,但是对Web来说太土了……

29、去噪算法1:根据观察结果,Content所在区域的HTML Tag含量最少。因此,提出了document slope curve,通过对accumulate tag的曲线的斜率变化,判断是否为Content区域。较为平缓的,判断为content区域。

这一看似不靠谱的算法,据说还不错。无论在性能还是效果方面。缺点是:无法对多Content的情况作出处理。

30、去噪算法2:分析Dom树的结构。遍历Dom树,过滤掉树上的噪音(如图像、脚本、无关联的链接)等,最后剩下的是Content区域。。。

31、去噪算法3:根据大量的机器学习,训练出一个分类器。用分类的方法辅助判断是否为Content区域。

Leave a Reply

Your email address will not be published.