太阳城集团

  • / 12
  • 下载费用:30 金币  

一种基于结构识别的WEB表格太阳城集团抽取方法.pdf

摘要
申请专利号:

太阳城集团CN201510287215.0

申请日:

2015.06.01

公开号:

太阳城集团CN105045769A

公开日:

2015.11.11

当前法律状态:

撤回

有效性:

无权

法律详情: 发明专利申请公布后的视为撤回IPC(主分类):G06F 17/22申请公布日:20151111|||实质审查的生效IPC(主分类):G06F 17/22申请日:20150601|||公开
IPC分类号: G06F17/22 主分类号: G06F17/22
申请人: 中国人民解放军装备学院
发明人: 刘东; 朱鸿乔; 李新明; 邢维艳; 李艺; 李亢; 王寿彪; 饶磊; 闫雪飞; 于少波; 李强
地址: 101416北京市怀柔区3380信箱
优先权:
专利代理机构: 中国人民解放军防化研究院专利服务中心11046 代理人: 刘永盛
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201510287215.0

授权太阳城集团号:

||||||

法律状态太阳城集团日:

2018.04.10|||2015.12.09|||2015.11.11

法律状态类型:

发明专利申请公布后的视为撤回|||实质审查的生效|||公开

摘要

太阳城集团本发明涉及一种基于结构识别的Web表格太阳城集团抽取方法。在该方法过程中,表格结构的识别采用了两种渐进式的方法进行。首先采用了一组启发式的规则对常见的几种类型的表格进行结构的判断,从而确定了Web中较大一部分表格的结构类型;对通过启发式规则未能识别的表格,采用字符串匹配的方式进行,被匹配的单元格被限定在ULC(upper-left-cell)所在的行或列中,这样就可以大大减少需要进行字符串匹配的内容,提高了匹配和识别的效率。最后,从总的两个维度的表格出发,分别提出了在太阳城集团抽取过程中合成单元格的处理策略问题,可以在保证抽取结果中数据间的关系不被破坏的基础上,尽可能的降低冗余数据的产生。

权利要求书

1.一种基于结构识别的Web表格太阳城集团抽取方法,其特征是该方法步骤如下:
首先通过启发式规则对表格的结构进行识别,启发式规则为:①表格左上角的单元格的
英文名称为upper-left-cell,缩写为ULC,当该单元格中的内容为空时,表格为二维表格,当
该单元格中的内容不为空且表格中的内容存在属性-值关系时,ULC为属性单元格;②当表格
中由<th>标签构造的单元格的个数大于2且这些单元格位于表格中的同一行或同一列时,这
些单元格是表格的属性单元格;对于符合启发式规则的表格,当识别出的属性区域仅按行展
开,则表格为一维表格,当属性区域同时按行和按列展开,则表格为二维表格;
一维表格

二维表格

对于通过步骤1不能进行结构识别的表格,再根据表格中同一属性下的值在内容上具有
相似性这一特点,采用字符串编辑距离的方法对单元格中内容字符串间的相似度进行计算,
进而区分出表格中的属性单元格区域和值单元格区域;通过对50组不同属性下的属性值组进
行内容相似度的计算,得出同一属性下属性值间相似度的阈值为0.3;为了减少进行表格结构
识别时相似度计算的次数,根据步骤1中的启发式规则①和表格右下角单元格为值单元格这
一特点,仅对ULC和右下角单元格所在的行和列中的单元格进行内容相似度计算,当相似度
的值大于0.3,两个单元格中的值同属一个属性,反之则不属于;在进行相似度计算后,当识
别出的属性区域仅按行展开,则表格为一维表格,当属性区域同时按行和按列展开,则表格
为二维表格;
通过上述两步骤之后即可判定表格的结构类型,对于一维表格中横向展开的类型,当值
单元格C2的属性colspan的值大于其所在行中属性单元格C1的属性colspan的值,则将该值
单元格进行分割,得到的两个新的单元格的rowspan的值不变,colspan的值分别为C1.
colspan.value、C2.colspan.value-C1.colspan.value,否则不对该值单元格进行处理;对于一维
表格中纵向展开的类型,当值单元格C2的属性rowspan的值大于其所在列中属性单元格C1
的属性rowspan的值,则将该值单元格进行分割,得到的两个新的单元格colspan的值不变,
rowspan的值分别为C1.rowspan.value、C2.rowspan.value-C1.rowspan.value,否则不对该值单
元格进行处理;对于二维表格,包括ULC为空或不为空的两种情况,分别根据值单元格所在
行中的属性单元格的colspan的值和所在列中的单元格的rowspan的值对该值单元格进行分
割,分割的方法同一维表格的处理过程。

