首页 > 搜索引擎 > “暗网”信息的抓取(1) (Crawling the Hidden Web)

“暗网”信息的抓取(1) (Crawling the Hidden Web)

写在最前面:最近,看了Sriram Raghavan, Hector Garcia-Molina的《Crawling the Hidden Web》一文,下面对文中所讲述主要的思想做一个简要的概括,同时就文中作者的想法,谈一些我自己的看法。

有研究表明(1997年的),互联网上的网页有80%多的是动态页面(Dynamic Pages)。现在,随着各种各样的高级编程语言和一些功能更加完备的web服务器的出现,使得动态页面的生成越来越简单。因此,80%这个比例,在现在看来,只是一个保守的估计,现在的比例肯定是高于80%的。

为什么要讲动态页面的比例呢,因为,在这里所讲的“暗网”(Hidden Web)指的是由动态页面产生的。但是,并不是所有的动态页面都属于“暗网”(Hidden Web),在这里,暗网是指那些,只有通过提交一个表单(Form)才能从数据库获取到相关信息的Web页面所组成的网。通常,我们所用的搜索引擎,只是为那些可以直接从网上抓取下来的页面建了索引,然后我们搜索的时候,得到的结果也只是从这部分页面中筛选出来的。因此,我们从搜索引擎能得到的只是小部分网页的一个结果集合。据统计,当前搜索引擎所收录的页面,只占整个互联网的千分之二。如果能把“暗网”里的页面收录下来,那么,搜索引擎的结果将会提高很大的一个档次。就在不久前,百度就提出过一个“阿拉丁”计划,大概就是讲的是要抓取暗网信息,提高检索结果的质量。但是,对暗网信息的抓取,面临的很大的挑战:一是,暗网信息量的庞大,二是,暗网信息的获取,获取不同数据库中的信息,所需要的接口有很大的不同。信息量的庞大,需要设计高效的分布式存储系统;数据获取接口的千变万化,需要设计高准确率,召回率的分布式计算处理系统。接下来,对《Crawling the Hidden Web》中的做法进行一个简单的介绍。

1. 动态页面的分类:

把动态页面从两个维度进行分类,一个是动态性,一个是动态页面产生机制。

从动态性来分,可以分为以下几种类型:

(1). 暂时性动态页(指含有根据时间变化的内容的页面)

(2).用户相关动态页(与用户个性化生成的页面等,比如个人主页,群组主页)

(3)  .基于用户输入的动态页(根据用户输入的不同,产生不同的页面)

从生成机制来分,可以分为以下几种类型:

(1).服务器端程序生成的动态页(CGI, Java Servlet等)

(2).内嵌服务端运行的代码片段的动态页(Jsp等)

(3).内嵌客户端运行的代码片段的动态页(Java Applet等)

一般来讲,暗网所关注的动态页,是指那个落在第一种分类的第(3)点和第二种分类的第(1)(2)点交集中的页面。不考虑第一种分类中(1)的原因是,当下的搜索引擎已经可以收录这部分,不考虑第一种分类中(2)的原因是,这种与个性化的动态页,对搜索引擎的价值不是很大,不考虑第二种分类中(3)的原因是,要在客户端边为执行动态代码提供相关环境,这样会使得爬虫的逻辑非常复杂。

2. 对网页中的表单(Form) 和表单的提交进行建模

(1)表单建模

表单F可以表示为: F = {(E1,D1), (E2,D2), …, (En,Dn)},其中(Ei,Di)为第i个(Element, Domain)对。

在这里Element是指:HTML中的selection lists, text boxes, text areas, checkboxes, or radio buttons

Domain是指:Element所指的Html控件的取值范围(值域),值域可以分为有限域(finite domain) 和无限域(infinite domain). 有限值域是指取值个数确定的,无限值域是指取值个数不确定的。

另外,还需要定义label(Ei), 表示第i个Element所对应的描述性文字

(2)对于取值 集合的建模

对于一个表单中某个特定的Element, 如果它所对应的值域是有限域,那么爬虫完全可以尝试各种取值,来进行抓取。而如果它所对应的值域是无限域,那么就不能采用上面的方法了。在这种情况下,就需要为该Element创建一个近似的有限域。下面对这种方法进行建模:

创建一个LVS(Label Value Set)的表,该表的每一项(可以是一行),是一个(L,V)对。其中,L是标签(label),V={v1,v2, …, vn}, 表示该标签的取值的集合。这里,每个V都有一个对应的函数Mv, 其中Mv(vi)用来计算vi的权重,它的值的大小表示Element Ei取值为vi时的有效性大小。

(3)取值建模

如果Element E对应的值域是有限域,那么直接取该有限域即可。如果Element E对应的值域是无限域,那么,需要在LVS表中找一项(L,V),满足如下条件: L与是LVS中与Element E的标签最为近似的标签,那么L所对应的有限域就是E的近似值域。

对于表单 F = {(E1,D1), (E2,D2), …, (En,Dn)}, 它的每个Elements把对应的值域分别是V1, V2, …, Vn, 那么可以得到F所有取值的集合为: ValAssign(F, LV S) = V1 x V2 x … x Vn

定义Smax为爬虫对表单F所能提交的最大次数,那么我们定义best=min{Smax, |V1|*|V2|*…*|Vn|}为爬虫所要提交表单F的次数。

如何从所有的表单赋值集合中找出best个最优的组合,在这里 采取Ranking的方法。如何ranking,下面提供三种计算方法:

A. Fuzzy Conjunction: 1

该方法用取值组合中的权值最小的那个值的权值为该组合的ranking值。

B. Average:

1

该方法中,用取值组合中所有取值的权值的平均值为该组合的ranking值。

C. Probabilistic:

2

该方法中,1-MVi(vi)表示的是取值vi不可信,没有用的概率,那么,1减去所有取值同时不可靠,没有用的概率,就是该组合可用的概率,也即是该组合的ranking值。

  1. raycheng
    2009年9月20日22:38 | #1

    这篇文章给出了抓去暗网的主要思想。
    对一些简单的form,这样的方法不失为一种好方法哟。

    • 2009年9月21日09:11 | #2

      你有认真看么?
      对复杂的form,有什么高见?

      • raycheng
        2009年9月22日22:58 | #3

        Oh,shit!
        Definitely i treat it seriously…
        复杂的form,比如说文本框。
        页面如果根据用户输入文本框的内容来显示相应的页面的话,那这种爬虫就不好办了。难道爬虫能通过不停地输入不同的内容来抓取?

        • 2009年9月22日23:12 | #4

          i think you really don’t understand what i have written above.

          上面的建模中,就提到了你所说的这种情况,就是要通过类似机器学习这样的方式,把一个无限值域训练得到一个近似的有限值域.
          (这里的无限值域的情况就是你所说的,由用户随便输入的那种)
          你现在明白了吗?这一点是上面建模的关键!

          • raycheng
            2009年9月22日23:41 | #5

            Oh,fuck
            你给我搞一个出来。。。

            • 2009年9月23日00:00 | #6

              Don’t you know what is Machine Learning ?
              Don’t you know what is methodology?

              If you are really interested in this topic, you can read my next post—Crawling the Hidden Web(2), there I will show one implementation of Crawler of the above type !!!!

              • raycheng
                2009年9月23日10:05 | #7

                Don’t you know what is Machine Learning ?
                Don’t you know what is methodology?
                哎,被打击了,被打击了,忒打击人呀。。。

                • 2009年9月23日12:57 | #8

                  I just want to tell you that when you didn’t understand what other people said, you should not pretend to have understood.

  1. 2009年9月20日12:52 | #1
您必须在 登录 后才能发布评论.