Regular expression matching algorithm based on parameters setting
1.School of Information Engineering, Southwest University of Science and Technology, Mianyang, Sichuan 621010, China; 2.Robot Technology Used for Special Environment Key Laboratory of Sichuan Province, Southwest University of Science and Technology, Mianyang, Sichuan 621010, China; 3.Sichuan Communication Research Planning and Designing Co., Ltd., Chengdu, Sichuan 610041, China
Abstract：To well balance time complexity and space complexity in regular expression, a matching algorithm for regular expression of deterministic finite automata was proposed through dynamic parameters DFA(DPDFA). The performance of current typical matching algorithm of regular expression was analyzed, and the insufficiencies in CPU memory occupation, matching time and expandability were indicated to give the design concept of DPDFA. The toplimit of state number after combination was set up, and the exclusivity among the combination expressions was separated to reduce the CPU occupation. The growth rate parameter of state number was set up, and the expression was sliced up. The expanding section of state number was isolated to reduce matching ambiguity and matching time. The experimental results show that the DPDFA algorithm is at least 23％ overmatching than D2FA in time complexity with 43％ overmatching than mDFA in space complexity and 260％ overmatching than XFA in expandability. It is briefly more superior to other algorithm in overall matching efficiency.
2016, Vol. 37 
