基于树先剪枝的网页正文抽取方法研究(全文)

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于树先剪枝的网页正文抽取方法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：本文提出了基于树先剪枝技术和信息熵的抽取网页正文新方法。该方法通过对网页上的各种模板和正文进行分析，提取按照信息熵定位的正文网页，把该正文网页转化成DOM树，再删除噪音节点，生成抽取公共路径，抽取相关网页。经过试验验证，该方法降低了搜索的复杂度，提高了搜索的准确度，提高了搜索效率。

关键词：剪枝技术；信息熵；DOM树；网页

1 引言

许多新闻网站使用模板来自动生成新闻网页，但是很多噪音严重影响网页新闻正文的抽取，如：导航栏、广告等等。文章把一个网页转化为一个简单树，使用简单树匹配算法来对网页进行聚类分析，从而解决了大规模数据效率低下问题。本文使用信息熵来判定样本树的公共抽取路径。在文献[1]中Reis只用RTDM（Restricted Top-Down Mapping）算法来计算两个树之间的相似度，这个算法是基于树编辑距离。它不但可以抽取给定网页的相关的文本，而且可以判断出噪音。文献[2]使用简单树匹配算法来计算两个树之间的相似度，简单树匹配算法是通过计算两个树最大的匹配值。通过研究发现来自同一网站的网页有很多相同之处，计算相似度没有必要匹配两个树的所有节点，因此不需要使用RTDM来计算两个树的相似度，这篇文章对STM算法进行了修改来解决计算两个简单树相似度的问题，由于这里只构建了一个包含标签孩子节点的简单树，因此复杂度远远小于RTDM。从实验结果来看，精确度也很理想。Reis对网页进行聚类后，把每个类生成一个ne-pattern，这里需要比较每个类中的所有网页，因此代价比较大。我们发现在同一个类中的网页分享一个相同的抽取路径，这个路径开始于标签。我们设计了一个高效的算法来找出每个类的抽取路径。

文章的主要贡献是：（1）构建了简单树并修改了简单树匹配算法。（2）使用信息熵来判定公共抽取路径。

2 相关工作

目前有很多研究是关于如何生成模板和抽取正文。Yang.SH[3] 使用统计学、结构化和可视区域的特征来检测模板。 Shuyi・z[4]模拟人类行为依靠模板提出了一个抽取方法。Lan・Y[5]构造了一个称作SST（Site Style Tree）新的树，来获取内容和格式，一般的噪音也可以被发现[6]。使用信息值来为每个节点赋权重。Donglin・C[7]有信息值来界定提交内容和评价内容的边界。他使用了可视信息和有效文本来定位正文.试验中我们发现因为空白区域和一些其它标记，有效文本的计算可能失真。Deng・C[8]，提出 VIPS（VIsion-based Page Segmentation）算法来抽取网页的语义结构。这里的语义结构是一个层级结构，每个节点对应一个块。[9]使用相同块出现的的次数来判断非文本区域。[10]根据标签的开始和结束，使用堆来帮助分块。Lin [11]对网页进行分块，然后构建数据向量。使用熵来判定块是否包含信息。

3 构建简单树和聚类

每个网页都可以转化为一棵DOM树，并且可以获得每个节点的属性。RTDM 算法包含了替换、删除和插入等操作，我们认为一棵树一旦被编辑后，树的结构也就发生了变化，这会影响到抽取的效果。我们实验发现来自同一网站的新闻网页结构基本相同。比如， Yahoo 许多新闻网页有，标签，而且它们的顺序和属性是相同的，新闻正文也保存在相同的标签中，因此我们可以根据网页结构对网页进行聚类，我们修改了简单树匹配算法使其可以计算两个简单树的相似度，这里的简单树不是包含所有树节点，这个树是节点的直接孩子，这里每个节点代表一个块[3]。

定义简单树匹配算法：

相似度的计算公式如下：

这里使用80%作为阀值。

4 判定公共抽取路径

这部分讨论如何找出公共抽取路径。在文献[1]中Reis通过文本长度来定位正文所在位置。这种方法有一定的局限性。为了解决这个问题，本文使用信息熵来定位正文位置。本文的假设条件如下：（1）节点区域越大，则该节点包含正文；（2）节点中包含的超链接越少，则该节点包含正文。因为每个类中的网页有相似的网页结构，因此只要找出类中任意一个页面的抽取路径，则该类的所有网页都共享此抽取路径。找出公共的抽取路径，需要找出包含正文的节点。

公共抽取路径的获取步骤如下：

（1）从每个类中随机的选取一个样本页；

（2）构造DOM树，同时对树进行先剪枝；

（3）生成公共抽取路径；

下面来讨论为什么要进行树先剪枝，以及如何进行树先剪枝和获取公共抽取路径。对网页进行树解析，我们会得到一个复杂的DOM树，其中树的节点包括：DOCTYPE html、head、body、style、script、div、span、comment、link、image、h2、ul、a、p等等。通过研究发现不会包含正文的标签如：DOCTYPE html、head、style、script、comment、link 、image、h2、ul、a等标签节点可以在构造DOM树时直接删除，这里这些节点可称作噪音节点。而像body、div、p、span等节点则需要进行判定方可决定是否删除。本文的判定算法如下：

输入：高度n的所有标签节点tag

输出：重要节点

方法：

TW初始化噪音节点集{DOCTYPE html，head，body，style，script，div，span，comment，link，image，h2，ul，a，p…}

for each 孩子节点 ∈ tag do

If（tag∈TW） {

delete tag；

}else if （width=0 or height=0 or text=0）{

delete tag；

}else{

计算important的方差判断是否停止树的构造；

}