说明书

一种基于结构识别的Web表格太阳城集团抽取方法

技术领域

太阳城集团本发明属于Web太阳城集团抽取技术领域,可用于对Web文档中表格太阳城集团的抽取和存储,特别是对数据间关系难以理解的复杂Web表格的太阳城集团抽取问题具有较好的处理能力。

背景技术

太阳城集团抽取是数据挖掘领域的一个重要研究方向,海量存在的Web资源又使得面向Web的太阳城集团抽取成为当前该领域的研究热点。在形式各异的Web太阳城集团中,表格(Tables)是Web文档中一种重要的数据表现形式,通常用于组织所描述对象的基本太阳城集团、统计数据等。由于这些结构化的数据具有的较高的使用价值,因此进行表格数据抽取的研究具有重要的意义。然而,HTML标记语言主要用于对数据进行展示,不具有对数据进行描述的能力。Web表格结构往往体现着数据间的关系,这种结构的解读依赖于用户的理解,而应用程序则无法直接读懂这些太阳城集团。在将复杂结构的Web表格转化成面向存储的逻辑模型时,需要考虑单元格的类型、数据间的关联约束等问题。因此,如何解决这些问题来正确理解表格结构就成为对表格太阳城集团进行准确抽取的关键。

太阳城集团早在1996年,《GraphicsRecognitionMethodsandApplications》中的一篇文章《Model-basedanalysisofprintedtables》就曾对表头单元格、属性单元格和数据单元格进行了层次上的划分,并通过label标记的方法对不同逻辑层次的单元格进行了表示。但是该研究的对象仅限于出版物中的表格,这类规范化程度较高的表格和格式约束较少的Web表格存在较大差异。此外,文中提出的单元格层次的划分方法在实际的处理过程中难度较大,并不适合通过编程语言进行操作。在2001年PacificAssociationforComputationalLinguistics的论文集中,《ExtractionontologiesfromWorldWideWebviaHTMLtables》一文提出了一种基于字符串比对的表格结构识别方法,但是该方法没有充分利用表格自身的特点,并且进行结构识别时需要比对的字符串较多,这就对表格结构识别的效率造成了影响。第八届《Informationandknowledgemanagement》国际会议中的一篇文章《AnautomatedapproachforretrievinghierarchicaldatafromHTMLtables》介绍了两种类型的数据层次的概念,并提出了一种基于表格中数据层次关系的内容树(contenttree,CT)的构建方法。国内在Web表格太阳城集团抽取领域的研究也取得了一定的进展,合肥工业大学2012年度的一篇硕士学位论文《基于Web结构的表格太阳城集团抽取研究》提出了一种基于路径模式挖掘的Web表格太阳城集团抽取方法;而燕山大学2008年度的硕士学位论文《基于表格结构的Web太阳城集团提取技术研究》则提出了一种基于HTML结构树的列表太阳城集团提取方法。但是表格结构识别方面的研究大多集中在通过本体的方法进行,和国外的研究相比思路较为单一、方法的可操作性不强。表格的结构模型直接决定着太阳城集团的抽取策略,不仅要能体现原表格中数据间的关系,又要尽可能减少冗余数据的产生。其中涉及到的一个主要问题就是如何使表格更加规整化,即如何处理存在rowspan和colspan情况的单元格。目前采用的最主要的方法就是如Proceedingsofthe18thconferenceonComputationallinguistics-Volume1.AssociationforComputationalLinguistics中的一篇文章《MiningtablesfromlargescaleHTMLtexts》所介绍的“将单元格按照rowspan和colspan的值划分成相应数量的基本单元格,并将原单元格中的内容复制到这些单元格中”的方法。这种方法虽然能在一定程度上保留原数据间的关系,但是不可避免的会造成大量重复数据(冗余数据)的出现。

