基于连续重复子串左联配的正则表达式识认算法

发布时间：2020-08-18 13:56

【摘要】：形式语言的归纳学习致力于研究如何从语言的有限信息出发,通过归纳推断得到语言的定义。在形式语言体系中,正则语言是一类使用较为广泛的语言类。以正则表达式为目标的正则语言学习算法在基因序列识别、XML模式推断、图数据库查询学习、信息抽取中有广泛应用。因此,对正则表达式学习算法的研究不仅具有重要的理论意义,还具有较大的实际应用价值。语言极限识认模型是语言学习的经典模型,在该模型下进行学习算法研究,不仅能确保算法的良好特性,且学习语言类具有清晰明确的界定。本文基于语言极限识认模型,研究正则表达式学习算法,主要研究成果如下所述。(1)提出了基于连续重复子串左联配的正则表达式识认框架:首先,识别句子中的最长连续重复子串;其次,基于连续重复子串分块;然后,对分块进行左联配;最后,将联配结果泛化为正则表达式。在该框架内进行算法研究,可以识认一元正则运算符作用在多个连续字符上的正则表达式,克服了现有大多数算法只能识认运算符作用在单个字符上的局限性。(2)针对标准表达式和带数字出现的表达式,分别提出了两类不同的泛化策略,并实现了两种不同的识认算法。分析出可由算法识认的表达式子类,总结出表达式子类对应的特征样本的特性。为了验证理论分析结果,本文开发了一组工具用于表达式及其特征样本的生成并进行了相关的实验,实验结果验证了理论分析的正确性。对比了本文算法和已有算法,结果表明本文算法的识认结果在紧凑性、可读性方面均存在优势。(3)探讨了识认算法在图数据库查询学习中的应用,分析出图数据库可达性查询中有一类由正则表达式定义的路径约束与本文提出的带数字出现的表达式子类相吻合,因此可将本文算法应用于图数据库可达性查询学习。总结出可达性查询学习的一般步骤,并用实例考察了本文算法在可达性查询学习中的应用。
【学位授予单位】：华侨大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：H08;TP391.1
【图文】：

研究内容结构图

章节结构图

最长公共前缀定义3.6（RMQ,RangeMinimumQuery）对于长度为n的数组A及区间bbaaaab1

【参考文献】

相关期刊论文 前3条

1 邓绪斌;;基于最优树联配的正则表达式学习算法[J];复旦学报(自然科学版);2011年06期

2 张瑞岭,董韫美;逐步求精法获取上下文无关文法[J];计算机研究与发展;2000年01期

3 张瑞岭;文法推断研究的历史和现状[J];软件学报;1999年08期

本文编号：2796300