通信学报
通信學報
통신학보
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
2013年
10期
183-190
,共8页
正则表达式%状态爆炸%自动机转化%状态约束
正則錶達式%狀態爆炸%自動機轉化%狀態約束
정칙표체식%상태폭작%자동궤전화%상태약속
regular expression%state explosion%automata convert%state constrains
通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程,分析内存增长的原因,提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组,利用状态间的约束关系,将原始NFA转化为NFA和DFA的混合结构。实验表明,在保持一定处理速率的前提下,Group2-DFA能够有效地减少内存占用。在300条规则下,Group2-DFA吞吐率能够达到1Gbps,并且减少约75%的状态数。
通過觀察不確定有限自動機NFA到確定性有限自動機DFA的轉化過程,分析內存增長的原因,提齣瞭一種基于狀態間約束關繫的正則錶達式匹配算法Group2-DFA。Group2-DFA通過兩級分組,利用狀態間的約束關繫,將原始NFA轉化為NFA和DFA的混閤結構。實驗錶明,在保持一定處理速率的前提下,Group2-DFA能夠有效地減少內存佔用。在300條規則下,Group2-DFA吞吐率能夠達到1Gbps,併且減少約75%的狀態數。
통과관찰불학정유한자동궤NFA도학정성유한자동궤DFA적전화과정,분석내존증장적원인,제출료일충기우상태간약속관계적정칙표체식필배산법Group2-DFA。Group2-DFA통과량급분조,이용상태간적약속관계,장원시NFA전화위NFA화DFA적혼합결구。실험표명,재보지일정처리속솔적전제하,Group2-DFA능구유효지감소내존점용。재300조규칙하,Group2-DFA탄토솔능구체도1Gbps,병차감소약75%적상태수。
By analysis of state explosion in deterministic finite automata DFA, a novel algorithm Group2-DFA based on state constrains was proposed to reduce the memory usage. With the state constrains, states in NFA were classified into several groups. Group2-DFA introduces two-level classification and merges NFA and DFA together to a hybrid FA construction. The experiments show that Group2-DFA can reduce memory usage efficiently and keep high throughput with a small increase of memory reading time. With 300 regex rules, Group2-DFA can cut 75%states and achieve 1Gbps throughput.