| 摘要 |
The present invention relates to a method for converting a regular expression on a text into deterministic finite automata (DFA), which is capable of realizing memory-efficient DFA by solving state blowup problems, which can occur in a process of converting a regular expression into DFA as regular expressions become complicated and a number thereof increases, by merging of a state having the same input character. The method of the present invention comprises the steps of: (a) storing, in L(i), the character string length of each of an N number of regular expression patterns; (b) reversely aligning the patterns according to the stored length L(i) of the patterns; (c) converting into DFA with uniqueness of a state converted upon a state transition; (d) searching a state having the same input character through a process of comparing DFA generated from an i(1<=i<=N-1)^th pattern with DFA generated from a j(i+1<=j<=N)^th pattern, among DFA converted in the step (c); (e) merging the combinable state searched in the step (d) to generate a new state; and (f) applying a conventional algorithm to the DFA generated in the step (e). [Reference numerals] (a) Initial DFA; (AA) Depth; (b) Search a mergeable state S4 and S6; (c) Search a mergeable state S3 and S5; (d) Non-mergeable state |
