论文部分内容阅读
XML是目前互联网中广泛使用的一种可扩展标记语言。XML模式在XML数据整合、验证等方面有着非常广泛的应用。然而,在现实应用中许多XML文档缺少对应的模式或给定的模式不满足规范。因此,从XML文档中学习到一个合适的XML模式是一个很重要的课题。XML模式学习本质上可以归约到正则表达式的推断问题。本文基于对实际数据的统计分析,提出了一类比现有子类具有更高覆盖率的确定性受限正则表达式k-occurrence deterministic extended chain regular expression(k-Dechare)。并给出一个推断算法k-Dechare-infer,从理论上证明对于给定的句子集合S,该算法可以推断出一个描述性泛化的k-Dechare。 k-Dechare-infer算法首先构造句子集合对应的一个确定性k-OA。其次对k-OA中带自环的节点、非平凡强连通分量和回形结构节点进行处理。接着计算k-OA中每个节点相应的级数以及找到所有的跳级,最后将每一个级数下面的所有节点转化为一个或者多个链式因子,由此得到句子集合对应的k-Dechare。 最后,本文基于Python语言实现了k-Dechare-infer算法,并与同k-Dechare具有相似结构的子类的推断算法Soa2Chare、GenEchare以及XML工具IntelliJ IDEA、Altova XMLSpy和Trang的推断结果进行了对比。实验结果表明,在相同的句子集上,本文提出的k-Dechare-infer算法的推断结果更接近现实样本中的数据出现形式,比前述算法更精确。