软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2011年
1期
149-163
,共15页
深度包检测%正则表达式%多模式匹配%复合的FSM%D2FA(delayed input DFA)%WD2FA(weighted delayed input DFA)
深度包檢測%正則錶達式%多模式匹配%複閤的FSM%D2FA(delayed input DFA)%WD2FA(weighted delayed input DFA)
심도포검측%정칙표체식%다모식필배%복합적FSM%D2FA(delayed input DFA)%WD2FA(weighted delayed input DFA)
随着深度包检测规则数目的剧烈增长.为了适应网络处理的需求,必须对表示正则表达式的DFA(deterministic finite automata,确定的有限自动机)进行高效的存储一方面,对DFA的状态点数目进行压缩,提出了一种复合的FSM(有限自动机)的构造方法,通过对正则表达转化成DFA的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建DFA,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对DFA队的状态转移数目进行压缩,给出了一种高效的压缩算法,即WD2FA(weighted delayed input DFA,带权延迟DFA)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于D2FA(delayed input DFA,延迟的DFA)有更好的压缩能力,并且使得D2FA是WD2FA在权值为O情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%.
隨著深度包檢測規則數目的劇烈增長.為瞭適應網絡處理的需求,必鬚對錶示正則錶達式的DFA(deterministic finite automata,確定的有限自動機)進行高效的存儲一方麵,對DFA的狀態點數目進行壓縮,提齣瞭一種複閤的FSM(有限自動機)的構造方法,通過對正則錶達轉化成DFA的狀態點數目複雜度的分析,將不同複雜度的正則錶達式採用不同的方式構建DFA,使得所有平方級和指數級複雜度的狀態點數目降低到瞭線性級.另一方麵,對DFA隊的狀態轉移數目進行壓縮,給齣瞭一種高效的壓縮算法,即WD2FA(weighted delayed input DFA,帶權延遲DFA)算法,對于任意複雜度的正則錶達式都可以將狀態轉移數目壓縮為原來的5%左右,相對于D2FA(delayed input DFA,延遲的DFA)有更好的壓縮能力,併且使得D2FA是WD2FA在權值為O情況下的特例.實驗結果錶明,有限自動機的狀態點數目能夠控製在線性級,併且在狀態點壓縮的基礎上將狀態轉移數目壓縮為原來的7%.
수착심도포검측규칙수목적극렬증장.위료괄응망락처리적수구,필수대표시정칙표체식적DFA(deterministic finite automata,학정적유한자동궤)진행고효적존저일방면,대DFA적상태점수목진행압축,제출료일충복합적FSM(유한자동궤)적구조방법,통과대정칙표체전화성DFA적상태점수목복잡도적분석,장불동복잡도적정칙표체식채용불동적방식구건DFA,사득소유평방급화지수급복잡도적상태점수목강저도료선성급.령일방면,대DFA대적상태전이수목진행압축,급출료일충고효적압축산법,즉WD2FA(weighted delayed input DFA,대권연지DFA)산법,대우임의복잡도적정칙표체식도가이장상태전이수목압축위원래적5%좌우,상대우D2FA(delayed input DFA,연지적DFA)유경호적압축능력,병차사득D2FA시WD2FA재권치위O정황하적특례.실험결과표명,유한자동궤적상태점수목능구공제재선성급,병차재상태점압축적기출상장상태전이수목압축위원래적7%.
