一类受限正则表达式的推断算法

• 作者: 冯晓强 郑黎晓 陈海明
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: XML模式 模式推断 正则表达式 自动机 算法
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 软件与数据库技术
• 页码范围: 178-183
• 页数: 6页
• 分类号: TP301
• 字数: 7467字
• 语种: 中文

摘要

XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式.提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法.该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式.该算法的时间复杂度为max(O(|V| +|E|),C(L)),其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和.对算法的终止性和正确性进行了证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈海明	中国科学院软件研究所计算机科学国家重点实验室	29	1570	11.0	29.0
2	冯晓强	中国科学院软件研究所计算机科学国家重点实验室	9	68	5.0	8.0
6	郑黎晓	华侨大学计算机科学与技术学院	9	92	4.0	9.0