基于深网络的垂直搜索引擎蜘蛛的基本解决方案

http://hi.baidu.com/anspider/blog/item/0718fa0004330605728da522.html

               最初接触搜索引擎是2年前，一位北京的朋友（对我帮助很大）让我帮他设计了一只抓网页的蜘蛛。当时我头一次听说蜘蛛，半天没有回过神来，心想：蜘蛛？莫非是蜘蛛机器人？后来我还知道，蜘蛛也被人称为爬虫，正规的名称叫Spider。
               第一次写蜘蛛的程序时，阅读了很多规范，同时找到了几个c#代码的（c#是朋友要求的语言）免费的Html解析的库（我记得有一个是解析SGML规范的）。可惜的是，国内的页面都是乱七八糟的，这2个库根本就是无能为力，连163的首页都无法正确解析。于是，我只好自己写了，代码不是很长（三五千行），构建dom树。（后来我把这个程序的结果发给百度，想找份工作，结果未见回音）当时遇到的主要问题有三：1）dom树的解析和容错；2）多线程下载和Url过滤；3）页面编码的分析。
当我离开学校，进入现在的公司的时候，是1年前的事情。进入的时候，我就想做点事情：构建一个垂直搜索引擎的完整解决方案。我没有想到这个事情是无法完成的，所以到目前为止，我也只是完成了一个十分局限的解决方案。
               最初的3个月，我疯狂的寻找我梦想中的终极解决方案。为了达到这个目标，我从各种数据库上（实在不好意思，因为穷的原因，所有的文章都是通过非正常渠道获得的，在此感谢帮我从ACM/IEEE等数据库上面下载文章的小鸡MM 和表弟）下载了500++篇文章（全部外文），还买了好几本中文英文的算法书（比如，支持向量机、HNC层次模型等），一个劲地看，管它是否能看明白。然后，我就开始设计了第一个智能分析页面的蜘蛛（使用HtmlParser作为dom树的解析），当然了，为了使用上我学习到的各种技术，我是把机器学习算法/自然语言理解/文法生成等等各种东西拼命的融合在一起，想构建出一个无敌算法来。可惜，一个月之后，这个思路走进了死胡同。机器学习算法？几乎无法用在页面信息抽取上；自然语言理解？没有一个有效易用的先例。文法生成？难而且不知道用在哪里。虽然问题很多，最后还是勉强的从一些论文里面借来了某些思路，构建成了一个智能页面分析的蜘蛛。
               接下来的3个月，我不断的为这个智能蜘蛛烦恼，因为它的精度太低了。为了提高它的精确度，我不断的修改算法，不断地给他打补丁，直到面目全非。当时，页面匹配是我遇到的最大的问题。
               进入2007年后，我不断的问自己，是不是我走错方向了？是不是我的完美理想无法实现？再一次，我仔细的翻阅了最新的一些论文，终于才明白了仅凭我现在的能力无法做到比它们更好，所以，我难以达到理想的目标了。基于这点考虑，我开始分解问题，把问题分解为3步：
               1）人工参与页面信息提取；
               2）半自动页面信息提取；
               3）全自动页面信息提取。
               其实，我之前一直做的是全自动页面信息提取，可以说已经做了一部分的第3步的工作了。而第二步的工作其实是半人工半全自动的形式。
               而本文主要阐述如何解决第一部分问题。

1、垂直搜索引擎的定义

国人对垂直搜索引擎的研究已经很久了，记得能够从cnki上面看到的中文文献中，最早出现垂直搜索引擎这几个字是在1996年（记忆中的）。当时，对它的定义是：行业搜索引擎。即把搜索的信息局限在某个行业里面的普通搜索引擎。今天垂直搜索引擎的定义还是一样的，唯一不同的是，随着时代的发展，垂直搜索引擎面临了2个新的问题：1）信息抽取；2）深网络挖掘。除此以外，人们对垂直搜索引擎的刷新速度也提出了比普通搜索引擎更高的要求。搜索引擎一般可以划分为蜘蛛和搜索系统2部分，前者负责获取数据，后者负责数据检索。本文主要谈论基于深网络的蜘蛛的设计和构建，而检索系统将在以后撰文说明。

2、蜘蛛的主要任务

蜘蛛的目的就是抓取页面，并从页面中提取出有用信息。所以，蜘蛛是分为网页抓取和页面信息抽取2部分的。前者主要关注如何正确的得到想要的页面，如何正确的得到页面的可视信息；后者主要关注如何分类页面，如何获取页面的关键信息。

