搜索的难题之Invisible Web/Deep Web

转贴来 自：http://www.thinktag.cn/

Deep Web (invisible Web) 中文可以翻译成深层网页或暗网。迈克尔.伯格曼将当今互联网上的搜索服务比喻为像在地球的海洋表面的拉起一个大网的搜索，巨量的表面信息固然可以通过这种 方式被查找得到，可是还有相当大量的信息由于隐藏在深处而被搜索引擎所错失掉。

数据来源：“Accessing the Deep Web”, Communications of the ACM, May 2007

Deep Web所涉及到的数量级要比我们想想的要大。实际上可以由搜索引擎的蜘蛛抓取的部分只是这巨大冰山浮出水面的很小的一部分。根据上图的一组数据所示，实际 我们目前主流的搜索引擎只覆盖到了其中的37%这样的数量级。所以如何获取更深层网页是各家搜索引擎所面临的挑战和机遇。

通常Deep Web由以下几个原因产生：

Dynamic content ，由程序动态生成的内容。特别是像很多大型企业或者学术机构的数据库，其中存放 着大量有价值的信息，但是获取他们都需要通过用户进行特定的Query查询才会返回结果。这样交互获取内容的方式使得依靠通过链接获取内容的搜索蜘蛛失 效。

Unlinked content ，没有链接的内容，或者说是很少有链接的内容。例如，当你的网站刚建立的时 候，它对于搜索引擎来说就是数据一个信息的孤岛。

Private Web ，这部分内容涉及到访问授权。通常为人为限制，例如需要用户输入用户名和密码才能访问。

Contextual Web ，上下文关联内容。这部分内容我觉得也可以归纳到第一部分Dynamic content中。因为它的产生通常都根据实际的情况动态的产生。例如某些推荐引擎生成的结果会根据用户不同的行为，时间，地点产生不同的结果。

Limited access content ，这部分我认为也可以算是因为人为限制访问产生的内容。

Scripted content ，这部分主要只通过Javascript的方式产生的内容，例如通过Ajax 这样的方式交互产生。

Non-HTML/text content ，这部分主要涉及非文本的信息，例如DOC、PDF、SWF等多种 格式。可喜的是目前搜索引擎已经部分解决了这个问题。对于PDF、DOC这类的格式有一定的支持。

对于处理的Deep Web问题的难点和处理优先级来说解决Dynamic content的问题是当前各家搜索引擎的重中之重。在这个问题的解决上各家有个家的方法。正面进攻和迂回策略两种渠道兼并。

正面进攻从原理上来说可能我们遇到这样的Dynamic content之后先要识别它的类型和交互方式 ，如果 是数据库类的可能需要先用少量的刺探性质的Query来尝试分辨它的类型和规模，确定后然后再用一组 特点的Query去抓取内容分析页面结构。当然这个从理论到实践的过程必定非常的复杂。

至于迂回的策略我认为雅虎目前鼓吹的BOSS和Search Monkey 就可以算是这类的方式，类似百度的开放平台，Google Base。它通过开发的API允许用户主动的将结构化 的数据提交上来 。站点在一方面获取到在雅虎结果页更丰富的结构化展现和搜索技术外，雅虎也在这个过程中获取到了自己所需要的数据。当然 这也仅是理论的方式，能收集到多少有效的数据还需要静观其效。

这条路上不乏一些先行者，例如犹他大学的DeepPeep.org 就 是其中之一。国内的百度也推出了自己的阿拉丁计划，其目的也是为了解决这个问题。同样这个问题的探究对于我们ASC来说也具有非常重要的意义。可以想象， 一旦通过技术的方式打通了各个数据库之间信息的隔阂，那么这些结构化的数据将帮助我们加速在语义网(Semantic web)上的进程。技术的创新很有可能会再次重写互联网的格局。

业界相关的研究：

Yahoo Search Monkey 系统设计图

系统结构示意

 

Google VLDB大会上关于Deep Web的演讲   Paper: Google’s Deep Web Crawl

From ： Google 工 程师 Jayant Madhavan 在 2008 年 VLDB 大 会上的发言。

Deep Web 指的是隐藏在 HTML 表 单之后的信息内容，举例来说，对于一个网上卖书的网页来说，用户必须反复的尝试不同的值去提交表单，网站返回给用户的是一个列表展示的各种书的页面，这些 内容其实都是属于 Deep Web 的内容。

 

