基于ＤＯＭ和网页模板的Ｗｅｂ信息抽取:学生html个人网页模板

　　摘要：文章提出了一种基于DOM(文档结构模型)和网页模板的Web信息提取方法。参照DOM的定义，通过构造HTML解析树来描述网页结构。在抽取网页之前，先通过归纳网页模板来过滤网页中的噪音信息。然后，使用基于相对路径的抽取规则来进行信息抽取。最后，本文给出了归纳网页模板和抽取网页信息的实验结果。实验结果表明本文提出的归纳网页模板方法和信息抽取方法是正确的和高效的。
　　关键词：信息抽取；文档结构模型；网页模板；抽取规则；相对路径
　　中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)18-31617-03
　　Information Extraction for the Web Sources Based on DOM and WebTemPlate
　　WANG Li,TANG Jian-xiong
　　(Computer Science and Technology School,WuHan University of Technology,Wuhan 430063,China)
　　Abstract:Information extraction studled by the Paper is based on D0M (Document object Model) and web template. According to the definition of DOM, the paper describes the structure of web Pages by constructing HTML Parsing tree. Before Information extraction, the noise information can be filtrated in web pages by inducting web template. Then, the paper uses the extraction rule based on relative path to extract information in web pages. At last，the paper presents the result of inducting web template3s and extracting web pages. From the result,it is evident that the way of inducting web templates and the way of extracting web pages are correct and effective.
　　Key words:Information Extraction;DOM;WebTemPlate;ExtractionRule;Relative Path
　　
　　1 引言
　　
　　随着互联网的飞速发展，互联网已经成为一个巨大的知识库。目前，Web上的网页已经成为人们日常生活中学习知识、获取信息必不可少的来源。为了有效地利用互联网上的信息，信息抽取技术应运而生。信息抽取技术属于人工智能的一个分支。使用信息抽取技术可以人性化地从网页中把人们需要的信息抽取出来。
　　
　　2 基本思想
　　
　　Web信息抽取流程如图1。
　　图1 Web信息抽取流程
　　2.1采集页面
　　页面采集分为手动和自动两种方法。手动方法是指通过人手打开需要浏览的网页，然后把它保存到电脑中。而自动的方法则是通过程序自动的从互联网上获取网页，大大地节省了工作时间。本文采用的是自动搜集网页的方式。因为具有相似结构的网页的地址形式一般是相似的。搜集页面的时候，只要指定id的范围，就能自动地获取页面。
　　采集页面过程中需要构造DOM树，即 HTML解析树，其算法如下：
　　while (读取数据没有到文件尾) {
　　获取HTML文档中的标签
　　if(获取标签成功) {返回标签名称和标签类型}
　　if(获取标签成功){
　　if(标签为开始标签){
　　if(根结点为空) {
　　根据标签名创建根结点
　　当前结点指向根结点
　　continue }
　　else{
　　if(标签属于没有结束标签的标签){
　　根据标签名创建新结点，并且为该结点赋值，
　　当前结点指向当前结点的父结点}
　　else{
　　根据获取标签创建新结点，当前结点指向新结点
　　}}}
　　else{
　　if(当前结点的结点名不等于结束标签名){
　　当前结点到结束标签所对应的结点之间的每一个祖先结点，如果该祖先结点得不到匹配，则把它删除，并调整 HTML解析树。}
　　当前结点指向该结束标签所对应的结点
　　if(当前结点为叶子结点){
　　当前结点赋值为该结束标签与开始标签之间的内容
　　} } } }
　　生成了HTML解析树后，要进一步的过滤HTML解析树的内容。、等标签的内容是没有意义的。另外，HTML文档中的转义字符要进行转换，制表符要被消除。最后还要去掉内容的前导空白和后置空白。通过过滤 HTML解析树中的不必要内容，能够使最后的抽取结果包含尽可能少的无关信息。
　　2.2生成模板
　　通过比较两个具有相似结构的网页的 HTML解析树而得到网页模板。理论上，算法可以归纳到任意层的子树。然后，由于如标题栏、导航栏这样的噪音信息一般分布在网页的外层。所以一般只需比较两层的子树就足够了。归纳网页模板是通过以下两个算法来实现的：
　　(1)比较两个结点是否相同的算法如下
　　if(1结点的标签不等于r结点的标签)返回false;
　　if(1结点的内容不为空而r结点的内容为空)返回false;
　　if(l结点的内容为空而r结点的内容不为空)返回false;
　　if(l结点的内容为空且r结点的内容为空)返回true;
　　if(1结点的内容等于r结点的内容)返回true;
　　if(l结点的标签等于r结点的标签并且1，r都不是叶子结点)返回true;
　　返回 false;
　　(2)比较两个分支是否相同的算法如下：
　　cur1= 1;cur2=r;
　　do{
　　while(cur1的儿子结点和cur2的儿子结点不为空且都没有被访问过){
　　cur1，cur2分别指向其儿子结点}
　　if(cur1和cur2都没被访问过){
　　curl，cur2 标记为已访问
　　result= ComPareTag(curl，cur2);
　　if(result等于false){
　　do{
　　curl和cur2指向其父亲结点，并标记为已访问
　　结点)
　　if(cur1和cur2是所处层数小于等于2的“table’结点，break;} while(true);
　　curl，cur2标记为己访问，并且标记为非模板结点}
　　if(result等于true)
　　if(cur1和cur2是所处层数小于等于2的“table”结点)curl，cur2标记为模板结点}
　　if(cur1和curZ的兄弟结点不为空且都没有被访问过)curl指向curl的下一个兄弟结点，curZ指向curZ的下一个兄弟结点
　　else{curl、cur2分别指向其父亲结点
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　if(curl或cur2为空)退出函数
　　if(curl和cur2都没有被访问过){
　　curl，cur2标记为己访问
　　result= ComPareTag(curl，cur2);
　　if(result等于false){
　　do{
　　if(cur1和curZ是所处层数小于等于2的“table”结点){curl、cur2标记为非模板结点
　　break;}
　　curl、cur2分别指向其父亲结点
　　curl、cur2标记为已访问}while(true);}
　　if(result等于true{
　　if(curl和cur2是所处层数小于等于2的“table”结点) curl、cur2 标记为模板结点 }}}}while(true);
　　把两个网页的HTML解析树分成一个个的分支，通过运用比较两个分支是否相同的算法，得出每一个分支的局部网页模板，然后再把这些局部网页模板按照其层次结构，组合成一棵网页模板树。把HTML解析树分成一个个的分支，只需要把“body”结点的儿子结点和其儿子结点的兄弟结点遍历一次就可以了。
　　生成了网页模板后就把网页模板保存到XML文件中。获取了网页模板后，就可以运用网页模板去过滤相似网页中的噪音内容。从而一方面可以节省存储空间，另一方面可以缩小信息抽取的范围。
　　2.3获取规则
　　根据网页模板对输入的网页的HTML解析树进行删减后，可以获得一棵更小的HTML解析树。这棵HTML解析树是通过过滤噪音信息生成的，是用户真正感兴趣的部分。抽取规则也是基于这棵HTML解析树生成的。
　　本文的抽取规则分为两类，一类是基于非循环信息的抽取规则，另一类是基于循环信息的抽取规则，并且在生成抽取规则的时候可以定制待抽取结点的结点名称，使得以后把抽取结果存入XML文件时，对应XML文件的元素名称就是这个定制的名称，从而使得XML中的结果具有自描述性。
　　(1)生成基于非循环信息的抽取规则：
　　a.选中一个结点作为参考点。
　　b.选中需要抽取的结点，并命名该结点，计算该结点相对于参考点的路径。
　　c.重复b，直至选中了所有感兴趣的信息。
　　(2)生成基于循环信息的抽取规则：
　　a.选中一个结点作为主要参考点。
　　b.选中一个结点作为次要参考点，计算次要参考点相对于主要参考点的路径。
　　c.选中需要抽取的结点，并命名该结点。如果需要抽取的结点是次要参考的子孙结点，计算该结点相对于次要参考点的路径。
　　d.重复c，直至选中了所有感兴趣的信息。
　　同一个网站中存在着许多结构相似的网页，所以抽取规则是可以复用的。因此把抽取规则保存到XML文件中。
　　2.4抽取信息
　　如图2，当获得了网页模板和抽取规则后，对于输入的一个具有相似结构的网页，先生成它的HTML解析树，然后运用对应的网页模板来过滤该网页中的噪音信息，从而生成一棵更小的HTML解析树，对这棵HTML解析树运用抽取规则，就可以把信息从HTML解析树中抽取出来。相应的，抽取信息也有两种，一种是抽取非循环信息，另一种是抽取循环信息。
　　图2 抽取信息过程
　　(1)抽取非循环信息过程如下：
　　a.为输入的网页生成HTML解析树。
　　b.用对应的网页模板来删减HTML解析树。
　　c.读取对应该网页的保存抽取规则的XML文件。
　　d.根据文件中的“pivot”标签中的内容来确定参考点。
　　e.根据文件中的“data”标签中的“rule”子标签生成待抽取信息基于参考点的相对路径来进行信息抽取，以“data”标签中的 “text”标签的内容作为该抽取结果的名称。
　　f.重复e，通过访问所有的“data”标签，从按照“rule”子标签中的定义的相对路径把所有的信息抽取出来。
　　(2)抽取循环信息过程如下：
　　a.为输入的网页生成HTML解析树。
　　b.用对应的网页模板来删减HTML解析树。
　　c.读取对应该网页的保存抽取规则的XML文件
　　d.根据文件中的“pivot”标签中的内容来确定主要参考点。
　　e.根据文件中的“pivotZ”标签中的“rule”子标签来获取次要参考点相对于主要参考点的路径，从而确定次要参考点。
　　f.根据文件中的“data”标签中的“rule”子标签生成待抽取信息基于次要参考点的相对路径来进行信息抽取，以“data”标签中的“text”标签的内容作为该抽取结果的名称。
　　g.重复f，通过访问所有的“data”标签，按照“rule”子标签中的定义的相对于次要参考点的路径把所有的信息抽取出来。
　　h.重复g，循环的抽取所有信息项。
　　完成了信息抽取后，把抽取结果存入XML文件中。由于网站都会不定期地进行改版。改版后网页结构的变动相当大，使得即使基于相对路径的抽取规则也是无效的。然后，尽管网页改版了，但是网页中的主要信息是不变的，以及用于表现这些信息的网址一般也是不变的。因此，可以利用以前的抽取结果来重新生成抽取规则。
　　(1)重新生成基于非循环信息的抽取规则:
　　a.打开保存抽取规则的XML文件，读取该XML文件中“pivot”元素的内容。
　　b.打开保存抽取结果的XML文件，读取抽取结果和对应的网页地址。
　　c.根据网页地址找到改版后的网页，生成该网页的HTML解析树。
　　d.查找匹配“pivot”元素内容的结点，该结点作为参考点，重新生成参考点结点的绝对路径。
　　e.查找匹配抽取结果的结点，重新生成该结点的绝对路径，并且计算该结点相对于参考点的相对路径，从而得出抽取规则。
　　f.重复e，直到重新生成所有抽取结果的抽取规则为止。
　　(2)重新生成基于循环信息的抽取规则
　　a.打开保存抽取规则的XML文件，读取该XML文件中“Pivot”元素的内容。
　　b.打开保存抽取结果的XML文件，读取抽取结果和对应的网页地址。
　　c.根据网页地址找到改版后的网页，生成该网页的HTML解析树。
　　d.查找匹配“Pivot”元素内容的结点，该结点作为主要参考点，重新生成主要参考点结点的绝对路径。
　　e.取出两个对应的数据项A，B(A、B属于不同的“data”元素，但其“URL”元素的内容是一样的)。查找匹配这两个数据项的结点，然后分别获取其绝对路径。这两条绝对路径的最后一次相交处的结点记为P结点。
　　f.在数据项A到P结点的相对路径上，P结点的儿子结点就是次要参考点。计算P结点到主要参考点的相对路径，从而得出主要抽取规则。
　　g.对于数据项 A所在的“data”元素，对于“data”元素下的所有数据项 (“URL”除外)，分别通过内容匹配的方法，在HTML解析树上找到其所对应的结点，然后分别生成这些数据项相对于次要参考点的路径，从而得出次要抽取规则。
　　3 系统评价与分析
　　实验的目的是为了验证本文提出的归纳网页模板的方法的有效性。评价指标包括归纳时间、删减时间和缩减率。
　　归纳时间：归纳时间是指由相似网页的 HTML解析树归纳网页模板树所需要的时间。
　　删减时间：用网页模板对网页的HTML解析树进行删减所需要的时间。
　　缩减率：缩减率是指经过使用网页模板过滤网页中的噪音后得到的网页的大小与原来的网页大小的比值。
　　在CPU为P4 1.6G，内存256M的电脑上，对表1中的8个网页集合，从每个网页集合中随机取出两个网页来归纳网页模板，情况如表2。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　从表2中可以看到归纳网页模板的方法是有效的，并且归纳时间很短，都在50ms以内，影响归纳时间的主要因素是网页的大小，网页所占的空间越大，一般来说，需要的时间就越长。而删减时间都在 10ms以内。影响删减时间的主要因素是网页的大小和网页模板树中结点的多少。网页越大，网页模板树中的结点越多，需要的分析就越多，因此需要的时间也就越多，反之亦然。而缩减率一般在0.4和0.5左右。影响缩减率的主要因素是网页中的噪音。噪音越多，缩减率就越小。网页集6出现了0.14的缩减率，是因为论坛信息所占网页中的比例很小。而网页集8出现了0.72的缩减率是因为该报价页面中有用的信息所占的比例很大。
　　表1 实验网页集
　　表2 网页模板归纳结果
　　
　　4 结束语
　　
　　本文研究的目标是对结构相似的网页进行信息抽取，所以需要的训练样品不多。通过归纳网页模板，可以减少网页中的噪音信息，从而能够提高信息抽取的准确率。而且基于相对路径的抽取规则具有自适应的特性，即使网站改版了，也能根据以前页面上的信息重新的自动的生成抽取规则。可见，本文所提提出的归纳网页模板方法和信息抽取方法是正确的和高效的。
　　
　　参考文献：
　　[1]Florescu D,Levy A Y,Mendelzon A.Database techniques for the World-Wide Web: A Survery. In: ACM The SIGMOD Rec-
　　ord,1998.59-74.
　　[2]Ziv Bar-Yossef,Sridhar Rajagopalan.Template Detection via Data Mining and its APPlication.WWW2002,2002.
　　[3]李效东,顾毓清.基于DOM的Web信息抽取[J].计算机学报,2002;25(5):526-533.
　　[4]Laender AHF,Ribeiro-Neto BA, Da Silva AS.et al. A Brief Survey of Web Data Extraction Tools[J].SIGMOD Record,2002,31(2):84-93.
　　[5]LI Xiangyang,ZHANG Yafei,LU Jianjiang,et al.A classific- ation method for web information extraction[J].Wuhan Unive-rsity Journal of Natural Sciences,2004,9(5):823-827.
　　[6]Crescenzi V,Mecca G.On Automatic Information Extra- ction from Large Web Sites[R].Technical Report DIA-76-2003.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文