2.1 检索器

检索器的概念出现在深网络相关技术文章里面，所谓的检索器其实就是如同于我们在百度上看到的那个输入框和搜索按钮一样，它决定了搜索结果页面的url地址。这个地址其实是一个入口地址。它是所有接下来的任务的方向标。

点击“百度一下”，看到的url即是检索器需要构建出来的地址。
从直观上面看，检索器一般在Form标签里面，有几个输入数据的文本框，加上一个提交的按钮。像百度这样形式的检索器，很容易自动识别出来。这样或许你会认为检索器很容易自动构造，其实不然。现在的网页越来越美观，很少有页面还是使用那种原始的检索样式，不信你看：

这个检索器几乎是无法自动识别的。至少我暂时没有看到或者想到办法自动识别。虽然有的检索器无法自动识别，但检索器肯定都是可以人工识别的。所以，一定可以设置一个可以配置的检索器。这就是我们蜘蛛设计的第一步：检索器的配置。
检索器对于外界来说，就是一个不断产生连接请求地址的机器，直到没有可以产生的为止。它产生的地址可以认为由4部分组成：1）请求的url地址；2）请求的方法；3）请求的参数；4）发送请求的编码。这几部分对于研究过的人来说，应该很容易理解。本处不作过多说明。

2.2 页面获取

我们首先用检索器得到一个请求的地址，接着就是发送这个请求地址，得到对应的页面信息。为了得到页面信息，我们需要一个强壮的http文件（页面）下载器。为什么这么说呢？第一，很多网站都是需要登陆才能够访问到机密信息 的，故你的下载器必须支持cookie；第二，网页编码识别是一个难题，下载器需要认真的处理这个方面的问题；第三，http的其它各种标准也需要支持，比如，页面跳转的支持；第四，其他特别的需求，比如，对于下载数据格式的限定（如只下载文本文件）。基于这4个方面和其他某些方面的考虑，我们建立了蜘蛛的第一个项目：HttpDownloader。
HttpDownloader 项目介绍：
这个项目重点解决了网页编码的识别问题（这个问题是没有完美解决方案的，我们只能够从Unicode标准中定义的utf标准的说明里面找到一些额外的办法。当然了，刚好有些开源的代码能够支持直接分析二进制数据对应的文本属于哪国文字，这个也是一个不错的补充。）其它问题大部分都是靠开源库搞定，少部分自己写代码搞定，都没有什么得意的地方值得谈论。另外，在进行大量测试之后，发现实际情况中有各种各样的问题，比如，请求url编码就是其中的一个问题。默认情况下，url编码应该使用utf-8，可是，国内的网站很多都是要求gb2312编码的，或者说utf-16编码。如果贸然认为都是utf-8的话，就会遇到连baidu的页面都无法正确获得的问题。这个只是冰山一角，还有好几个这类型的问题，都是和中国国情不兼容。顺便说一句，这个项目主要以HttpClient 作为底层。

2.3 页面解析

虽然我个人曾经用C#写过html代码dom树解析的程序，但我们还是使用了开源的东西来做页面解析。HtmlParser和NekoHtml显然是做页面解析的2个最有名最好的开源库。不过，它们都有不少的缺点（不兼容），当你遇到后，你需要修改它们的代码，让他们能够正确的运作。这里举个例子说明一下：

基本的HtmlParser（最新版本的，2006年9月）无法解析下面的代码：
“<strong>very!</strong>”
因为它居然没有识别strong标签！

如果比较一下NekoHtml，你或许会感觉到NekoHtml才像专业人士写的代码，而HtmlParser有点业余。其实呢？？。。。
NekoHtml并不是很好很好。我们知道Balance是NekoHtml最得意的地方，因为其他的解析都是扩展的别人的代码。但是，作者身处在一个有序的环境之中，并不需要考虑过多的容错性问题，这直接导致了Balance做的很一般（对于中国国情来说）。举个简单例子：

<table>
test
</table>
IE和FF会解释为：test<table></table>，而NekoHtml则解释为<table>test</table>

               虽然我自己也感觉HtmlParser过于业余，但是，它做的是一个比较有扩展性的框架，这点比NekoHtml强。另外，它对加密Script也进行了相关处理。
               综合起来看，如果你只是需要进行html解析，你就该使用HtmlParser；如果你需要对js进行处理，你就需要使用NekoHtml，不然，你会遇到很多没有html也没有body标签的网页。
               为了解决NekoHtml和HtmlParser的一些问题和提高容错度，我们建立了2个新的项目：NekoHtml2007 和HtmlParser2007 ，它们专门用来解决这2个开源项目的Bug（虽然我很希望那些库的作者能够出来解决这些Bug）。

