摘要
从有限自动机中生成简短、可读性强的正则表达式是计算机理论研究中的一个重大课题.在经典的正则表达式生成算法中,状态序列是影响正则表达式质量的关键因素.为了能够快速高效地找到较优的状态序列,本文以食肉植物算法的理论为核心,并结合其他启发式算法的思想进行设计与优化,提出了一种基于食肉植物算法的状态序列搜索方法.通过实验将此方法与已有的一些使用启发式规则的搜索算法进行了对比,实验结果表明,基于食肉植物算法的状态序列搜索方法优于其他启发式算法,生成的正则表达式长度比起其他启发式算法明显缩短,如跟DM算法相比,长度的缩短幅度可以随着自动机阶数的增加达到20%以上,跟随机序列算法相比,可以把长度缩短多个数量级.
Generating short and readable regular expressions from finite automata is an important topic in computer theory. In the classical regular expression generation algorithms, the state sequence is the key factor that affects the quality of regular expressions. To search for excellent state sequences quickly and efficiently, this study takes the theory of the carnivorous plant algorithm as the core, combines the ideas of other heuristic algorithms for design and optimization, and proposes a state sequence search method based on the carnivorous plant algorithm. Through experiments, this method is compared with some existing search algorithms using heuristic rules. The experimental results demonstrate that the proposed state sequence search method is superior to other algorithms, and the length of the generated regular expressions is significantly shorter than that of other heuristic algorithms. For example, compared with the results of the DM algorithm, the length can be shortened by more than 20% with the increase in the order of automata,and compared with the results of the random sequence algorithm, the length can be shortened by several orders of magnitude.
作者
刘丁铨
高俊涛
LIU Ding-Quan;GAO Jun-Tao(School of Computer and Information Technology,Northeast Petroleum University,Daqing 163318,China)
出处
《计算机系统应用》
2023年第3期232-237,共6页
Computer Systems & Applications
基金
东北石油大学优秀中青年科研创新团队培育基金(KYCXTDQ202101)。
关键词
正则表达式
状态序列
食肉植物算法
有限自动机
regular expression
state sequence
carnivorous plant algorithm
finite automata