Deep Web 产生的原因是这种通过表单提交的方式已经超过了搜索引擎的范围：

1、 很少有其他网页的超文本链接指向的网页表单提交；

2、 当前的网页抓取程序是没有能力自动提交表单的。

因为这些网页未进入搜索引擎的索引，不能把它们展示给给搜索引擎用户，所以我们把这部 分隐藏的信息叫做 Deep Web 。

为什么要在 VLDB （ Very Large Data Base ）上做这个报告呢？

我们认为在 Deep Web 的 背后有一个非常大的结构化的数据源，没一个表单之后都是由背后的数据库做支撑的。而事实上，在早期的一些文档中，我们可以知道 www 存 在超过 1000 万不重复的表单，很显然，这样会带来更多的数据。我们所 面临的挑战就是如何把这些隐藏在表单之后的网页尽可能方便的展示给用户。

Deep Web 会处理很多的 表单，包括位置信息，二手车，专利，食谱等，但是不会包括登陆表单，或者航班预定等信息，而且不能处理多步骤表单的处理。

当我还是一个毕业生参加早些时候 VLDB 会 议，也有一些文章是讲 Deep Web 的。 大部分的解决方案似乎是一个数据集成一体化的方案。有一种虚拟一体化的办法，为每一个域名（网站）建立一个虚拟的表单，收集每个域名的数据源，然后构建语 义类型的从数据源到虚拟表单的映射关系，这种模式也是当前非常流行的设计垂直搜索引擎（特定领域的搜索引擎）的设计方案。不过这并不是一个能够很好的推广 的方案。首先，有太多的网站域名（重复和很难界定是否重复），建设和建模这样一个系统是非常困难的。其次有运行时间的问题，如查询路由的选择问题（确定用 户关键字和哪个数据源最相关），如果路由选择做的不够好，可能会导致 Deep Web 数 据源的负载非常高。

相反，我们平常使用的称之为 Surfacing （表 面）。我们预先计算所有有趣的需要提交的 HTML 表单，每种形式的提交 对应一个独特的 URL 地址，然后把这些网址添加到搜索引擎索引，同其他 任何网页一样索引。这样对于 Surfacing 来说，有两个显着的优 势。首先， Dee Web 的网址可以被当作另一个 URL ，对现有的搜索引擎的是一种很好的补充。其次，当用户认为 Deep Web 的结果和关键词非常相关（基于搜索片段），用户会点击搜索结果，然后执行的一种表单形式的提交，大大减少 负载 Deep Web 网页源。

然而，这种形式也对搜索引擎提出了新的挑战：

1、 如何适当的预测文本表单的输入值？如：在 recipes.com 需要输入正确的原料 名称， borderstores.com 需 要输入正确的 ZIP 编码。

2、 预测正确的输入的组合。一个表单可能同时存在多个输入框，假如只能一个简单的预测方 案，创造一切可能的预测结果会非常浪费并且耗费资源。例如 cars.com ， 仅仅只有 50 万个列表页面，但是会产生的 2.5 亿 左右的可能性查询。

我们的目标是尽可能覆盖更多的 Deep Web 的内容，也就是要影响尽可能多的搜索引擎的用户查询关键词。当前我们已经知道有超过 1 千 万的表单需要覆盖，此外，由于表单产生的分布具有“重尾”的特性，每周能够新产生 80 万 唯一的表单，同时 Deep Web 总体的覆盖度比特定网站的覆盖度更重 要。我们不能把眼光聚集到 1000 个网站，而应该更加高效率的解决百万 级别的表单的提交，我们需要面对很多各种各样的网站和各种语言的网站，并且不能人工的执行循环或者有一些特定的脚本去做这些事情。

网页的提交一般都是采用表单的方式，通过各种各样的表单项和组合可以形成各种各样的查 询。表单的提交方式有两种， POST 方式和 GET 方 式， POST 方式所有的提交网址都是同一种形式，表单内容都隐藏在 HTTP 的 请求中一起提交的，而 GET 方式则每次都是不一样的。

我们可以想象每一个 Form 后 面都有一个数据库，每一次 Form 的提交就类似于查询 SQL 语 句一样： select * from DB where I₁ =V₁ and … and I_N =V_N 。 但是也不是所有 Form 中的每一个表单都是对于这个数据库是有意义的。 比如：排序，分页大小的选择等等。如何得到一个非常适合的 Query 集 合是非常关键的。

