这是笔者参加今年的泰迪杯C题的论文简化版。虽然最后只评上了一个安慰奖,但个人感觉里边有些思路对爬虫工作还是有些参加价值的。所以还是放出来供大家参考一下。

I. 简介

一个爬虫可以分为两个步骤:1.把网页下载下来;2.从网页中把所需要的信息抽取出来。这两个步骤都存在相应的技术难点。对于第一个步骤,难度在于如何应对各大网站的反爬虫措施,如访问频率过高则封IP或者给出验证码等,这需要根据不同网站的不同反爬虫措施来设计,理论上不存在通用的可能性。对于第二个步骤,传统的做法是设计对应的正则表达式,随着网站设计上日益多样化,正则表达式的写法也相应变得困难。

显然,想要得到一个通用的爬虫方案,用传统的正则表达式的方案是相当困难的。但如果我们跳出正则表达式的思维局限,从全局的思维来看网站,结合DOM树来解析,那么可以得到一个相当通用的方案。因此,本文的主要内容,是围绕着爬虫的第二个步骤进行展开。本文的工作分为两个部分进行:首先,提出了一个适用于一般网站的信息抽取方案,接着,将这个方案细化,落实到论坛的信息抽取上。

II. 流程

看上去很高端,但事实上思想一句话就可以说完,那就是“做减法”:网页内容-网页模版=网页有效内容。网页模版怎么来?是同一网站的所有网页的交!

具体流程大概就是

1、把待爬取网站的页面下载下来,并将其解析为DOM树;

2、比较若干个页面的DOM树,得到网站的基础模板;

3、以“深度优先”的方式遍历DOM树,给树的每个节点和叶子都编号;

4、将每个页面的DOM树与标准模板比较,差异部分即为有效文本;

5、通过一些人工规则进一步过滤;

6、以节点和叶子的编号为值,对有效文本进行聚类分块。

III. 解析

下面对上述流程稍加解释。

正常的网页源代码,都是HTML标签与有效文本的混合,而且不同的网站有不同的模板,这就带来了通用爬取的困难。但是,在同一个网站的不同页面内,页面之前却具有统一性。用通俗的话说,就是:同一个网站,不同的页面的样子看起来是差不多的,唯一的区别就是页面的主要内容了。

因此,对于通用爬虫,我们的设计思路是:利用同一网站的不同页面,来构造该网站的标准模板,把同一网站的任意页面与标准模板进行比较,其差异处就是我们所需要提取的有效文本。在这个过程中,我们利用了DOM树来对网页源代码进行语法解析。

HTML代码

正常的一个比较规范的HTML页面源代码,大概是如下这样的

<html>
    <head>
        <meta charset="UTF-8">
        <title>这是网站的标题</title>
    </head>
    <body>
        <div id="post_1">
            <h2>这是文章的标题1</h2>
            <a href="http://xxx.com"><img src="http://xxx.com/test.img"></a>
        </div>
        <div id="post_2">
            <h2>这是文章的标题2</h2>
            <a href="http://xxx.com"><img src="http://xxx.com/test.img"></a>
        </div>
        <div id="post_3">
            <h2>这是文章的标题3</h2>
            <a href="http://xxx.com"><img src="http://xxx.com/test.img"></a>
        </div>
    </body>
</html>

DOM树

我们可以把一个HTML页面的源代码,解析为树结构,称为DOM树,全称为Document Object Model。它是一个文档对象模型, 使用对象的表示方式来表示对应的文档结构及其中的内容。如前面所示的HTML页面,可以表示为如下的DOM树结构:

DOM树.png

也就是说,网页实际上是HTML标签的层层嵌套,每个标签是树中的节点或者叶子,而网页的文本内容就在这些标签之中。解析为DOM树的一个好处就是我们可以忽略掉具体样式的干扰,比如

<div id="content" class="content">
    <h2 id="title_1" class="title_1">今天天气不错</h2>
    <h2 id="title_2" class="title_2">通用爬虫方案</h2>
</div>

这里的div和h2都是固定的标签,但为了给不同的标题分配不同的样式,所以这里给每个<h2>标签设置了不同的id和class,id和class是可以自由设置的(或者按照某种规律自动生成),这就给通用爬取造成了困难。但是,如果解析为DOM树,就会自动地忽略这些特定标记,而只保留通用的div和h2标记。

解析为DOM树的另外一个好处是能够描述网页的层次结构,使得我们可以有序地去遍历一个HTML页面,并且通过不同页面层次的划分,来对所爬取的内容进行划分。

标准模板