2.4 页面JS解析

               至于为什么要处理js，你可以简单的访问 http://image.baidu.com/i?ct=201326592&cl=2&lm=-1&tn=baiduimage&pv=&word=mm&z=0 ，然后看看源文件。明白了吧？现在很多网站的页面都是使用js构建出来的，更不用说那些使用web2.0(AJAX)技术的网站了。一个强壮的有竞争力的商业垂直搜索引擎，不支持这种东西是不行的。最基本的支持JS的方法是使用IE或者FF（FireFox）使用的借口，调用它们解析页面，不过，这种方法的浏览速度超慢，不可能成为一个搜索引擎的选择。所以，必须自己想办法做一个支持的库出来（忽略图像渲染部分，能够加快构建速度和处理时间）。
               说支持JS容易，可是，到底该怎么支持呢？好在我多年前关注js的时候，已经关注过一个叫SpiderMonkey的东西了。它的Java版本叫 Rhino。现在Rhino已经整合到JDK1.6里面了，所以，各位不用再去下载它了。Rhino它是一个js脚本的解释运行库。但它并不支持dom树（因为js实际上和html已经没有任何关系了，js更多的时候用在脚本处理里面，这点和VBScript有点像）。为了让它支持dom树，需要我们自己进行扩展。研究一番Rhino，再研究一番其他使用了Rhino的开源项目（特别推荐你看看HtmlUnit 项目的源代码，最新的htmlunit1.13已经可以比较好的支持js的解析了，如果你只是做点基本的小应用，可以用它来做js方面的问题），你就应该能够找到思路了。剩下的就是艰苦的编程了，很无趣的工作，因为你需要满足IE的规范，也要满足FF（dom1-dom3）的规范。
               做好js的解析之后，你还可以考虑css的解析，css的解析目前没有发现特别好的开源工具。一切完备之后，就是把它们组合起来，构建一个模拟IE和FF 的浏览器了（没有图形界面，所以，速度飞快）。浏览器支持的额外功能可能要根据自己的需要来定了。

为了解决js的问题，我们建立了一个Browser 的项目。Browser项目模拟了IE的工作方式，主要是2个方面的处理：1）Cookie的处理；2）js的处理。cookie的处理大部分由底层处理， js的处理包含了js的解析、js的运行、dom初始事件的处理等。Browser除了js的基本支持以外，它显然最需要支持的是url地址。我们知道，很多网页的超链接都使用：javascript:...的形式，这个地址是搜索引擎需要的。所以，Browser必须支持运行js脚本，并且返回一个链接地址回来。

完美的Browser实现十分复杂，我们只能够部分的支持js，无法完全的做到IE那样（还差很远很远，但比最新的htmlunit(2007-8-7版本)要强很多）。下面的图示部分的说明了这点：

然后是IE的实际效果：

3 信息抽取

信息抽取属于哪个部分，一直都没有一个明确的说法，反正现在我们是把它划分在蜘蛛里面。因为它的重要性和难度于基本的蜘蛛功能差别比较大，所以，我单独的列为一节来详细描述。垂直搜索引擎一般面对的并不是基本的网页数据，而是深网络数据。深网络数据的主要特点是它无法通过基本的爬行技术获得信息。对深网络的数据的处理一般包含了3部分：1）检索器的构建；2）列表页面的分析；3）详细页面的分析。第一部分的处理我在前面已经说过了，这里不再涉及。下面分别说明另外2部分的处理过程。

3.1 列表页面的处理

页面净化算法多如牛毛，什么基于视觉啊、什么基于边界线规则啊、什么基于行切分啊，太多太多了。这里我不想评价哪个算法更好，反正我个人喜欢简洁明快的思路，所以，根据深网络数据的特点，我选择了基于页面聚类的页面净化算法。这个算法就是根据多个相似的页面，根据节点的信息增益寻找那些垃圾信息所在的地方。因为页面十分相似的缘故，这类根据多个页面进行处理的算法具有很好的效果。注：有兄弟问为什么不在这里把算法描述的明白一点？我回答：页面净化算法本身的东西太多，如果真要我说清楚，我恐怕十万字都无法把所有的算法详细描述一遍。不过，可以说明的是，我们的算法的基础思想来自于： Discovering Informative Content Blocks from Web Documents。

