本章介绍了关于搜索原信息获取的问题，数据源除了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区域。