对于同一个网站,我们先依此下载若干个页面,然后解析为DOM树。接着,我们将每个节点或者叶子,都表示为“标签路径+标签文本”的形式,如前面所示的HTML页面,它的网站标题可以表示为“html_head_title_这是网站的标题”,它的文章标题可以表示为“html_body_div_h2_这是文章的标题1”,注意,并非每个标签都有文本内容的,如标签一般就没有文本,这里我们只考虑带有文本的标签。

这时候,每一个网页就表示为标签的集合了,我们可以定义网站的标准模版为:
\begin{equation}S = \bigcap_{h\in H} h\end{equation}
其中$H$是该网站所有网页的集合。也就是说,标准模板就是所有网页的交集。这时候,提取网页有效文本就很简单了:
\begin{equation}\text{effective} = h\backslash S\end{equation}
也就是说,$h$页面的有效文本,就是$h$集合与$S$集合的差集。

通过这个方案,我们可以自动地为任意指定网站来构建标准模板,从而提取页面的有效文本,这个过程是基于“网页间同样的内容就是没有意义的,而不同的内容才是有爬取价值的”这个假设下成立的。这样的话,不管网站层次结构如何,有没有植入广告,我们都可以有效地把无效文本过滤掉。这样,我们就得到了一个通用的爬取方案了。

流水生成

尽管我们将标准模板定义为所有页面的交,但我们并不需要将所有页面爬取下来后,再得到标注模版。在开始时,我们可以只使用两个页面,取它们的交集作为标准模板,然后每爬取一个新的页面,我们就可以更新标准模板,使得标准模板越来越精确。这种流水式的方案,符合生产环境的要求。

规则过滤

在某些网站上,不同页面嵌套了不同的代码,因此,用前面的方案进行爬取后,会把这些代码同时也保存下来,降低了有效文本的精度,因此需要一些过滤规则来过滤掉它们。

工程规则

从生产角度,通常来说愿意放弃一些精度,而换取更高的速度。因此很显然,对于工程上来说,最容易实现的办法就是统计前面所得到的每一段有效文本的中英文字数之比,然后基于“网页内容基本都是中文”这个假设,我们就可以放心地去掉中文占比低的部分了。

当然,这同时也会把日期和用户名等信息去掉,因此,我们要先识别出日期和用户名,以防止误删。对于日期来说,故事相对来说比较固定,比如“2017-04-15”、“2017年4月15日”等,还通常伴有“发布时间”、“发表于”等字眼,因此相对容易识别。而对于用户名,通常来说用户名是中文、英文、数字和下划线的组合,不允许空格,而恰好代码是含有很多空格的,因此,根据这个过滤,可以提前识别用户名。

所以,总的规则就是:

1、带有日期格式的文本需要保留;

2、纯粹由中文、英文、数字和下划线组合而成的文本需要保留;

3、剩下的部分中,中文占比大于某个阈值的,需要保留;

4、其余内容直接过滤掉。

学术方案

工程的规则是简单高效,但只适用于特定的情况。比如,上述规则适合于一般中文网站的爬取,但如果是英文网站,这个规则就不适合了。

总的来说,这事实上是判断一段文本是不是自然语言的问题,我们可以使用语言模型。语言模型是对句子概率进行的建模,一个句子由$n$个词$w_1,w_2,\dots,w_n$构成,我们考虑概率:
\begin{equation}P(w_1,w_2,\dots,w_n)\end{equation}
根据概率论的公式,我们得到
\begin{equation}P(w_1,w_2,\dots,w_n)=P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)\dots P(w_n|w_1,w_2,\dots,w_{n-1})\end{equation}
上式等号右端一般是很难精确估算的,为此,我们做个截断:\emph{后一个词的概率只取决于前一个词的概率},这样一来就得到
\begin{equation}\label{eq:score}P(w_1,w_2,\dots,w_n)=P(w_1)P(w_2|w_1)P(w_3|w_2)\dots P(w_n|w_{n-1})\end{equation}
这样我们只需要统计每个词的概率$P(w_i)$和相邻词的共现概率$P(w_{i-1}, w_{i})$,就可以算得转移概率
\begin{equation}P(w_i|w_{i-1}) = \frac{P(w_{i-1}, w_{i})}{P(w_{i-1})}\end{equation}

有了转移概率之后,我们就可以利用式$\eqref{eq:score}$给每段文本打分,然后设定一个阈值,只有大于这个阈值,才断定它是自然语言,从而保留下来。这种方案同时适用于所有语种(只需要对应语种的语言模型),是理论上更加漂亮的模型。


转载到请包括本文地址:http://kexue.fm/archives/4413/

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!