第3章 动态网页信息抽取算法与模型
3.1 动态网页的类型与特点
据统计
WWW 上有80%的Web
页面是动态网页
例如搜索引擎返回的搜索结果
它们通常是由网站
动
网上商店的商品信
的后台数据库通过某种通用的模板构成
态网页的类型十分广泛
义
息页面都是典型的动态网页
因此具有十分相似的页面结构
如何从动态网页中抽取信息有着十分重要的意
因为它们通常是一个网站最为主要的信息来源动态网页按照信息项的分布主要分为两个类型
多记录动态网页 单记录动态网页
1
多记录动态网页
多记录是指一个动态网页中包含多个结构重复的记录项这个类型是动
态网页的主要信息表示类型
因为一个信息项的数据量往往很小
所以同一
个动态网页中通常包含超过10个甚至50
个的记录项结果就是多记录动态网页的一个典型例子中只包含了其中的4
项似性
例如搜索引擎的返回
图 3-1 是百度搜索引擎的返回结果网页网页中包含了10个信息项图
这10个信息项在结构和信息内容上都有很大的相
因此对于这类动态网页的抽取主要问题在于如何定为这些结构相似的
多记录项动态网页的另一个典型例子就是包含表格信息项的动态网页这里的表格信息并不等同于数据库中的表格
而是指包含表格形态的数据项
记录项以及如何提取这些信息项的共同的结构
图 3-1 百度搜索引擎结果
2 单记录项动态网页
动态网页中除了多记录项动态网页之外还有很大一部分动态网页仅包
含一个单一的记录项
这类网页通常出现在一些用于描述详细信息的场合中例如个人详细信息产品信息论文信息等图 3-2 是一个典型的单记录项动态网页该动态网页仅包含一个信息项包括姓名性别学历
电话
兴趣爱好等
这类动态网页信息抽取的难度比较高
因为记录项在结构上没
对于这类
随后在
也就是所谓
有单记录项动态网页所具有的相似性
动态网页的抽取
的自定义模板
模板的基础上定位并抽取信息项
因此很难准确定位记录项
通常需要在样例网页的基础上首先生成抽取模板
这一步往往需要用户自定义
如何从网页中正确的抽取出这些信息数据
如何定位这些数
据以及如何生成抽取信息的模板式这类动态网页信息抽取的难点
图 3-2 单记录项动态网页
3.2 多记录项动态网页的信息抽取
根据前文所述
动态网页主要分为两种类型
多记录项动态网页 单记录项动态网页
其中多记录项动态网页是指一个动态网页中包含多个结构重复的记录
项
本节所提出的基于树模型的动态网页信息抽取算法Data Extraction base on Tree Model
态网页的信息抽取
树编辑距离
可以更准确的
并对重复
并
主要针对第一类
DETM
算法
也就是多记录项动
DETM 算法充分利用了HTML 的树型结构运用树编辑距离 (Tree Edit Distance) 模型和树归并(Tree Align)
算法来定位和抽取网页信息模型利用了网页的树结构特点
系统中的Align
算法思想
相比传统的字符串编辑距离
描述HTML 的结构抽取的结构也更为准确树归并算法借鉴了Roadrunner
并将它运用到多数据项的模式抽取上
实验表明
数据项和可选数据项作了更好的控制
且在不需要用户参与的情况下
基于树模型的信息抽取算
它可以适合不同的领域
法对于多记录项动态网页有着良好的抽取效果
自动高效地抽取网页信息
3.2.1 算法总体框架
多记录项动态网页的信息抽取主要有两个步骤数据项的定位和抽取模式的生成本章提出的DETM 算法分别通过树编辑距离模型和Tree Align算
法来实现这两个主要的抽取步骤
DETM 方法的整个框架如图
3-3
图 3-3 DETM 方法框架
图 3-3 中的知识库包括了领域知识库和用户兴趣知识库过程的中间结果网站不同的包装器
包括初始动态网页
标签树和数据项树
询类型进行了分类存储
提供了一个强大的语料库
即动态网页转化为标签树
它们将抽取
按领域和用户查
抽取规则库记录了不同
用xml 文档格式进行存储结果数据库记录了所有用户
的历史查询请求和抽取结果1. 将初始的用户抽取请求
生成数据项树
图 3-3 中的虚线框部分表示了主要的三个抽取步骤2. 通过树编辑距离模型定位并分离网页中的数据项3. 利用Align 算法生成最终的包装器
以下分别对 图 3-3 的三个主要的抽取步骤进行详细说明3.2.2 标签树生成
并为每个数据项单独
标签树是针对HTML 文档生成目前Web 上的数据大部分是以HTML 的形式出现的HTML 文档由标签(TAG)和元素Element 组成HTML 标签确定了浏览器所显示文档元素的格式
大多数HTML 标签是成对出现的
它们分别用作开始标签和结束标签HTML 的结束标签与开始标签的唯一区
别是多了个斜杠
/文档中的第一个条目文档的标题
始和结束
HTML 标签放在尖括号里如 是位于HTML
为标明HTML 文档标题部分的起
同样
可以使用标签
是表头起始和结束标签是表行起始和结束标签
是表格内容起始和结束标签等3.2.2.1 标签树相关定义
一个HTML
文档的标签主要分为两类
和
EndTag
开始标签
StartTag
public static class StarTag extends HtmlElement { public String tagName;
public AttributeList attributeList; public boolean emptyTag = false; }
结束标签
EndTag
public static class EndTag extends HtmlElement { public String tagName; }
其中StartTag
不仅包含标签名
标签没有结束标签的标签具体的描述如下
一类同时包含开始和结束标签
另一类仅包含单个标签因此算法中针对开始和结束标签分别定义StartTag
具体的描述如下
tagName
同时包含标签属性列表
attributeList 和单个标签标志
emptyTag
如
,
等
由于HTML
的嵌套结构
这里的单个标签是指只有开始
因此需要定义标签集合来表示标签集的嵌套
标签集合TagBlock
public static class TagBlock extends HtmlElement { public StartTag startTag; public EndTag endTag; public ElementSequence body; }
public static class ElementSequence { protected Vector elements; }
一个标签集合TagBlock 同时包含开始标签用startTag, endTag和body
表示含一个Vector,
表示所有的标签子集它的endTag 是
它的startTag 是
结束标签和标签子集
分别包
这里的body 是ElementSequence
类型
一棵标签树在系统中表示为一个
TagBlock
3.2.2.2 标签树生成算法
利用HTML 的TAG
的特征Web
文档结构树记之间
采用标记匹配和回溯相结合的方法构造
在起始标记和结束标
如
在起始标记之间的width ="33% " >
是属性信息名
是网页的内容信息在构造网页标签树时忽略属性描述信息因此只
需对部分TAG 标记进行分析通常需要考虑的HTML 标记主要有, ,
,,
,
|
和用于显示 HTML 文档由标题和主体两部分组成标题部分包含 主题部分包含文档的内容可以使用标签和 和 标明文档主体部分的开始和结束WEB 页面的标题 是表格起始和结束标签 |
||
|---|---|---|
|
姓 大多数HTML 标记是成对出现的 包括网页描述属性信息和网页内容信息 姓名 |
和结束标记 |
,,,,, 对于其它的HTML 标记可视为无用HTML 标记在程序处理中将忽略对这些标记的处理网页标签树的每个结点对应一个 Tag 标签因
此构建标签树的前提条件是正确地读取标记
有得到匹配的标记
DETM
生成标签树采用的算法是1. 顺次浏览Web 文档 2. 去除一些无用的标签
分析开始标记结束标记和没
3. 补齐缺少结束标签的标签 4. 生成Html
标签树 注释标签
等修饰字体的标签
标签
整个标签树生成算法的时间复杂度是O(n),其中n
是整个文档的长度3.2.3 记录项的定位和抽取
多于多记录项的动态网页记录项的定位通常来说有两个步骤一是找
到包含网页记录项的那部分信息块HTML
代码
在DETM
中有很高的准确率
也就是包含网页主要信息的那部分
二是将每个单独的记录从网页信息块中分离出来
其中无用的标签是指
采用启发是规则来首先初步定位动态网页中的网页信息对于记录项的分离
DETM 采用数模型中的树编辑距离来
从而分离出每个不同的记录项
它能较好
块
这类启发是规则是通过观察大量的多记录项动态网页的特征后总结得出
定量的表示出网页记录项之间的相似度
对于记录项信息的抽取
DETM 采用Tree Align算法来实现
的通过网页记录项子树之间的匹配来抽取记录项信息
以下章节将对这些步骤进行详细的描述3.2.3.1 树编辑距离
网页结构可以看成是一个树形结构因此如果需要从一个网页中找出
结构相似的记录项
的描述
就需要对同一个网页
不同子树之间的差异有一个定量
树A 和树B 的树编辑
在本算法中指定删
树编辑距离较好的定量反映了不同子树之间的差异
树编辑距离的定义类似于字符串编辑距离定义除
插入和替换
距离即为由A 通过最少的操作转化为B 的代价这里的操作指的是节点的删
可以为每个操作分别指定相应的权值
替换的权值为
1.5映射的定义如下
除和插入的权值为
1
要计算两棵树之间的树编辑距离通常的做法是找到两棵树之间权值最小的一个映射
(mapping)
假定X 是一棵树X[i]是树X 中第i 个子节点则树T1和树T2之间的映射M 是满足以下条件的有序数对 (i,j) 的集合
对于任何(a1,b2),(a2,b2) 1. a1=a2当且仅当 b1=b2
2. T1[a1]是T1[a2]的左邻节点当且仅当T2[b1]是T2[b2]的左邻节点 3. T1[a1]是T1[a2]的父节点当且仅当T2[b1]是T2[b2]的父节点
第一条定义保证每个节点在映射中都不会重复出现射后仍然保持原来相邻节点的前后顺序原来父子节点的层次顺序
有了映射
设两棵树T1, 和T2之第二条定义保证映
第三条定义保证了映射后仍然保持
就可以计算两棵树之间的树编辑距离
间的映射为M 在M 包含的数据对(a,b)中其中a,b 分别表示T1, 和T2的标签令S 表示a 和b 不相同的数据对数量即需要替换的标签D 表示T1 中没出现在M
中的节点
点
即需要插入的标签
即需要删除的标签
I 表示T2中没出现在M 中的节
则树编辑距离Dis(T1T2)
可以由以下公式得出
Dis (T
1
, T 2) =Sp
+Iq +Dr
其中p,q,r 分别表示替换
有很多种计算树编辑距离的算法
[23]中
提出的
一种算
法
algorithm 串
射
它们各有不同的侧重点
DETM 采用
它是一种动态规划算法
dynamic programming
算法通过一个递
插入和删除的权值
它将树的每个内部节点都对应一个由它们子节点标记组成的字符
得到两棵树之间拥有最小代价的一个映整个算法的复杂度为O(n1 n2 h1 h2) 其中
并将树之间的编辑距离转化为字符串之间的编辑距离继而求出它们的树编辑距离
归计算节点字符串最优匹配的过程
n 是表示网页标记树的总节点数h 是表示树的高度一般n 不会超过300 去除了无用的标签后
h 不会超过30
3.2.3.2 数据项定位和分离
图 3-4 网页标签树
由于整个网页是一颗标签树
据项
因此每个数据项就对应一颗数据项子树
图 3-4 是一个网页标签树的主要部分两个虚线框分别对应网页中的两个数
它们所对应的数据项子树就是以TBODY 为根节点并包括虚线框内所
定位数据项就是要找出所有的数据项子树
由于数据项结构的相关性
为下一步
它们所对应的
有标签项的一颗子树
生成包装器和信息抽取做好准备
数据项子树之间的必然有很大的相似性子树之间的相似度Sim(T1T 2)
作如下定义
通过上述的树编辑距离模型可以对
Size(Ti)表示子树的大小
其中Dis(T1
T 2)
表示两棵子树的树编辑距离
即为子树包含的标签总数
从相似性的定义可以看出Sim(T1
T 2) 的值在
0至1
之间值越大相似性越高在DETM 中定义相似度大于0.75的子树为相似子树
所包含的子树的数量通常也很大
因此不可
由于标签树的结构可能很复杂
通过对多类动态网页的观察则
并且数据项之间的标签结构高度相
似
能对标签树所有的子树集合均做出比较
为数据项定位算法定义以下三个启发式规
数据项的分布是在一个连续的区域
数据项分布在同一个父节点之下
项
数
它们都对应同一个父节点
如上图中
两个虚线框表示两个数据
既拥有较多的孩子节点
初步定位数据项
TBODY
数据项父节点在整个标签树中拥有较大的扇出
基于这三点启发式规则
1. 构造标签树
2.
按节点的扇区数目排序
区域的公共父节点定位数据项合
生成数据项子树
定位数据项的算法如下
找出拥有最大扇区数的节点
3.
对公共父节点下的一级子节点进行组合
找出覆盖面最广的相似子树
这里的覆盖面指的公共父节点下所有相似子树的标签集
4.
分离所有数据项
3.2.3.3 Tree Align算法
在这一模块中
可选项的问题
单个节点
重复节点
可选节点
. +?
将生成用于抽取的包装器树
包装器树与数据项树不同
之处在于它对每个节点增加了节点类型
仅出现一次的节点
以此解决网页数据项中的重复项和
包装器树的节点有以下四种类型 出现一次或多次的节点 出现0次或一次的节点 *
出现0次或多次的节点
可选重复节点
Tree Align算法在生成包装器树的过程中借鉴了RoadRunner 系统中ALIGN 算法的一些主要思想算法的输入是一个数据项树的集合它是由上
一过程生成
输出是一颗包装器树
包装器树初始化为输入的树集合中节点
算法每次比较包装器树和集合中一
然后再利用新的包装器树和另一颗数
数最少的数据项树
据项树进行比较装器树
行处理
同
不匹配
并附上了节点类型
颗数据项树并生成一颗新的包装器树
即最终的抽取器
直至集合中所有的数据项树全部比较完成后生成最终的包
利用先序遍历对两颗树进
如果节点不相
对于这两者类型的
在对包装器树和数据项树进行比较的过程中
如果两颗树的节点相同
分别对应一下的处理方法则有两种情况
1.
字符串不匹配
则进行下一个节点的处理
2.
标签项不匹配
字符串不匹配
在同一网页对数据项中字符串的不匹配通常是由同一
则可以认
数据库字段不同数值造成的
因此如果出现字符串的不匹配
为该处对应着数据库中的同一字段趣的内容
对应的处理方式为将包装器树的对
应位置标示为#PCDATA,表示该处为一个信息字段也就是通常用户感兴
标签项不匹配
标签项不匹配是指包装器树和数据项树之间的标签与标
出现这种情况的原因可能有两种
算法在出现标签项不匹配时首
则在包装器树中将该节点对应的
如
二是出现了重复项
如果是
签不匹配或者标签与数据项不匹配
一是出现了可选项
先判断是否是重复的数据项
果不是
可选节点树
则该节点是可选节点
类型设为重复节点或可选重复节点
如果节点类型原本为可选节点
在包装器树中将该节点对应的类型设为
将生成最终用于抽取的包装器
当处理完数据项集合中所有数据项树时实现自动的信息抽取
根据最终的包装器树可以很方便的确定此类数据型网页的数据项模式并
3.3 单记录项动态网页的信息抽取
3.3.1 单记录项网页信息抽取算法和功能描述 3.3.1.1 单记录项网页描述
单记录项动态网页是指一个网页上仅包含一组相关数据项这一类动态
网页信息的抽取通常需要基于用户的交互来生成信息抽取的模板一个或多个网页很难定位和确定所需要抽取的信息项
上节中的 图 3-2
就是一个典型的单记录项网页的数据项有多个
因为单从
这个网页所包含的记录项只有一个就是有关童献平的个人信息具体
包括
姓名 性别 年龄 民族 学历 手机
用户记录项部分的HTML
代码如下
| , |
|---|
| , |
|
姓名 性别 童献平 男 出生于一个难忘的岁月 民族 学历 汉 硕士 手机 None |
3.3.1.2 抽取模板描述
经过抽取系统的初步过滤
名
据项
性别
年龄
民族
性别和学历
则抽取系统将根据用户选择生成
电话
将会罗列出可供选择的信息数据项学历等
包括姓
用户可以选在全部或其中的部分数
用来从其他网页中抽
系统将根据用户所选择的数据项生成抽取模板
取用户需要的信息项如下的抽取模板
假定用户选择的是姓名
+
+
|
姓名 性别 学历 |
+
用户模板使用XML 文档表示如
DOM
XSLT
等
由于XML 文档的结构化特征它能够较
好的表现出HTML 文档的树型结构此外XML
有很多比较成熟的查询技术
用户模板使用XML 文档表示可以较方便的使用这些技
抽取姓名
术进行信息抽取和信息的存储
对于上例
针对用户的抽取选择
性别和学历系统将生
成如上模板模板中包含HTML 代码中的部分标签也就是说仅保留对模板定义有作用的HTML 标签如何定义对于模板有作用的标签将在后续章节中
详细描述
这也是模板生成中的核心部分
通常为信息的标
在
另外用户在定义抽取信息外同时可以自定义描述信息题或其他标识性的信息上述模板文档中
3.3.1.3 抽取结果表示
网页抽取结果同模板一样录项网页
取模板
同样使用XML
表示
对于一个普通的单记
对于单记录项
姓名
性别
这些信息将在XML 模板中以Text
的形式出现
学历即为用户自定义的描述信息
系统将使用模板匹配的方法首先从模板库中确定最为适合的抽
因为用户的自定义
然后使用上文所述的Tree Align
算法进行信息抽取
网页的Tree Align将比多记录项的Tree Align
简单的多模板确定了信息的表现形式和信息的结构
根据上述模板
姓名 性别 学历
则根据Tree Align
算法
需要信息抽取的项有
抽取的结果如下
董献平 男 硕士
如上所示抽取的结果包括模板中的三部分信息即姓名
性别和学历结果使用XML
表示可以十分方便的用于其他抽取系统或其他信息挖掘系统
并为之提供结构良好的语料和附加的描述信息
因为XML 有HTML 所无法比拟的自定义Tag
3.3.2 自定义模板生成技术 3.3.2.1 模板抽取算法
模板是单记录项网页抽取的核心项网页的抽取效果和抽取精度
转换为可供抽取系统使用的抽取模板
模板的正确与否将直接影响到单记录
模板生成算法总的框架如下
模板生成算法的目的就是如何将用户的选择
图
3-5 模板生成算法
初始的抽取请求为包含单个记录项的动态网页也就是HTML 算法首
先将会把网页转换为标签树户自定义模板
然后通过用户的选择生成XML
表现形式的用
然后对于需要信息抽取的并将结果保存在知识库中作
生成的模板将会保存在模板库中
动态网页算法将从模板库中找出最为匹配的模板这一过程称为模板匹配
最后算法将通过匹配出的模板进行信息的抽取为结果信息或其他抽取系统的预料
模板抽取算法的步骤如下2. 如果是样例网页3. 过滤网页信息
则转3
如果是需要抽取的网页则转5
1. 将初始的抽取网页转换为标签树
生成供用户选择的网页信息记录项
确定用来抽取的模板
4. 根据用户的选择生成抽取模板 5. 从模板库中进行模板匹配6. 使用模板进行信息抽取 7. 导出信息至XML 文档
3.4 小结
本章首先描述了动态网页的分类定义
记录项动态网页和单记录项动态网页的类别
模型和算法法
本章描述了一种基于树模型的动态网页信息抽取算
它充分利用HTML
将动态网页分为两个类别
即多
这两种类别基本涵盖了所有动态网页
分别提出了两种信息抽取的
随后针对这两种不同的动态网页类型
对于多记录项网页的树型结构
DETM 算法
Data Extraction base on Tree Model
运用树编辑距离 (Tree Edit Distance)模型和树归并(Tree Align)
本章描述了一种基于用户自定义模板的信息抽取算
算法来定位和抽取网页信息
对于单记录项网页法模板
较困难这个难题
它利用模板自动生成技术较好的解决了单记录项动态网页信息项定位比
将单记录项动态网页的结构通过XML 文档的形式转化为
从而可以将树匹配的一些算法模型应用到抽取模型中
第3章 动态网页信息抽取算法与模型
3.1 动态网页的类型与特点
据统计
WWW 上有80%的Web
页面是动态网页
例如搜索引擎返回的搜索结果
它们通常是由网站
动
网上商店的商品信
的后台数据库通过某种通用的模板构成
态网页的类型十分广泛
义
息页面都是典型的动态网页
因此具有十分相似的页面结构
如何从动态网页中抽取信息有着十分重要的意
因为它们通常是一个网站最为主要的信息来源动态网页按照信息项的分布主要分为两个类型
多记录动态网页 单记录动态网页
1
多记录动态网页
多记录是指一个动态网页中包含多个结构重复的记录项这个类型是动
态网页的主要信息表示类型
因为一个信息项的数据量往往很小
所以同一
个动态网页中通常包含超过10个甚至50
个的记录项结果就是多记录动态网页的一个典型例子中只包含了其中的4
项似性
例如搜索引擎的返回
图 3-1 是百度搜索引擎的返回结果网页网页中包含了10个信息项图
这10个信息项在结构和信息内容上都有很大的相
因此对于这类动态网页的抽取主要问题在于如何定为这些结构相似的
多记录项动态网页的另一个典型例子就是包含表格信息项的动态网页这里的表格信息并不等同于数据库中的表格
而是指包含表格形态的数据项
记录项以及如何提取这些信息项的共同的结构
图 3-1 百度搜索引擎结果
2 单记录项动态网页
动态网页中除了多记录项动态网页之外还有很大一部分动态网页仅包
含一个单一的记录项
这类网页通常出现在一些用于描述详细信息的场合中例如个人详细信息产品信息论文信息等图 3-2 是一个典型的单记录项动态网页该动态网页仅包含一个信息项包括姓名性别学历
电话
兴趣爱好等
这类动态网页信息抽取的难度比较高
因为记录项在结构上没
对于这类
随后在
也就是所谓
有单记录项动态网页所具有的相似性
动态网页的抽取
的自定义模板
模板的基础上定位并抽取信息项
因此很难准确定位记录项
通常需要在样例网页的基础上首先生成抽取模板
这一步往往需要用户自定义
如何从网页中正确的抽取出这些信息数据
如何定位这些数
据以及如何生成抽取信息的模板式这类动态网页信息抽取的难点
图 3-2 单记录项动态网页
3.2 多记录项动态网页的信息抽取
根据前文所述
动态网页主要分为两种类型
多记录项动态网页 单记录项动态网页
其中多记录项动态网页是指一个动态网页中包含多个结构重复的记录
项
本节所提出的基于树模型的动态网页信息抽取算法Data Extraction base on Tree Model
态网页的信息抽取
树编辑距离
可以更准确的
并对重复
并
主要针对第一类
DETM
算法
也就是多记录项动
DETM 算法充分利用了HTML 的树型结构运用树编辑距离 (Tree Edit Distance) 模型和树归并(Tree Align)
算法来定位和抽取网页信息模型利用了网页的树结构特点
系统中的Align
算法思想
相比传统的字符串编辑距离
描述HTML 的结构抽取的结构也更为准确树归并算法借鉴了Roadrunner
并将它运用到多数据项的模式抽取上
实验表明
数据项和可选数据项作了更好的控制
且在不需要用户参与的情况下
基于树模型的信息抽取算
它可以适合不同的领域
法对于多记录项动态网页有着良好的抽取效果
自动高效地抽取网页信息
3.2.1 算法总体框架
多记录项动态网页的信息抽取主要有两个步骤数据项的定位和抽取模式的生成本章提出的DETM 算法分别通过树编辑距离模型和Tree Align算
法来实现这两个主要的抽取步骤
DETM 方法的整个框架如图
3-3
图 3-3 DETM 方法框架
图 3-3 中的知识库包括了领域知识库和用户兴趣知识库过程的中间结果网站不同的包装器
包括初始动态网页
标签树和数据项树
询类型进行了分类存储
提供了一个强大的语料库
即动态网页转化为标签树
它们将抽取
按领域和用户查
抽取规则库记录了不同
用xml 文档格式进行存储结果数据库记录了所有用户
的历史查询请求和抽取结果1. 将初始的用户抽取请求
生成数据项树
图 3-3 中的虚线框部分表示了主要的三个抽取步骤2. 通过树编辑距离模型定位并分离网页中的数据项3. 利用Align 算法生成最终的包装器
以下分别对 图 3-3 的三个主要的抽取步骤进行详细说明3.2.2 标签树生成
并为每个数据项单独
标签树是针对HTML 文档生成目前Web 上的数据大部分是以HTML 的形式出现的HTML 文档由标签(TAG)和元素Element 组成HTML 标签确定了浏览器所显示文档元素的格式
大多数HTML 标签是成对出现的
它们分别用作开始标签和结束标签HTML 的结束标签与开始标签的唯一区
别是多了个斜杠
/文档中的第一个条目文档的标题
始和结束
HTML 标签放在尖括号里如 是位于HTML
为标明HTML 文档标题部分的起
同样
可以使用标签
是表头起始和结束标签是表行起始和结束标签
是表格内容起始和结束标签等3.2.2.1 标签树相关定义
一个HTML
文档的标签主要分为两类
和
EndTag
开始标签
StartTag
public static class StarTag extends HtmlElement { public String tagName;
public AttributeList attributeList; public boolean emptyTag = false; }
结束标签
EndTag
public static class EndTag extends HtmlElement { public String tagName; }
其中StartTag
不仅包含标签名
标签没有结束标签的标签具体的描述如下
一类同时包含开始和结束标签
另一类仅包含单个标签因此算法中针对开始和结束标签分别定义StartTag
具体的描述如下
tagName
同时包含标签属性列表
attributeList 和单个标签标志
emptyTag
如
,
等
由于HTML
的嵌套结构
这里的单个标签是指只有开始
因此需要定义标签集合来表示标签集的嵌套
标签集合TagBlock
public static class TagBlock extends HtmlElement { public StartTag startTag; public EndTag endTag; public ElementSequence body; }
public static class ElementSequence { protected Vector elements; }
一个标签集合TagBlock 同时包含开始标签用startTag, endTag和body
表示含一个Vector,
表示所有的标签子集它的endTag 是
它的startTag 是
结束标签和标签子集
分别包
这里的body 是ElementSequence
类型
一棵标签树在系统中表示为一个
TagBlock
3.2.2.2 标签树生成算法
利用HTML 的TAG
的特征Web
文档结构树记之间
采用标记匹配和回溯相结合的方法构造
在起始标记和结束标
如
在起始标记之间的width ="33% " >
是属性信息名
是网页的内容信息在构造网页标签树时忽略属性描述信息因此只
需对部分TAG 标记进行分析通常需要考虑的HTML 标记主要有, ,
,,
,
|
和用于显示 HTML 文档由标题和主体两部分组成标题部分包含 主题部分包含文档的内容可以使用标签和 和 标明文档主体部分的开始和结束WEB 页面的标题 是表格起始和结束标签 |
||
|---|---|---|
|
姓 大多数HTML 标记是成对出现的 包括网页描述属性信息和网页内容信息 姓名 |
和结束标记 |
,,,,, 对于其它的HTML 标记可视为无用HTML 标记在程序处理中将忽略对这些标记的处理网页标签树的每个结点对应一个 Tag 标签因
此构建标签树的前提条件是正确地读取标记
有得到匹配的标记
DETM
生成标签树采用的算法是1. 顺次浏览Web 文档 2. 去除一些无用的标签
分析开始标记结束标记和没
3. 补齐缺少结束标签的标签 4. 生成Html
标签树 注释标签
等修饰字体的标签
标签
整个标签树生成算法的时间复杂度是O(n),其中n
是整个文档的长度3.2.3 记录项的定位和抽取
多于多记录项的动态网页记录项的定位通常来说有两个步骤一是找
到包含网页记录项的那部分信息块HTML
代码
在DETM
中有很高的准确率
也就是包含网页主要信息的那部分
二是将每个单独的记录从网页信息块中分离出来
其中无用的标签是指
采用启发是规则来首先初步定位动态网页中的网页信息对于记录项的分离
DETM 采用数模型中的树编辑距离来
从而分离出每个不同的记录项
它能较好
块
这类启发是规则是通过观察大量的多记录项动态网页的特征后总结得出
定量的表示出网页记录项之间的相似度
对于记录项信息的抽取
DETM 采用Tree Align算法来实现
的通过网页记录项子树之间的匹配来抽取记录项信息
以下章节将对这些步骤进行详细的描述3.2.3.1 树编辑距离
网页结构可以看成是一个树形结构因此如果需要从一个网页中找出
结构相似的记录项
的描述
就需要对同一个网页
不同子树之间的差异有一个定量
树A 和树B 的树编辑
在本算法中指定删
树编辑距离较好的定量反映了不同子树之间的差异
树编辑距离的定义类似于字符串编辑距离定义除
插入和替换
距离即为由A 通过最少的操作转化为B 的代价这里的操作指的是节点的删
可以为每个操作分别指定相应的权值
替换的权值为
1.5映射的定义如下
除和插入的权值为
1
要计算两棵树之间的树编辑距离通常的做法是找到两棵树之间权值最小的一个映射
(mapping)
假定X 是一棵树X[i]是树X 中第i 个子节点则树T1和树T2之间的映射M 是满足以下条件的有序数对 (i,j) 的集合
对于任何(a1,b2),(a2,b2) 1. a1=a2当且仅当 b1=b2
2. T1[a1]是T1[a2]的左邻节点当且仅当T2[b1]是T2[b2]的左邻节点 3. T1[a1]是T1[a2]的父节点当且仅当T2[b1]是T2[b2]的父节点
第一条定义保证每个节点在映射中都不会重复出现射后仍然保持原来相邻节点的前后顺序原来父子节点的层次顺序
有了映射
设两棵树T1, 和T2之第二条定义保证映
第三条定义保证了映射后仍然保持
就可以计算两棵树之间的树编辑距离
间的映射为M 在M 包含的数据对(a,b)中其中a,b 分别表示T1, 和T2的标签令S 表示a 和b 不相同的数据对数量即需要替换的标签D 表示T1 中没出现在M
中的节点
点
即需要插入的标签
即需要删除的标签
I 表示T2中没出现在M 中的节
则树编辑距离Dis(T1T2)
可以由以下公式得出
Dis (T
1
, T 2) =Sp
+Iq +Dr
其中p,q,r 分别表示替换
有很多种计算树编辑距离的算法
[23]中
提出的
一种算
法
algorithm 串
射
它们各有不同的侧重点
DETM 采用
它是一种动态规划算法
dynamic programming
算法通过一个递
插入和删除的权值
它将树的每个内部节点都对应一个由它们子节点标记组成的字符
得到两棵树之间拥有最小代价的一个映整个算法的复杂度为O(n1 n2 h1 h2) 其中
并将树之间的编辑距离转化为字符串之间的编辑距离继而求出它们的树编辑距离
归计算节点字符串最优匹配的过程
n 是表示网页标记树的总节点数h 是表示树的高度一般n 不会超过300 去除了无用的标签后
h 不会超过30
3.2.3.2 数据项定位和分离
图 3-4 网页标签树
由于整个网页是一颗标签树
据项
因此每个数据项就对应一颗数据项子树
图 3-4 是一个网页标签树的主要部分两个虚线框分别对应网页中的两个数
它们所对应的数据项子树就是以TBODY 为根节点并包括虚线框内所
定位数据项就是要找出所有的数据项子树
由于数据项结构的相关性
为下一步
它们所对应的
有标签项的一颗子树
生成包装器和信息抽取做好准备
数据项子树之间的必然有很大的相似性子树之间的相似度Sim(T1T 2)
作如下定义
通过上述的树编辑距离模型可以对
Size(Ti)表示子树的大小
其中Dis(T1
T 2)
表示两棵子树的树编辑距离
即为子树包含的标签总数
从相似性的定义可以看出Sim(T1
T 2) 的值在
0至1
之间值越大相似性越高在DETM 中定义相似度大于0.75的子树为相似子树
所包含的子树的数量通常也很大
因此不可
由于标签树的结构可能很复杂
通过对多类动态网页的观察则
并且数据项之间的标签结构高度相
似
能对标签树所有的子树集合均做出比较
为数据项定位算法定义以下三个启发式规
数据项的分布是在一个连续的区域
数据项分布在同一个父节点之下
项
数
它们都对应同一个父节点
如上图中
两个虚线框表示两个数据
既拥有较多的孩子节点
初步定位数据项
TBODY
数据项父节点在整个标签树中拥有较大的扇出
基于这三点启发式规则
1. 构造标签树
2.
按节点的扇区数目排序
区域的公共父节点定位数据项合
生成数据项子树
定位数据项的算法如下
找出拥有最大扇区数的节点
3.
对公共父节点下的一级子节点进行组合
找出覆盖面最广的相似子树
这里的覆盖面指的公共父节点下所有相似子树的标签集
4.
分离所有数据项
3.2.3.3 Tree Align算法
在这一模块中
可选项的问题
单个节点
重复节点
可选节点
. +?
将生成用于抽取的包装器树
包装器树与数据项树不同
之处在于它对每个节点增加了节点类型
仅出现一次的节点
以此解决网页数据项中的重复项和
包装器树的节点有以下四种类型 出现一次或多次的节点 出现0次或一次的节点 *
出现0次或多次的节点
可选重复节点
Tree Align算法在生成包装器树的过程中借鉴了RoadRunner 系统中ALIGN 算法的一些主要思想算法的输入是一个数据项树的集合它是由上
一过程生成
输出是一颗包装器树
包装器树初始化为输入的树集合中节点
算法每次比较包装器树和集合中一
然后再利用新的包装器树和另一颗数
数最少的数据项树
据项树进行比较装器树
行处理
同
不匹配
并附上了节点类型
颗数据项树并生成一颗新的包装器树
即最终的抽取器
直至集合中所有的数据项树全部比较完成后生成最终的包
利用先序遍历对两颗树进
如果节点不相
对于这两者类型的
在对包装器树和数据项树进行比较的过程中
如果两颗树的节点相同
分别对应一下的处理方法则有两种情况
1.
字符串不匹配
则进行下一个节点的处理
2.
标签项不匹配
字符串不匹配
在同一网页对数据项中字符串的不匹配通常是由同一
则可以认
数据库字段不同数值造成的
因此如果出现字符串的不匹配
为该处对应着数据库中的同一字段趣的内容
对应的处理方式为将包装器树的对
应位置标示为#PCDATA,表示该处为一个信息字段也就是通常用户感兴
标签项不匹配
标签项不匹配是指包装器树和数据项树之间的标签与标
出现这种情况的原因可能有两种
算法在出现标签项不匹配时首
则在包装器树中将该节点对应的
如
二是出现了重复项
如果是
签不匹配或者标签与数据项不匹配
一是出现了可选项
先判断是否是重复的数据项
果不是
可选节点树
则该节点是可选节点
类型设为重复节点或可选重复节点
如果节点类型原本为可选节点
在包装器树中将该节点对应的类型设为
将生成最终用于抽取的包装器
当处理完数据项集合中所有数据项树时实现自动的信息抽取
根据最终的包装器树可以很方便的确定此类数据型网页的数据项模式并
3.3 单记录项动态网页的信息抽取
3.3.1 单记录项网页信息抽取算法和功能描述 3.3.1.1 单记录项网页描述
单记录项动态网页是指一个网页上仅包含一组相关数据项这一类动态
网页信息的抽取通常需要基于用户的交互来生成信息抽取的模板一个或多个网页很难定位和确定所需要抽取的信息项
上节中的 图 3-2
就是一个典型的单记录项网页的数据项有多个
因为单从
这个网页所包含的记录项只有一个就是有关童献平的个人信息具体
包括
姓名 性别 年龄 民族 学历 手机
用户记录项部分的HTML
代码如下
| , |
|---|
| , |
|
姓名 性别 童献平 男 出生于一个难忘的岁月 民族 学历 汉 硕士 手机 None |
3.3.1.2 抽取模板描述
经过抽取系统的初步过滤
名
据项
性别
年龄
民族
性别和学历
则抽取系统将根据用户选择生成
电话
将会罗列出可供选择的信息数据项学历等
包括姓
用户可以选在全部或其中的部分数
用来从其他网页中抽
系统将根据用户所选择的数据项生成抽取模板
取用户需要的信息项如下的抽取模板
假定用户选择的是姓名
+
+
|
姓名 性别 学历 |
+
用户模板使用XML 文档表示如
DOM
XSLT
等
由于XML 文档的结构化特征它能够较
好的表现出HTML 文档的树型结构此外XML
有很多比较成熟的查询技术
用户模板使用XML 文档表示可以较方便的使用这些技
抽取姓名
术进行信息抽取和信息的存储
对于上例
针对用户的抽取选择
性别和学历系统将生
成如上模板模板中包含HTML 代码中的部分标签也就是说仅保留对模板定义有作用的HTML 标签如何定义对于模板有作用的标签将在后续章节中
详细描述
这也是模板生成中的核心部分
通常为信息的标
在
另外用户在定义抽取信息外同时可以自定义描述信息题或其他标识性的信息上述模板文档中
3.3.1.3 抽取结果表示
网页抽取结果同模板一样录项网页
取模板
同样使用XML
表示
对于一个普通的单记
对于单记录项
姓名
性别
这些信息将在XML 模板中以Text
的形式出现
学历即为用户自定义的描述信息
系统将使用模板匹配的方法首先从模板库中确定最为适合的抽
因为用户的自定义
然后使用上文所述的Tree Align
算法进行信息抽取
网页的Tree Align将比多记录项的Tree Align
简单的多模板确定了信息的表现形式和信息的结构
根据上述模板
姓名 性别 学历
则根据Tree Align
算法
需要信息抽取的项有
抽取的结果如下
董献平 男 硕士
如上所示抽取的结果包括模板中的三部分信息即姓名
性别和学历结果使用XML
表示可以十分方便的用于其他抽取系统或其他信息挖掘系统
并为之提供结构良好的语料和附加的描述信息
因为XML 有HTML 所无法比拟的自定义Tag
3.3.2 自定义模板生成技术 3.3.2.1 模板抽取算法
模板是单记录项网页抽取的核心项网页的抽取效果和抽取精度
转换为可供抽取系统使用的抽取模板
模板的正确与否将直接影响到单记录
模板生成算法总的框架如下
模板生成算法的目的就是如何将用户的选择
图
3-5 模板生成算法
初始的抽取请求为包含单个记录项的动态网页也就是HTML 算法首
先将会把网页转换为标签树户自定义模板
然后通过用户的选择生成XML
表现形式的用
然后对于需要信息抽取的并将结果保存在知识库中作
生成的模板将会保存在模板库中
动态网页算法将从模板库中找出最为匹配的模板这一过程称为模板匹配
最后算法将通过匹配出的模板进行信息的抽取为结果信息或其他抽取系统的预料
模板抽取算法的步骤如下2. 如果是样例网页3. 过滤网页信息
则转3
如果是需要抽取的网页则转5
1. 将初始的抽取网页转换为标签树
生成供用户选择的网页信息记录项
确定用来抽取的模板
4. 根据用户的选择生成抽取模板 5. 从模板库中进行模板匹配6. 使用模板进行信息抽取 7. 导出信息至XML 文档
3.4 小结
本章首先描述了动态网页的分类定义
记录项动态网页和单记录项动态网页的类别
模型和算法法
本章描述了一种基于树模型的动态网页信息抽取算
它充分利用HTML
将动态网页分为两个类别
即多
这两种类别基本涵盖了所有动态网页
分别提出了两种信息抽取的
随后针对这两种不同的动态网页类型
对于多记录项网页的树型结构
DETM 算法
Data Extraction base on Tree Model
运用树编辑距离 (Tree Edit Distance)模型和树归并(Tree Align)
本章描述了一种基于用户自定义模板的信息抽取算
算法来定位和抽取网页信息
对于单记录项网页法模板
较困难这个难题
它利用模板自动生成技术较好的解决了单记录项动态网页信息项定位比
将单记录项动态网页的结构通过XML 文档的形式转化为
从而可以将树匹配的一些算法模型应用到抽取模型中