论文部分内容阅读
随着Interact的飞速发展,Web已经发展成为一个全球的、巨大的、分布和共享的信息空间,为用户提供了一个极具价值的资源。但因Interact所固有的开放性、动态性与异构性,使得用户很难准确快捷地从WWW上获取所需信息。如何快速准确地从浩瀚的信息资源中找到所需信息成为困扰网络用户的一大难题,这就是所谓的RichData-Poor Information。针对这一问题,出现了Web信息抽取技术。Web信息抽取系统从Internet上抽取的信息不仅可以直接提供给用户,还可以作为构建智能查询系统和数据挖掘系统的基础,有着广阔的应用前景。
本文在概述Web信息抽取以及分析现有系统的基础上,针对数据密集型网站,设计并实现了一种新的基于网站结构的Web信息抽取方案。该方案主要包括四个步骤:(1)网站结构树生成:从网站的拓扑结构入手,根据网页之间的链接关系,生成网站结构图;然后去掉网站结构图中的回溯边,将网站结构图转化成网站结构树;(2)页面规范化:将网站结构树的叶子结点所在的页面进行规范化,转换成格式良好的XHTML文档;(3)页面二次聚类:采用二次聚类算法对网站结构树的叶子结点根据文档的组织结构进行聚类;(4)模板推导:采用匹配算法推导出每类的模板。
本文所取得的主要研究成果如下:
(1)提出了由网站结构图生成网站结构树的算法。该算法的目的是去掉网站结构图中的回溯边,从而将网站结构图转化成网站结构树,其主要思路是:首先根据网页结点URL所在目录的层次关系,去掉网站结构图中的部分回溯边;然后在宽度优先遍历的过程中去掉已经遍历过的重复结点,生成网站结构树。实验证明了该算法的有效性。
(2)针对聚合聚类算法时间耗费较大从而不适合数据量大的网站的特点,本文提出二次聚类算法对此进行了改进。二次聚类算法首先将网站结构树中深度值最大的叶子结点与其兄弟结点合并为同一类,称为“一次聚类”;然后采用聚合聚类法对一次聚类的结果以及剩余叶子结点进行聚类,称为“二次聚类”。这样可以大大减少聚合聚类的工作量,提高聚类的运行速度。并且实验证明,结果基本上能够达到聚类要求。
(3)模板推导是本文研究的重点。本文引入抽象语法树(Abstract Syntax Tree,AST)和union-free正则表达式的概念,并且用AST描述的union.free正则表达式来表示模板(即包装器),提出了一种新的模板推导方法。该方法采用树状结构的匹配算法,对表示为AST的当前包装器和DOM树形式的当前样本进行匹配操作。算法不仅能够正确推导出结构上的可选、迭代模式,而且能推导出文本模板。
本文设计实现的Web信息抽取方案,可以自动推导出数据密集型网站中各类网页的通用结构模板和文本模板,从而利用该模板对同类网页的信息进行抽取,为当前Web信息抽取方法的研究提供了新的思路。