东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2013, Vol. 34 ›› Issue (9): 1240-1243.DOI: -

• 信息与控制 • 上一篇    下一篇

一种构造正则表达式更小ε-NFA的方法

敬茂华1,2，杨义先2,3，于长永1，辛阳3   

  1. (1东北大学秦皇岛分校计算机与通信工程学院，河北秦皇岛066004；2东北大学信息科学与工程学院，辽宁沈阳110819；3北京邮电大学信息安全中心，北京100876)
  • 收稿日期:2013-01-18 修回日期:2013-01-18 出版日期:2013-09-15 发布日期:2013-04-22
  • 通讯作者: 敬茂华
  • 作者简介:敬茂华(1977-)，女，四川蓬溪人，东北大学秦皇岛分校讲师，东北大学博士研究生;杨义先(1961-)，男，四川盐亭人，北京邮电大学教授，东北大学外聘博士生导师，教育部“长江学者奖励计划”特聘教授.
  • 基金资助:
    国家自然科学基金资助项目(61100021，61121061，61202447)；河北省自然科学基金资助项目(F2012501014)；教育部高等学校博士学科点专项科研基金资助项目(20120042120009)；河北省自然科学青年基金资助项目(F2013501048).

A Constructing Method of Regular Expression’s Smaller εNFA

JING Maohua1,2， YANG Yixian2,3， YU Changyong1， XIN Yang3   

  1. 1. School of Computer and Communication Engineering， Northeastern University at Qinhuangdao， Qinhuangdao 066004， China; 2. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 3. Information Security Center， Beijing University of Posts and Telecommunications， Beijing 100876，China.
  • Received:2013-01-18 Revised:2013-01-18 Online:2013-09-15 Published:2013-04-22
  • Contact: JING Maohua
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

771

摘要： 基于有限自动机的正则表达式匹配技术在网络信息领域得到了广泛应用，提出了一种构造正则表达式的更小NFA的方法——基于闭包的分片构造法GREC.GREC方法基于正则表达式中同态运算的封闭性以及闭包运算的层次特性和递归性进行构造.首先对正则表达式进行分片处理，然后构造每个分片的NFA，最后利用栈对各分片NFA进行重组获得最终的NFA.GREC方法在正则表达式层次结构复杂或包含有大量闭包运算的情况下，能够快速地构造出空间效率比传统的Thompson构造法高得多的NFA.

关键词: 正则表达式, 有限自动机, 闭包, 同态运算, 构造算法

Abstract: Regular expression matching technology based on finite automaton(FA)has been widely used in the network and information field. A new method was proposed to construct the smaller nondeterministic FA(NFA) of regular expressions， namely， grouping regular expression based on closure(GREC). The GREC method was constructed based on the principle that all kinds of homomorphism computing of regular expression were closure and the hierarchy and recursiveness of closure operation were in regular set. The regular expression was cut into pieces， and then the NFA was constructed for each slice. Finally the stack to the restructuring of the NFA of each slice was used to obtain the final NFA. It can be concluded that NFA can be quickly constructed by the proposed GREC method， which has higher space efficiency compared with traditional Thompson structured approach when the regular expression is too complex in hierarchical structure or contains too many closure operations.

Key words: regular expression, finite automaton, closure, homomorphism computing, construction algorithm

中图分类号: