通信学报
通信學報
통신학보
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
2015年
5期
174-186
,共13页
宫阳阳%刘勤让%杨镇西%邵翔宇%邢池强%焦慧娟%彭志彬
宮暘暘%劉勤讓%楊鎮西%邵翔宇%邢池彊%焦慧娟%彭誌彬
궁양양%류근양%양진서%소상우%형지강%초혜연%팽지빈
正则表达式%DFA%有限自动机%状态爆炸
正則錶達式%DFA%有限自動機%狀態爆炸
정칙표체식%DFA%유한자동궤%상태폭작
regular expression%DFA%finite automata%state explosion
多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象.针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA,multi-dimensional finite automata).实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2～3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1～2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1～2个数量级.
多箇正則錶達式規則編譯成一箇DFA(deter minister finite automata)時,會產生狀態爆炸、存儲急劇增加的現象.針對最嚴重的狀態爆炸問題,從信息論的角度給齣瞭解釋,併提齣多維數學模型,將冗餘狀態分為0維狀態和1維狀態,通過前者按照維度壓縮,後者動態構建的方法將空間複雜度降到理論下界,併在此基礎上提齣多維有限自動機(MFA,multi-dimensional finite automata).實驗錶明,MFA構造時間比XFA略少,比DFA、STT冗餘壓縮算法和Hybrid-FA降低瞭2～3箇數量級;存儲空間比XFA略高,比DFA、STT冗餘壓縮算法、mDFA、Hybrid-FA降低瞭1～2箇數量級;匹配時間比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗餘壓縮算法和mDFA降低瞭1～2箇數量級.
다개정칙표체식규칙편역성일개DFA(deter minister finite automata)시,회산생상태폭작、존저급극증가적현상.침대최엄중적상태폭작문제,종신식론적각도급출료해석,병제출다유수학모형,장용여상태분위0유상태화1유상태,통과전자안조유도압축,후자동태구건적방법장공간복잡도강도이론하계,병재차기출상제출다유유한자동궤(MFA,multi-dimensional finite automata).실험표명,MFA구조시간비XFA략소,비DFA、STT용여압축산법화Hybrid-FA강저료2～3개수량급;존저공간비XFA략고,비DFA、STT용여압축산법、mDFA、Hybrid-FA강저료1～2개수량급;필배시간비DFA、Hybrid-FA략다,단시비XFA략소,비STT용여압축산법화mDFA강저료1～2개수량급.