太阳城集团本发明从表格自身所隐含的规则出发,探寻一种简单、有效的表格结构识别方法,以便于对Web表格太阳城集团进行准确抽取;并通过对两种维度表格特征的分析提出新的、面向存储的值单元格处理方法,可以在一定程度上减少冗余数据的产生。

发明内容

太阳城集团本发明的目的是为了解决Web中表格太阳城集团的抽取问题,尤其是复杂表格的太阳城集团抽取策略。通常在对后者进行太阳城集团抽取时,数据间关系的难以理解会对抽取结果的准确性造成影响。

太阳城集团本发明的技术方案如下:

对于一个给定的Web表格,首先经过启发式规则对其结构特征进行判断。如果该Web表格的结构类型经过启发式规则未能被判断出,再通过字符串匹配的方法来区分属性单元格区域和值单元格区域,从而确定表格的结构类型。根据表格结构类型的判断结果,一维表格中的值单元格按照所对应的属性单元格的rowspan或colspan的值(属性单元格位于属性行中,则根据属性单元格的colspan.value();属性单元格位于属性列中,则根据属性单元格的rowspan.value())进行处理;二维表格中的值单元格按照其所对应的两个属性单元格的rowspan和colspan的值进行处理,两个属性单元格所需考虑的情况同一维表格的处理方式。表1和表2分别展示了一维表格和二维表格的实例。

表1一维表格实例

表2ULC为空的二维表格的实例

本发明的核心是:提出了一种快速判断Web表格结构的方法,并针对两种结构类型的表格制定了相应的抽取策略,该策略使得抽取结果在保证原有的数据间关系的基础上尽可能地减少存储时冗余数据的产生。

太阳城集团本发明的关键之一是:归纳出了快速识别Web表格结构的启发式规则。即当表格的左上角的单元格为空时,表格为二维表格。首先通过这一规则对Web表格的结构类型进行判断;在该规则未能适用的情况下,可根据<th>标签进行表格结构的识别。基于的规则为:如果表格中存在<th>标签构造的属性单元格,则该表格中所有的属性单元格均由<th>标签构造而成。

太阳城集团本发明的关键之二是:采用字符串编辑距离(EditDistance,也称为LevenshteinDistance)对单元格中内容字符串间的相似度进行计算。给出了通过多次实验得出的区分属性字符串和值字符串间相似度的阈值;需要进行相似度计算的单元格被限定在ULC(upper-left-cell,左上角的单元格)所在的行和列中。

太阳城集团本发明关键之三是:对一维表格(包括横向展开和纵向展开两种情况),按照属性单元格的cell.rowspan.value()或cell.colspan.value()对所在列或行中的值单元格进行切分。基于的考虑是,合成的值单元格的处理方式依赖于其所对应的属性单元格。即尽管一个值单元格可以同时对应多个属性单元格,但是用户在阅读表格的时候通常还是按照一个“属性”对应一个“值”的方式去理解。如果该属性单元格位于属性行中,则只考虑其rowspan的值。而如果该属性单元格位于属性列中,则只需考虑其colspan的值;对于二维表格(包括ULC为空或不为空的两种情况),则需要分别考虑所在行或列中属性单元格的colspan和rowspan的值对该值单元格相应值的约束。

约束条件一:

Cij.rowspan≤Ci1.rowspan

