通信学报
通信學報
통신학보
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
2014年
10期
98-106
,共9页
敬茂华%杨义先%汪韬%辛阳
敬茂華%楊義先%汪韜%辛暘
경무화%양의선%왕도%신양
深度分组检测%模式匹配%正则表达式%有穷自动机%构造算法
深度分組檢測%模式匹配%正則錶達式%有窮自動機%構造算法
심도분조검측%모식필배%정칙표체식%유궁자동궤%구조산법
deep packet inspection%pattern matching%regular expression%finite automata%construction algorithm
提出了一种新颖的正则NFA引擎构造方法——PFA构造法.PFA构造法包括3个主要算法:预处理算法、解析树编码算法和基于编码树的NFA构造算法.采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp.NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小.
提齣瞭一種新穎的正則NFA引擎構造方法——PFA構造法.PFA構造法包括3箇主要算法:預處理算法、解析樹編碼算法和基于編碼樹的NFA構造算法.採用PFA構造法能夠構造齣隻含有一箇開始狀態和一箇終止狀態的規模更小的NFA,稱其為NFAp.NFAp的規模與正則錶達式組的長度線性相關,較Thompson自動機、後跟自動機、位置自動機以及部分派生自動機的規模都要小,是Thompson NFA的1/3,比已經接近最優的後跟自動機構造法所穫得的NFA還要小.
제출료일충신영적정칙NFA인경구조방법——PFA구조법.PFA구조법포괄3개주요산법:예처리산법、해석수편마산법화기우편마수적NFA구조산법.채용PFA구조법능구구조출지함유일개개시상태화일개종지상태적규모경소적NFA,칭기위NFAp.NFAp적규모여정칙표체식조적장도선성상관,교Thompson자동궤、후근자동궤、위치자동궤이급부분파생자동궤적규모도요소,시Thompson NFA적1/3,비이경접근최우적후근자동궤구조법소획득적NFA환요소.
