软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2012年
9期
2261-2272
,共12页
柳厅文%孙永%卜东波%郭莉%方滨兴
柳廳文%孫永%蔔東波%郭莉%方濱興
류청문%손영%복동파%곽리%방빈흥
正则表达式%深度包检测%分组算法%局部搜索%1/(1-1/k)近似
正則錶達式%深度包檢測%分組算法%跼部搜索%1/(1-1/k)近似
정칙표체식%심도포검측%분조산법%국부수색%1/(1-1/k)근사
对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k)与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.
對正則錶達式集閤進行分組是解決DFA狀態膨脹問題的一種重要方法.已有的分組算法大都是啟髮式的或蠻力的,分組效果很差.分析瞭DFA狀態膨脹的原因,總結瞭某些正則錶達式間的遲突狀況.證明瞭噹遲突非負和遲突獨立時,正則錶達式集閤的最優k分組問題可歸結為最大k割問題,從而說明該問題是NP-Hard的.基于跼部搜索的思想,提齣瞭一種分組算法GRELS來解決分組問題,併證明對最大k割問題,該算法的近似比是1/(1-1/k)與已有的分組算法相比,噹分組數目相同時,GRELS算法分組結果的狀態總數最少,併且集閤髮生變化時所需的更新時間最短.
대정칙표체식집합진행분조시해결DFA상태팽창문제적일충중요방법.이유적분조산법대도시계발식적혹만력적,분조효과흔차.분석료DFA상태팽창적원인,총결료모사정칙표체식간적충돌상황.증명료당충돌비부화충돌독립시,정칙표체식집합적최우k분조문제가귀결위최대k할문제,종이설명해문제시NP-Hard적.기우국부수색적사상,제출료일충분조산법GRELS래해결분조문제,병증명대최대k할문제,해산법적근사비시1/(1-1/k)여이유적분조산법상비,당분조수목상동시,GRELS산법분조결과적상태총수최소,병차집합발생변화시소수적경신시간최단.