(1)

太阳城集团(2≤j≤Table.column.size())

约束条件二:

Cij.colspan≤C1j.colspan

(2)

太阳城集团(2≤i≤Table.row.size())

本发明的有益效果:确定Web表格结构是正确理解表格中数据间关系的关键,将直接影响到这类表格抽取结果的准确性。本发明总结出了两种判断表格结构的启发式规则可对部分表格的结构进行快速地判断。而在对未能被启发式规则识别的表格进行字符串比对时,本发明根据表格的特点,选择了ULC所在行或列中的单元格进行计算,从而减少了在进行表格结构识别时需要进行字符串匹配的次数,和其他通过字符串匹配来识别表格结构的方法相比降低了计算量,以达到快速识别表格结构的目的。此外,针对两种结构类型表格的抽取策略将会有效减少冗余数据的产生。

附图说明

太阳城集团图1常见的表格结构示例

太阳城集团图中:黑色区域为属性单元格区域,白色区域为值单元格区域;(a)为非“属性-值”类型表格,(b)为单向展开的一维表格,(c)为ULC为空的二维表格,(d)为ULC不为空的二维表格。

图2Web表格太阳城集团抽取流程

图3一维表格逻辑模型构建过程

太阳城集团图中:(a)为表1的抽象化模型,(b)为(a)中单元格对应的结构树,(c)为表格数据的存储效果。

图4二维表格逻辑模型构建过程

太阳城集团图中:(a)为抽象化的ULC为空的二维表格,(b)为通过属性坐标表示的单元格,(c)为表格数据的存储效果。

图5基于结构识别的Web表格太阳城集团的抽取方法的流程

太阳城集团图6表格标签间的相互关系

图中:实线箭头表示标签间的嵌套关系,箭头末端的标签必须嵌套在所指向的标签内使用;虚线箭头表示同级标签间标签使用的先后次序关系,箭头所指向的标签通常在尾部标签之前使用。

具体实施方式

本发明提出了一种基于结构识别的Web表格太阳城集团抽取方法。该方法能够在快速、准确识别表格结构的基础上对表格太阳城集团进行正确抽取,并且能够有效减少抽取结果中冗余数据的产生。方法的完整流程如图5所示。

太阳城集团本方法的运行包括如下步骤:

1.Web表格的结构识别

①启发式规则(给定一个Web表格)

获取表格的列数,Get_Table.column.size();

如果Table.column.size()为2或3,并且Table.row.size()远大于列数(通常为2倍以上),则表格的第一列为属性单元格;

//同样的规则在列数远大于行数的表格中也适用,而表格的第一行则为属性行。

对于不符合上面判断标准的表格,则再根据表格中<th>标签的使用情况来判定。如果表格中仅有一个<th>标签,则该单元格为表格标题单元格。如果该标签的数量大于1,则由<th>标签构造而成的单元格为属性单元格。进而根据属性单元格的分布情况确定表格的结构类型。

太阳城集团②基于字符串匹配的结构识别方法

如果经过启发式规则无法直接识别表格的结构,则需要进一步通过字符串匹配的方法识别出表格中的属性单元格和值单元格,步骤如下:

假设相邻属性单元格中的内容字符串分别为s1和s2,编辑距离d(s1,s2)表示将s1变成s2所需要的点突变的最少次数。主要的计算过程为:

太阳城集团d(s1-+l1,s2-+l2)=

(3)

min(d(s1-,s2-)+p(l1,l2),d(s1-+l1,s2-)+1,d(s1-,s2-+l2)+1)

太阳城集团其中,l1和l2分别是s1(=s1-+l1)和s2(=s2-+l2)的最后一个字符串。当l1=l2,p(l1,l2)=0;否则p(l1,l2)=1。采用归一化编辑距离(NormalizedEditDistance,ND(s1,s2))作为衡量两个字符串间相似度的指标:

