正反例相结合的正则表达式极限识认算法

Study of regular expression learning algorithms is not only of theoretical interest but also of practical importance. According to Gold’s learning paradigm of “identification in the limit”, the classical model of language learning, regular languages are not identifiable from positive data only. The known subclasses of regular languages that are identifiable have strong limit in expressive power, which restricts the use of them in practical applications. Gold has also proved that, together with negative data, the whole of regular languages can be identified. Most of the existing algorithms for identifying regular languages from positive and negative data take finite automata as learning target. The disadvantage of basing expression identification on the identification of automata is that when we finally translate automata into expressions by standard algorithms, the results are often clumsy and lengthy, not suitable for practical use. In this project, we propose to take regular expressions as the direct learning target, and investigate the theoretical problems and algorithms for identification in the limit of regular languages from positive and negative data. More specifically, we will focus on the following issues: design of identification algorithms, characterization of characteristic samples, theoretical analysis of algorithms and characteristic samples, evaluation method of the identification results, and so on. Apart from the standard regular expressions as target, we will also consider regular expressions with counting which are also commonly used in practice. The obtained results of this project will not only provide effective support for the use of regular expression learning algorithms in practice, but also can further enhance the theory of identification in the limit of regular languages.

对正则表达式学习算法的深入研究不仅具有重要理论意义，还具有较大实际应用价值。根据语言学习的经典理论模型，即Gold极限识认模型，正则语言在只有正例的情况下无法极限识认。已知的可识认子类对语言表达能力限制太强，在实际中不一定够用。如果同时含有反例，则整个正则语言类可以极限识认。已有的正反例相结合的正则语言识认算法大多以自动机为识认目标，而从自动机转换为表达式时存在长度爆炸等问题，给实际应用带来困难。因此，本项目围绕如何从含有正反例的样本信息中直接以正则表达式为学习目标，研究正则语言极限识认相关的理论和算法问题，包括：认识算法的设计和特征样本的刻画、算法及特征样本特性的理论分析、识认结果的评估等。识认目标除了标准表达式之外，还研究实际中经常用到的带数字出现的表达式。项目研究成果一方面能够为正则表达式学习算法的更好应用提供理论与算法支持，另一方面也可以丰富正则语言极限识认研究相关的理论体系。

形式语言的归纳学习致力于研究如何从语言的有限信息出发，通过归纳推断得到语言的定义。在形式语言体系中，正则语言是一类使用较为广泛并且具有良好特性的语言类。对以正则表达式为学习目标的正则语言学习算法的深入研究不仅具有重要理论意义，而且在基因序列识别、XML模式推断、信息抽取、图数据库中路径查询语句学习等领域具有广泛而重要的应用。本项目基于经典的语言极限识认模型，围绕如何从给定的样本信息中直接以正则表达式为学习目标，研究正则语言极限识认相关的理论和算法问题。主要研究成果简述如下。（1）从XML模式推断这一应用作为出发点，对现有的正则表达式学习算法现状进行了深入调研，对已有算法进行了细致的分类、归纳和对比。（2）提出一种基于连续重复子串挖掘和左联配的正则表达式学习算法。理论分析证明出该算法符合语言学习的极限识认模型，能够学习出一类不含“|”操作符的受限正则表达式，同时算法经过扩展可以学习出支持计数的扩展表达式。理论分析并总结出学习出的目标表达式所对应的特征样本的特点，并通过实验验证了理论分析结果的正确性。（3）基于软件测试中成对测试的思想提出一种正则表达式覆盖准则，称作“成对覆盖”，并设计和实现从正则表达式中自动生成满足成对覆盖准则的字符串生成算法。该算法可以用来为正则表达式识认（推断） 算法自动生成测试数据。（4） 研究一类路径查询语句的视图确定性问题，其中对路径表达式的性质、确定性问题的可判定性及复杂性等理论问题做了深入探讨，为正则表达式推断算法在图数据查询学习中的应用研究提供必要的知识积累。此外，还尝试将进化算法的思想应用于正则表达式学习中，研究如何对正则表达式进行编码，已经如何定义适应度函数和获得新的候选解使用的交叉、变异等算子。该部分工作正在进行中。这些研究成果一方面能够为正则表达式学习算法的更好应用提供理论与算法支持，另一方面也可以丰富正则语言极限识认研究相关的理论体系。

内容获取失败，请点击重试