论文部分内容阅读
摘要：如今Web上越来越多的信息可以通过查询接口获得，但为了获取某Hidden Web站点的页面，用户不得不键入一系列的关键词。由于没有直接指向Hidden Web页面的静态链接，当前大多搜索引擎不能发现和索引这些页面。然而，研究表明，由Hidden Web站点提供的高质量的信息对许多用户来说非常有价值。文章通过研究针对特定类型的表单，建立一个有效的Hidden Web爬虫，以便获取Hidden Web后台数据库信息。
关键词：Hidden Web；Hidden Web爬虫；静态链接；搜索引擎；采样策略
0 引言
网络上大部分内容是不能通过静态链接获取的，特别是大部分隐藏在搜索表单之后的页面只有通过用户键入一系列关键词才可以获得。这些页面被称为Hidden Web。由于当前的搜索引擎不能索引到或不能在它们的返回结果中显示这些页面，因此对用户来说这部分页面是隐藏的。Hidden Web最初由Dr．Jill Ellsworth于1994年提出，指那些由普通搜索引擎难以发现其信息内容的Web页面。2001年，Christ Sherman、GaryPrice对Hidden Web定义为：虽然通过互联网可以获取，但普通搜索引擎由于受技术限制而不能或不作索引的那些文本页、文件或其它通常是高质量、权威的信息。根据最近对HiddenWeb的调查文献得到了如下有意义的发现：
(1)Hidden Web大约有307,000个站点，450,000个后台数据库和1,258,000个查询接口。它仍在迅速增长，从2000年到2004年，它增长了3～7倍。
(2)Hidden Web内容分布于多种不同的主题领域，电子商务是主要的驱动力量，但非商业领域相对占更大比重。
(3)当今的爬虫并非完全爬行不到Hidden Web后台数据库内，一些主要的搜索引擎已经覆盖Hidden Web大约三分之一的内容。然而，在覆盖率上当前搜索引擎存在技术上的本质缺陷。
(4)Hidden Web中的后台数据库大多是结构化的，其中结构化的是非结构化的3．4倍之多。
(5)虽然一些Hidden Web目录服务已经开始索引Web数据库，但是它们的覆盖率比较小，仅为0．2％～15．6％。
(6)Web数据库往往位于站点浅层，多达94％的Web数据库可以在站点前3层发现。
可以看出Hidden Web中信息量要比Surface Web信息量多得多，同时由于Hidden Web页面信息是由后台数据库动态产生的，数据库大多是结构化的关系数据库，因此信息的质量比非结构化的页面要高。
本文以不含或含有少量的文本元素，其它类型元素都具有值的表单作为研究对象，提出了Hidden Web爬虫没设计的—种框架。
1 Hidden Web爬虫
为实现自动获取Hidden Web页面的任务，此爬虫必须能自动寻找表单，填写表单，然后获取和识别结果页面。HiddenWeb爬虫系统结构如图1所示。
图1 Hidden Web爬虫系统框架
1．1寻找Hidden Web入口页面
Web上存在多种多样的表单，同时表单上含有各种各样的元素，如单选按钮、下拉列表框、文本框等，有些还是用户自定义的，因此处理所有的表单是比较困难的。为此，需要先解析HTML页面，获取要研究的表单类型，同时从中抽取有用信息。本文要研究的是不含或含有少量的文本框元素，其它类型元素都具有默认值的表单。这很容易通过解析HTML表单来完成，如可以使用标记序列树或DOM(文档对象模型)来过滤出要研究的表单。
1．2自动提交表单
当搜索表单提供了每一表单元素所有可能的值时，直接的方法是对具有少量的文本框元素使用空串作为默认值，穷尽表单其他元素所有可能值的组合来填写表单，获取后台数据库全部的数据。此方法存在两个问题：①处理过程非常耗时；②在穷尽所有可能值组合之前，也许已经获取了所有或大部分的后台数据库数据，从而出现了重复提交；③多个字段组合可能存在语义上的冲突。Hidden Web爬虫设计的目标是使用最少的资源(如提交时间或次数等)获取特定Hidden Web站点内最大量的数据，然而不能保证对所有表单使用有限次的提交可以获取后台数据库的全部数据，因此有必要再次发送查询来确定是否已获取了全部数据。本文提出一种两阶段采样爬行策略以充分获取Hidden Web数据，它分为如下两个步骤：
(1)首先使用表单提供的默认值来提交；
(2)然后对表单元素值组合进行采样以确定默认值提交是否返回了后台数据库的所有数据，若返回了后台数据库所有或大部分数据则可以结束提交过程。否则，在爬虫所具有资源限制范围内穷尽所有可能值的组合。
1．2．1采样查询后台数据库
下面介绍采样阶段以确定默认值提交是否返回了后台数据库的全部数据。一种方法是从表单元素所有可能值的组合中随机采样来提交表单。然而随机采样提交不能覆盖表单元素每种取值，造成所有可能值的不均匀使用，如表1所示。这里形式化定义表单的第i个元素为因子Li。集合L1，L2，…，Ln是对应于表单上具有有限值的所有元素，| Li|表示第i个因子可能取值的个数，则表单元素所有可能值组合的个数为：
这里考虑了表单具有多个元素而势很小的情况。其中「log2N」的选择参见文献。
对表单元素所有可能值组合采样C次后若没有新的数据记录返回则表明已经获取了所有数据。举例来说，假设一个含有两个元素的表单，它们都具有有限的值域，每个元素可能取值个数为7和4，则上述N=28，C=6。
表1 随机采样
从表1中可以看到，对于元素A的可能值a6和a7，元素B的可能值b3在采样提交中一次都没有使用，同时元素B的可能值b1在6次采样提交中就使用了3次。这说明使用随机采样来提交表单可能造成表单元素某些值可能过分使用，而漏用其它一些值的情况。解决这个问题的一种方法是记录采样因子已经使用的值的次数，扩大采样值的范围，即“分层采样”的方法。使用此方法采样提交模式如表2所示。
表2 使用规则模式的“分层采样”
表2使用了一个规则的模式“分层采样”来覆盖每个因子的所有可能值。根据上述规则下次将使用(a7，b4)来填写表单元素。可以看到此方法覆盖了元素B的所有可能值，这种规则的模式必然会对某些元素有所偏重。为了覆盖所有元素的可能 值，表3使用了一个随机的“分层采样”方法。
对上述处理含有两个因子的表单的方法加以扩展，可用于含有两个以上元素的表单。
在C次采样提交的过程中，系统处理返回的页面来确定是否已返回了后台数据库的所有记录。若返回了所有记录则结束提交过程，否则进入穷尽阶段。用来确定一个查询提交是否返回了新的数据记录的方法很多。一种方法是使用Web信息抽取工具抽取返回页面中的记录，把记录存储到数据库中，然后通过数据库记录比较来确定是否有新的记录加入。这里使用改进后的复本检测系统来判断记录是否重复。它主要是计算每个候选记录的哈希值，视具有相同哈希值的为重复记录。
表3 使用随机模式的“分层采样”
1．2．2穷尽后台数据库信息
如果C次采样提交每次都产生了新的记录，则穷尽表单元素其它可能值组合来提交表单，直到满足特定的结束条件。然而在继续提交表单前，先要估计完成这样的操作所需的最大剩余时间和用于存储所有结果记录所需的最大空间。可以指定如下几个参数来完成此阶段的任务：最大查询提交次数、最大存储空间和最大剩余时间等。
可以通过叠加每次查询所返回的数据量来估计所需最大存储空间S。类似地可以估计最大剩余时间T。
在穷尽阶段，可以使用几个参数阀值来提前结束提交过程。包括：
(1)获取Web数据库数据的百分比：通过估计Web数据库百分比以确定获取了多少数据以后可以结束提交过程。
(2)查询提交次数：通过确定查询提交次数来减轻站点的负担。
(3)获取数据的数量：即获取了多少惟一性的Web数据库信息。
(4)提交时间：爬行某特定站点需要多长时间。
上述每一个阀值或其组合都可以在穷尽阶段提前结束爬虫爬行。
1．3识别和存取查询结果
对表单提交操作产生的响应主要有如下几种情况：响应页含有后台数据库部分或所有数据；响应页不仅包含有数据还包含链接；响应页含有数据和原始表单结构；响应页可能是另一张需要进一步填写的表单；错误页面通知；无记录通知或需要缺失字段。这一步主要是针对这些可能出现的情况进行处理。然后从含有丰富数据的页面中使用信息抽取工具抽取结构化的数据构建数据，以进一步提供信息检索服务。
2 结束语
本文提出一种针对特定类型表单获取Hidden Web页面的爬虫设计原型系统，它首先使用默认值来提交表单，以两阶段采样策略确定是否充分获取了后台数据库数据，然后从响应页中抽取出用户感兴趣的信息。此爬虫可以获取一部分Hidden Web页面，它弥补了当前爬虫只能索引静态页面的不足。下一步需要做的工作是，在真实Hidden Web站点进行大量实验及解决自动发现搜索接口等问题以完善此系统。毕竟存在很多需要填写文本元素的表单，这就需要扩展此系统使其能自动填写文本域元素。如使用HiWE系统中的属性标签值对表或使用领域本体知识库来自动学习填写表单以处理更多类型的表单，从而从Hidden Web中获取更多的用户感兴趣的高质量信息。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：Hidden Web；Hidden Web爬虫；静态链接；搜索引擎；采样策略
0 引言
网络上大部分内容是不能通过静态链接获取的，特别是大部分隐藏在搜索表单之后的页面只有通过用户键入一系列关键词才可以获得。这些页面被称为Hidden Web。由于当前的搜索引擎不能索引到或不能在它们的返回结果中显示这些页面，因此对用户来说这部分页面是隐藏的。Hidden Web最初由Dr．Jill Ellsworth于1994年提出，指那些由普通搜索引擎难以发现其信息内容的Web页面。2001年，Christ Sherman、GaryPrice对Hidden Web定义为：虽然通过互联网可以获取，但普通搜索引擎由于受技术限制而不能或不作索引的那些文本页、文件或其它通常是高质量、权威的信息。根据最近对HiddenWeb的调查文献得到了如下有意义的发现：
(1)Hidden Web大约有307,000个站点，450,000个后台数据库和1,258,000个查询接口。它仍在迅速增长，从2000年到2004年，它增长了3～7倍。
(2)Hidden Web内容分布于多种不同的主题领域，电子商务是主要的驱动力量，但非商业领域相对占更大比重。
(3)当今的爬虫并非完全爬行不到Hidden Web后台数据库内，一些主要的搜索引擎已经覆盖Hidden Web大约三分之一的内容。然而，在覆盖率上当前搜索引擎存在技术上的本质缺陷。
(4)Hidden Web中的后台数据库大多是结构化的，其中结构化的是非结构化的3．4倍之多。
(5)虽然一些Hidden Web目录服务已经开始索引Web数据库，但是它们的覆盖率比较小，仅为0．2％～15．6％。
(6)Web数据库往往位于站点浅层，多达94％的Web数据库可以在站点前3层发现。
可以看出Hidden Web中信息量要比Surface Web信息量多得多，同时由于Hidden Web页面信息是由后台数据库动态产生的，数据库大多是结构化的关系数据库，因此信息的质量比非结构化的页面要高。
本文以不含或含有少量的文本元素，其它类型元素都具有值的表单作为研究对象，提出了Hidden Web爬虫没设计的—种框架。
1 Hidden Web爬虫
为实现自动获取Hidden Web页面的任务，此爬虫必须能自动寻找表单，填写表单，然后获取和识别结果页面。HiddenWeb爬虫系统结构如图1所示。
图1 Hidden Web爬虫系统框架
1．1寻找Hidden Web入口页面
Web上存在多种多样的表单，同时表单上含有各种各样的元素，如单选按钮、下拉列表框、文本框等，有些还是用户自定义的，因此处理所有的表单是比较困难的。为此，需要先解析HTML页面，获取要研究的表单类型，同时从中抽取有用信息。本文要研究的是不含或含有少量的文本框元素，其它类型元素都具有默认值的表单。这很容易通过解析HTML表单来完成，如可以使用标记序列树或DOM(文档对象模型)来过滤出要研究的表单。
1．2自动提交表单
当搜索表单提供了每一表单元素所有可能的值时，直接的方法是对具有少量的文本框元素使用空串作为默认值，穷尽表单其他元素所有可能值的组合来填写表单，获取后台数据库全部的数据。此方法存在两个问题：①处理过程非常耗时；②在穷尽所有可能值组合之前，也许已经获取了所有或大部分的后台数据库数据，从而出现了重复提交；③多个字段组合可能存在语义上的冲突。Hidden Web爬虫设计的目标是使用最少的资源(如提交时间或次数等)获取特定Hidden Web站点内最大量的数据，然而不能保证对所有表单使用有限次的提交可以获取后台数据库的全部数据，因此有必要再次发送查询来确定是否已获取了全部数据。本文提出一种两阶段采样爬行策略以充分获取Hidden Web数据，它分为如下两个步骤：
(1)首先使用表单提供的默认值来提交；
(2)然后对表单元素值组合进行采样以确定默认值提交是否返回了后台数据库的所有数据，若返回了后台数据库所有或大部分数据则可以结束提交过程。否则，在爬虫所具有资源限制范围内穷尽所有可能值的组合。
1．2．1采样查询后台数据库
下面介绍采样阶段以确定默认值提交是否返回了后台数据库的全部数据。一种方法是从表单元素所有可能值的组合中随机采样来提交表单。然而随机采样提交不能覆盖表单元素每种取值，造成所有可能值的不均匀使用，如表1所示。这里形式化定义表单的第i个元素为因子Li。集合L1，L2，…，Ln是对应于表单上具有有限值的所有元素，| Li|表示第i个因子可能取值的个数，则表单元素所有可能值组合的个数为：
这里考虑了表单具有多个元素而势很小的情况。其中「log2N」的选择参见文献。
对表单元素所有可能值组合采样C次后若没有新的数据记录返回则表明已经获取了所有数据。举例来说，假设一个含有两个元素的表单，它们都具有有限的值域，每个元素可能取值个数为7和4，则上述N=28，C=6。
表1 随机采样
从表1中可以看到，对于元素A的可能值a6和a7，元素B的可能值b3在采样提交中一次都没有使用，同时元素B的可能值b1在6次采样提交中就使用了3次。这说明使用随机采样来提交表单可能造成表单元素某些值可能过分使用，而漏用其它一些值的情况。解决这个问题的一种方法是记录采样因子已经使用的值的次数，扩大采样值的范围，即“分层采样”的方法。使用此方法采样提交模式如表2所示。
表2 使用规则模式的“分层采样”
表2使用了一个规则的模式“分层采样”来覆盖每个因子的所有可能值。根据上述规则下次将使用(a7，b4)来填写表单元素。可以看到此方法覆盖了元素B的所有可能值，这种规则的模式必然会对某些元素有所偏重。为了覆盖所有元素的可能 值，表3使用了一个随机的“分层采样”方法。
对上述处理含有两个因子的表单的方法加以扩展，可用于含有两个以上元素的表单。
在C次采样提交的过程中，系统处理返回的页面来确定是否已返回了后台数据库的所有记录。若返回了所有记录则结束提交过程，否则进入穷尽阶段。用来确定一个查询提交是否返回了新的数据记录的方法很多。一种方法是使用Web信息抽取工具抽取返回页面中的记录，把记录存储到数据库中，然后通过数据库记录比较来确定是否有新的记录加入。这里使用改进后的复本检测系统来判断记录是否重复。它主要是计算每个候选记录的哈希值，视具有相同哈希值的为重复记录。
表3 使用随机模式的“分层采样”
1．2．2穷尽后台数据库信息
如果C次采样提交每次都产生了新的记录，则穷尽表单元素其它可能值组合来提交表单，直到满足特定的结束条件。然而在继续提交表单前，先要估计完成这样的操作所需的最大剩余时间和用于存储所有结果记录所需的最大空间。可以指定如下几个参数来完成此阶段的任务：最大查询提交次数、最大存储空间和最大剩余时间等。
可以通过叠加每次查询所返回的数据量来估计所需最大存储空间S。类似地可以估计最大剩余时间T。
在穷尽阶段，可以使用几个参数阀值来提前结束提交过程。包括：
(1)获取Web数据库数据的百分比：通过估计Web数据库百分比以确定获取了多少数据以后可以结束提交过程。
(2)查询提交次数：通过确定查询提交次数来减轻站点的负担。
(3)获取数据的数量：即获取了多少惟一性的Web数据库信息。
(4)提交时间：爬行某特定站点需要多长时间。
上述每一个阀值或其组合都可以在穷尽阶段提前结束爬虫爬行。
1．3识别和存取查询结果
对表单提交操作产生的响应主要有如下几种情况：响应页含有后台数据库部分或所有数据；响应页不仅包含有数据还包含链接；响应页含有数据和原始表单结构；响应页可能是另一张需要进一步填写的表单；错误页面通知；无记录通知或需要缺失字段。这一步主要是针对这些可能出现的情况进行处理。然后从含有丰富数据的页面中使用信息抽取工具抽取结构化的数据构建数据，以进一步提供信息检索服务。
2 结束语
本文提出一种针对特定类型表单获取Hidden Web页面的爬虫设计原型系统，它首先使用默认值来提交表单，以两阶段采样策略确定是否充分获取了后台数据库数据，然后从响应页中抽取出用户感兴趣的信息。此爬虫可以获取一部分Hidden Web页面，它弥补了当前爬虫只能索引静态页面的不足。下一步需要做的工作是，在真实Hidden Web站点进行大量实验及解决自动发现搜索接口等问题以完善此系统。毕竟存在很多需要填写文本元素的表单，这就需要扩展此系统使其能自动填写文本域元素。如使用HiWE系统中的属性标签值对表或使用领域本体知识库来自动学习填写表单以处理更多类型的表单，从而从Hidden Web中获取更多的用户感兴趣的高质量信息。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。