ND ( s 1 , s 2 ) = d ( s 1 , s 2 ) ( | s 1 | + | s 2 | ) / 2 - - - ( 4 ) ]]>

太阳城集团其中,|s1|和|s2|分别为字符串s1和s2的长度。由于合成单元格可以看作是几个相同单元格的组合,因此在对其进行相似度计算时需要首先将其划分成基本单元格,并且这些基本单元格内容间的相似度为1。用FrowSim表示属性行中除ULC外的单元格中内容字符串间的平均相似度,n表示头属性行中单元格的个数,计算公式为:

FrowSim = Σ i = 1 n - 2 ND ( s i , s i + 1 ) n - 2 - - - ( 5 ) ]]>

太阳城集团属性列中字符串的平均相似度LcolSim同样可以用上述方法求得。实验采集50组不同属性下(如日期、型号、速度等)的属性值字符串作为实验样本,计算出在视觉上具有相同特征的同组属性值字符间的相似度,实验结果如下:

表3字符串相似度计算统计结果

太阳城集团由于算法没有考虑同种字符间的相似性(如“45”和“13”间的相似度为0),因此部分同组字符串间的相似性还应高于实验结果。而不同属性下的字符串间相似度的值基本都在10-2数量级以下,和同一属性下字符串间的相似度相差很大。为了充分识别同组字符串,并有效地保证识别的准确率,本文拟将相似度的阈值定为0.3,这个数值在实验中被证明能够有效地区分出同一属性下的内容字符串。

2.表格结构确定后的太阳城集团抽取

①一维表格的太阳城集团抽取

由于一维表格具有单向展开的特点,因此可以借助结构树的方法来理解表格中单元格间的逻辑关系。本发明以一个Row-wise(按行展开)表格为例进行说明,该方法同样适应于Column-wise表格。为了表述方便,图3表格中的数字既表示单元格的编号,又表示单元格中的内容。

在对一维表格进行处理时只需从一个维度进行考虑,按照约束条件(1)对如图3(a)中的合成单元格进行处理,“武器”属性单元格下所对应的三个值单元格均存在COLSPAN的情况,只做横向切割,即将值单元格的rowspan值变为1,而不从纵向的角度进行考虑。如果将其分割成两列完全一样的单元格,就会造成冗余数据的产生。这种冗余数据的数据量是可以衡量的,如Row-wise表格中一个合成单元格所产生的冗余的数据量为cell.colspan-1;对应的,Column-wise表格中一个合成单元格所产生的冗余数据量为cell.rowspan-1。

太阳城集团在对抽取结果进行存储时,分别将叶子节点(图3中3、5、7、8单元格)到其所对应的属性节点(即第二层节点)的路径按行进行存储。

②二维表格的太阳城集团抽取

在二维表格中,一个属性值同时由两个属性决定。如果将属性行和属性列分别看作是直角坐标系的x轴和y轴,则值单元格的表示方式则如图4(c)所示。在这种情况下,表格中的值单元格需要同时满足约束条件(1)和(2)。因此在处理合成单元格时,需要同时考虑其COLSPAN和ROWSPAN的因素。

如果Cm2ij,Cm3ij...Cmnij(n=row(m).columnsize())中,单元格的ROWSPAN的值均不小于Cm1ij.rowspan(),则以Cm1ij.rowspan()为基准对ROWSPAN的值大于Cm1ij.rowspan()的单元格进行横向切分;当Cm2ij,Cm3ij...Cmnij(n=row(m).column.size())中存在ROWSPAN的值小于Cm1ij.rowspan()的时候,就以ROWSPAN的值最小的单元格为基准对该列的表格进行横向切分。表格中各列的处理方式同行中单元格的处理方式相同,判断的标准则变为单元格的COLSPAN的值。

关 键 词:
一种 基于 结构 识别 WEB 表格 太阳城集团 抽取 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种基于结构识别的WEB表格太阳城集团抽取方法.pdf
链接地址:http://zh228.com/p-6401514.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');