为了得到更合适的 Query 集 合，我们想到了采用 Query 模版，也就是一个 Query 的 表单集，能够迭代得到最多可能的所有的 Query 。对于一个卖书的商 店，对应的 Query 集合可能如下：

{select * from DB where zip = z | z are valid zip codes }

{select * from DB where type = t | t are valid store types }

{select * from DB where zip = z and type = t | … }

对于一个 HTMl 表 单来说，经常会存在同时存在多个输入域，假如我们需要穷举得到所有可能的 Query 集 合，这个是非常复杂的事情，而且会非常浪费。产生太多的 Query 会导 致爬虫在抓取的过程中抓取太多无用的信息，其实我们更需要得到所有可能的表单组合，并不一定是采用穷举的方式来实现，我们的目标是采用最小的集合得到最大 的产出，物超所值！

但是 我们也需要考虑其他的问题：比如每一条产生的 URL 都会被建立到索引文 件里去，我们必须得到尽可能好的 URL 地址，我们也不需要穷尽后台数据 库对应的每条记录，我们产生的所有的 Query 只要能够代表整个 Deep Web 站点就可以了。

假如我们绑定的参数尽可能的多，那么会产生足够多的 Query ， 这样会得到很多的空结果页面，整个站点的覆盖度会非常高。相反，假如我们绑定的参数比较少，相应产生的 Query 集 合比较小，这样会导致 Query 太单一，结果和 Query 不一定相关，整个网站覆盖率太低的问题。

如何才是一个真正好的 Query 模 版呢？依赖网站后台数据库大小？依赖 Query 得到结果量的趋势？

 

如图所示：对于两种不同的 Query 集 合，有些能产生信息，而有些并不能带来更多的信息，对于“ state ” 这个参数来说，是有价值的，但是对于“ type ”这个参数来说，并不能 带来更多的有价值的信息。

为了识别有效地信息模版，得到有效地 form 表 单。我们必须能够做到如下几点：

1、 能够随即抽样一些 Form 表 单；

2、 分析和比较通过 From 表 单得到的结果页面；

3、 对结果页面进行信息的签名，能够唯一标识页面；

4、 页面信息签名必须能够应对布局经常改动的页面，某些具有动态广告的页面等。

如 下图所示：采用穷举所有的 Query 集合和绑定三个输入源产生的 Query 集 合与得到的信息量曲线：

 

 

通过 测试我们得到两个结论：

大模版是非常有用的。采用简单的策略进行比较，我们仅仅考虑绑定输入域多少的模版，如下所示：

a) 模版大小为 1 的 时候为谷歌贡献了 6% 的搜索结果

b) 模版大小为 2 的 时候为谷歌贡献了 37% 的搜索结果

c) 模版大小为 3 的 时候为谷歌贡献了 57% 的搜索结果

Google 的 Deep Web 爬虫具有如下特征：

a) 采用信息模版的解决方案来实现爬虫

b) 通过上百万的 Form 来 实现自动描述

c) 跨越多个站点和 50 多 种语言

d) 每秒能够产生 100 多 个 Query

e) 每天能够产生 40 万 以上的结果页面

f) 每周能够产生 80 万 以上的结果页面

Google 未来的工作，能够 完成更多的 Form ，比如实现 Post 方 式提交的 From ，当前某些站点采用 JS 提 交的 Form 等。

译者注： Deep Web 指 那些存储在网络数据库里、不能通过超链接访问而需要通过动态网页技术访问的资源集合。网络数据库包括搜索引擎数据库、在线专业数据库及站内搜索数据库，当 前的搜索引擎仅仅包含了很少的部分内容，据 BrightPlanet 公 司技术白皮书, Deep Web 资源容量约为 Surface Web 的 500 倍，而且包 含着更多有价值的资源。当时最大的搜索引擎只索引了 Surface Web 中 的 16 ％信息量，而如果算上那些无法被传统搜索引擎索引的 Deep Web 中的信息，那么一般搜索引擎只能搜索 0.03 ％ 的 Web 信息。但是要实现能够抓取这部分的信息，对于爬虫来说具有很大 的挑战，不仅仅需要爬虫能够自动识别 Form ，对网站进行分类，自动识 别表单类型和需要填写的表单值，而且需要根据提交的 Query 去噪，识 别和抽取得到的信息，