如果你没有这个闲心去研究各种复杂的页面净化算法，至少你可以使用如下的最简单的页面净化算法：

1）找2个相似页面；

2）得到页面的文本列表；

3）前后文本一样的地方认为是垃圾信息；

4）按照这个思路同样处理链接。

经过页面净化之后的列表页面，可能如下图所示：

基于深网络的垂直搜索引擎蜘蛛的基本解决方案

从图中我们看到，列表信息占据比较大的地方，十分显眼。列表页面信息提取是hidden(deep) web crawling研究的内容。可以称为Data Record Alignment、Record-Boundary Discovery等。其主要目的是从一个原始页面中提取出一条一条的信息。原始的列表必须包含一个多条信息列表。

如果仅仅只考虑文本信息的话，那么，记录列表定位是一个明显的聚类问题。不过，聚类在一起的文本必须是连续的（先序访问DOM树，得到的文本列表）。作为一个参考，有人提出相邻2个文本之间的距离应该用它们之间的路径差异来决定（比如，路径不同之处包含的节点个数）。聚类技术同样可以用在页面分块上面，因为直观上面看，页面上的分块之间具有一定的聚类关系。

考虑到一般的记录都有超链接的关系，我们甚至可以仅仅考虑页面中的超链接。那么，聚类也只是考虑超链接的聚类。只考虑超链接的聚类具有十分不错的效果。基本的KKM都能得到很好的结果。作为聚类的一种替代策略，可以仅仅考虑相邻的2个节点之间路径的差异，设置一个最大门限，小于门限的认为是一个类别。
如果你在记录提取方面是一个初学者，那么，我推荐你先看看：STAVIES: a system for information extraction from unknown Web data sources through automatic Web。同样的道理，这里涉及到的算法太多，请根据你自己的实际应用选择一个好的算法。

出现在列表页面上面的另外一个重要的信息就是下一页的信息。下一页描述了下一个列表页面的地址。它决定了能否遍历所有的结果。提取下一页的算法很多，最简单的一种办法就是穷尽所有“下一页”的文本，然后满页面寻找这类文本，如果文本表示的是超链接的话，这个链接就是下一页的地址了。最复杂的办法是寻找页面里面连接的特点（上图中的1、[2]、[3]...等也构成了一个列表），利用文法推断的算法来自动生成下一页的地址，这种算法的好处是可以并行的访问列表页面，坏处是优秀的文法推断算法十分晦涩。

上面的列表页面只是一个十分简单的例子，一个一般的列表页面具有如下的特点：

1）多列表；

2）多形式的记录；

3）列表里面包含了多种形式的记录；

4）一种形式的记录可以被多个列表包含；

5）列表的个数可变；

6）列表包含的记录数可变；

7）除了列表以外，还包含有用信息。

如果你想对这类列表页面有一个感性的认识，可以看看文章：Fully Automatic Wrapper Generation For Search Engines。

为了解决列表的问题（包括将要说到的详细页面的问题），我们构建了3个项目：Algorithm、VerticalSearch、WalkingSpider 。这3个项目分别介绍如下：

Algorithm ：算法库。构建算法库的主要目的其实是为了把各种自创的或者改进的算法总结在一起，以提供高效的底层支持。现在算法库包含了联合数组的排序算法、联合数组的 k排序算法、各种压缩算法（算术、Huffman、BinaryCode等）、可变数组的快速实现、字符串和树相关的各种算法。这些算法的唯一特点就是几乎没有可用的免费库。

VerticalSearch ：垂直搜索引擎库。这个库是一个行业无关的库，所以，它是完全通过结构来进行处理的。它包含了html页面解析、dom树结构的各种算法、基于结构的模板处理（配置、解析、匹配）等。它设计了通用的页面模板形式，这个模板结构可以匹配一般的列表页面（即涵盖了上面提出的7点特点）。因为它是行业无关，也就是和文字无关，所以，这一层的所有模板都是已经构建好的（可以手工在这里构建，也可以上层自动构建）。我之前说的Baidu的图片url地址提取其实就是直接使用了手工构建的模板（所谓的手工是有程序支持的，如下图）。

