Efficient i-DFA construction algorithm based on state grouping
Regular expression matching plays an important role in many network and security applications.DFA is the preferred representation to perform regular expression matching in high-speed network,because of its high and stable matching efficiency.However,DFA may experience state explosion,and thus consum...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2013-08-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2013.08.014/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539839641518080 |
|---|---|
| author | Deng-ke QIAO Qing WANG Ting-wen LIU Yong SUN Li GUO |
| author_facet | Deng-ke QIAO Qing WANG Ting-wen LIU Yong SUN Li GUO |
| author_sort | Deng-ke QIAO |
| collection | DOAJ |
| description | Regular expression matching plays an important role in many network and security applications.DFA is the preferred representation to perform regular expression matching in high-speed network,because of its high and stable matching efficiency.However,DFA may experience state explosion,and thus consume huge memory space.As a classical solution for the problem of state explosion,i-DFA can reduce the memory consumption significantly and guarantee the worst matching performance at the same time.However,prior methods are inefficient in both time and space during the construction of i-DFA.An efficient i-DFA construction algorithm based on the idea of state grouping was proposed.Furthermore,a formal description for the problem of state grouping was given,and it was proved that it was NP-hard to get the best state grouping result.Thus,based on local search strategy,a near-optimal algorithm was introduced to divide states into different groups.Compared with the classical construction method,the significant improvement in both time and space is achieved; the i-DFA of the proposed method may have 2/3 states as that of prior method and the proposed i-DFA is constructed with only 1/16 time of it. |
| format | Article |
| id | doaj-art-cef0bf8f9460441097e0a49c0003bc47 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2013-08-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-cef0bf8f9460441097e0a49c0003bc472025-01-14T06:41:05ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2013-08-013410210959674257Efficient i-DFA construction algorithm based on state groupingDeng-ke QIAOQing WANGTing-wen LIUYong SUNLi GUORegular expression matching plays an important role in many network and security applications.DFA is the preferred representation to perform regular expression matching in high-speed network,because of its high and stable matching efficiency.However,DFA may experience state explosion,and thus consume huge memory space.As a classical solution for the problem of state explosion,i-DFA can reduce the memory consumption significantly and guarantee the worst matching performance at the same time.However,prior methods are inefficient in both time and space during the construction of i-DFA.An efficient i-DFA construction algorithm based on the idea of state grouping was proposed.Furthermore,a formal description for the problem of state grouping was given,and it was proved that it was NP-hard to get the best state grouping result.Thus,based on local search strategy,a near-optimal algorithm was introduced to divide states into different groups.Compared with the classical construction method,the significant improvement in both time and space is achieved; the i-DFA of the proposed method may have 2/3 states as that of prior method and the proposed i-DFA is constructed with only 1/16 time of it.http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2013.08.014/regular expressionstate explosionstate groupinglocal search |
| spellingShingle | Deng-ke QIAO Qing WANG Ting-wen LIU Yong SUN Li GUO Efficient i-DFA construction algorithm based on state grouping Tongxin xuebao regular expression state explosion state grouping local search |
| title | Efficient i-DFA construction algorithm based on state grouping |
| title_full | Efficient i-DFA construction algorithm based on state grouping |
| title_fullStr | Efficient i-DFA construction algorithm based on state grouping |
| title_full_unstemmed | Efficient i-DFA construction algorithm based on state grouping |
| title_short | Efficient i-DFA construction algorithm based on state grouping |
| title_sort | efficient i dfa construction algorithm based on state grouping |
| topic | regular expression state explosion state grouping local search |
| url | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2013.08.014/ |
| work_keys_str_mv | AT dengkeqiao efficientidfaconstructionalgorithmbasedonstategrouping AT qingwang efficientidfaconstructionalgorithmbasedonstategrouping AT tingwenliu efficientidfaconstructionalgorithmbasedonstategrouping AT yongsun efficientidfaconstructionalgorithmbasedonstategrouping AT liguo efficientidfaconstructionalgorithmbasedonstategrouping |