这里返回max（ipt）的节点。使用递归方式可以得出一个抽取路径。其中j表示孩子节点数。i，m表示三个属性即：节点的height、width和text（不包含超链接的文本数）。经过试验我们得出停止构造树的阀值设置为0.1。下面从凤凰网随机获取一个新闻网页为例来判定公共抽取路径。

（1）标签的直接孩子如下所示：

style type="text/css"

script type="text/javascript"

div class="h_infoNav" width= 693 height=54 text=0

div class="h_mainNav " width=693 height =472 text=0

div class="pic1000" width= 693 height =90 text=0

div class="space10" width= 693 height =0 text=0

div class="focus" width= 1265 height =501 text=86

div class="searchDiv02" width=676 height=53 text=21

div class="main" width=676 height =10986 text=1409

div class="space10" width= 676 height =0 text=0

div class="links" width= 676 height =2245 text=54

#comment

style type="text/css"

div class="chaFotNav" width= 676 height =529 text=0

div class="chaFotNav02" width= 676 height =0 text=0

div class="chaFooter" width=676 height=76 text=9

script type="text/javascript"

div id="ifeng_da_le" width= 1 height =1 text=0

#comment

script type="text/javascript"

#comment

div id="ArpAdPro_iams1081" width=0 height =0 text=0

script language="javascript"

#comment

（2）带入上式判定算法，经过判定条件后，保留的节点如下：

div class="focus" width= 1265 height =501 text=86

div class="searchDiv02" width=676 height=53 text=21

div class="main" width=676 height =10986 text=1409

div class="links" width= 676 height =2245 text=54

div class="chaFooter" width= 676 height =76 text=9

（3）将上述结果代入重要度计算公式结果如下：

div class="focus" important=0.040

div class="searchDiv02" important=0.007

div class="main" important=0.612

div class="links" important=0.085

div class="chaFooter" important=0.008

（4）返回节点div class="main"，并计算节点的方差为0.0539，小于阀值0.1；

（5）对节点div class="main"做1-4操作；

（6）使用递归算法，直到节点的方差大于于阀值0.1时停止树的剪枝与构造；

最终得出抽取路径为：

本文在实际试验中是从15个不同的新闻网站上随机抓取 2000个新闻网页作为实验数据。试验结果如表1所示，RTDM[1] 算法最坏情况下的复杂度O（n1， n2）。这篇文章使用了标签的孩子来计算相似度，所以复杂度比RTDM 小的多。同时使用公共抽取路径代替ne-pattern。为了给每个类生成 ne-pattern。D・Reis 必须遍历每个网页，比较所有节点，而文章则避免了这些复杂操作。当抽取正文的时候D.Reis 使用文本长度来决定哪个是正文和标题，但是当正文和标题字数小于阀值时，这种方法就不合适了。这文章使用信息熵来计算节点的重要度。我们的算法和RTDM[1]算法做了比较：如表2所示。

5 结束语

文章介绍了一种抽取网页新闻正文的新方法，本方法通过信息熵确定网页类，随机抽取一个样本页，构建DOM树，使用先剪枝方法生成抽取路径，进行网页正文的抽取。同时，该方法删除了噪声节点，降低了搜索的复杂度，提高抽取效率。经过对15个网站进行正文抽取试验，准确率达到94%以上。与RDTM方法相比，抽取准确率得到了很大幅度的提高。然而我们的算法是基于结构化网页，对于非结构化网页可能会出现过多的聚类，效率变低下，因此我们会在接下来的工作中解决这个问题。

参考文献

[1]D・Reis， P・Golgher， A・Silva， etal， "Automatic Web News Extraction Using Tree Edit Distance"，2004，5：17-22.

[2]W・Yang，Identifying Syntactic Differences Between Two Programs[J].Software - Practice and Experience，1991，21（7）：739-755.

[3]Yong・SH， Liu・HL， Hon・YB.Automatic Data Extraction from Template -Generated Web pages. Journal of Software.2007，2（19）：209-223.

[4]Shuyi・Z，Ruihua・S，Ji-Rong・W.Template-Independent News Extraction Based on visual Consistency[J]. American Association for Artifical Intelligence， 2007.

[5]Lan・Y，Bing・L，Xiaoli・L.Eliminating Noisy Information in Web Pages for Data Mining[Z].ACM 1-58113-737-0/03/008，2003.

[6]Yeongjung・k，Jeahyun・P，Teehuan・K，etal.Web Information Extraction By Html Tree Edit Distance Matching". DOI10.1109/ICCIT，2007.

[7]DongLin・C，Xiangwen・L，Hongbo・X，etal.Blog Post and Comment Extraction Using Information Quantity of Web Format". AIRS LNCS 4993，2008：298-309.

[8]Deng C， Shipeng Y， Ji-Rong W and Wei-Ying M. VIPS： "a Vision-based Page Segmentation Algorithm Microsoft Research Microsoft Corporation One Microsoft Way Redmond"， WA 98052 ，2003.

[9]Sandip.D， Prasenjit Mitra， C.Lee G "Automatic Extraction of Informative Blocks from Webpages" ，ACM 1-58113-964-0/05/0003 ，2005.

[10]Jiangtao. Q， Changjie. T， Kaikuo.X， Qian.L "Web Contents Extracting for Web- Learning" ， Springer，2008 ， pp.59-68.

[11]Lin，S・H，Ho，J・M.Discovering Informative Content Bolcks from Web Documents[J].Proceedings of ACM SIGKDD， 2002.

基于树先剪枝的网页正文抽取方法研究

优秀范文

精选范文