需要提醒大家的是，基于结构的页面信息提取其实是一个中间过程。其完整的过程是：1）根据结构和文本获得结构模板；2）根据模板匹配页面，获得信息。上图展示的是一个手工构建模板的程序。它替代了自动模板构建的过程。这样做的原因是很明显的：部分页面很难自动生成模板或者说自动生成的模板精确度不高。基于结构的页面信息提取的主要算法就是页面的Dom树匹配。树匹配算法研究很多，大家可以自己去找资料。唯一的是，这类算法一般都会遇到各种实现的问题，正好是检测算法水平的时候，赫赫。

WalkingSpider： 不用我告诉大家，大家就应该知道猜测到它应该是比上面的基于结构的信息抽取更加高层的东西。它就是专门针对某个行业的自动模板构建程序。它大量的运用了页面短语文本和超链接文本的特性，使用一些简单的文本分析技巧。因为信息抽取的文章太多了，各种办法都有。考虑到行业的特点，这里只是使用了简单的基于正则表达式和命题学习算法来分析文本（短语），这类算法一大把，随便找篇论文都能看到。当然了，为了更好的判断短语的含义，这里也使用了一些语义网络（和本体论）的知识。具体的步骤就不说了，因为那会泄露行业的信息。

3.2 详细页面的处理

其实之前的列表页面的处理就说了一部分详细页面的处理了。大家看到的页面的处理（VerticalSearch项目），其实就包含了详细页面的处理。因为那个项目是通用页面处理程序，对列表和详细页面都是适合的。我不想再重复一遍处理方式，只把一个详细页面的例子贴上来，让大家对所谓的详细页面有个理解：

上面的这个图片是一张新闻页面的详细页面。

详细页面的信息抽取其实包含了2部分的处理：1）基于页面的信息抽取；2）基于无格式化文本的信息抽取。第一部分的信息抽取就是我们前面讲过的，它一般只能够处理到短语（文本）级别。比如，它知道某句话“一九九八年2月”是表示的出生时间。第二部分的信息抽取是把第一次信息抽取得到的文本信息进行进一步的处理，这部分就是基本的无格式化文本信息抽取的问题。

目前，对于无格式化文本信息抽取的解决方案主要有2个：1）基于机器学习的算法；2）基于自然语言理解的方法。基于机器学习的算法的分类方法很凌乱，目前研究比较火爆的是基于关系学习的无监督学习算法。基于自然语言理解的方法目前因为难度太大，还没有在实践中有什么应用，但是，它们已经被用到了文本政治倾向的判断等问题上面。传统上（2000年前）的基于机器学习的文本信息抽取算法一般都是使用命题学习或者一阶谓词，现在常用的本体论的标准也是使用了一阶谓词作为其推导的基础。为了得到这些推导标准，人们使用最大熵，HMM等通用算法来分析样本。有关信息抽取方面的说明，请大家看2006年的 Survey。晕死，突然发现电脑里面的大量文章不知去向。呜呜呜......

我们的项目现在只能够处理到第一部分的信息抽取，同时，在第二部分的信息抽取中，只是简单的使用了命题学习的算法。不过，我们正在考虑如何把本体论的思想用到信息抽取中，最顶级的目标是做到自然语言理解下的信息抽取。

备注：如果有哪位兄弟对中文自然语言理解很有见解的（特别是HNC），请您留点建议，谢谢。

因为我这里差东西，导致程序无法运行，明日到公司后，补上今天想加的各种图片（7-19）。未完，待续。

抱歉的很，这几天因为繁忙了一点，居然忘记了这篇文章还没有写完，今日继续更新（7-24）。

昨天因为看GPL魔兽比赛的半决赛（Sky vs Th000），故没有更新，今日是决赛，所以，估计还是不会更新的。明天再更新。7-26

Sky 3:1 战胜老对手Moon，最后一局的比赛相当精彩，Moon的熊猫到了6级，2次分身，可惜第二次让Sky建好了4个塔，然后熊猫把Sky的大法师和娜迦都杀死了，Sky钱多，直接把大法师买出来，然后引诱熊猫，用娜迦的减速把熊猫围起来，杀死了。以后，Moon的完全没有金钱了，只好把生命之树爬到一个分矿那里，想弄点钱，可怜的是，当它走过去的时候，发现那里已经有Sky的箭塔在等着了。Moon无奈gg了。

仍然是图片没有，等待明天加上去。。。。7.26。今日Sky获胜，所以更新的多一点。哈哈。

似乎是写完了，可是，感觉好像什么都没有说。郁闷，不知道说什么好。思考几天再说。欢迎读者提点意见。（2007-7-30）
今日再次修改。（2007-8-24）

基于深网络的垂直搜索引擎蜘蛛的基本解决方案

相关推荐