计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2014年
8期
282-287,292
,共7页
杨嘉佳%姜腊林%姜磊%戴琼%谭建龙
楊嘉佳%薑臘林%薑磊%戴瓊%譚建龍
양가가%강석림%강뢰%대경%담건룡
正则表达式%ClusterFA算法%确定型有穷自动机%游程编码%压缩率%吞吐率
正則錶達式%ClusterFA算法%確定型有窮自動機%遊程編碼%壓縮率%吞吐率
정칙표체식%ClusterFA산법%학정형유궁자동궤%유정편마%압축솔%탄토솔
regular expression%ClusterFA algorithm%Deterministic Finite Automata DFA)%Run-length Encoding (RLE)%compression ratio%throughput
基于簇聚类的确定型有穷自动机(DFA)压缩算法,即ClusterFA算法,解决了正则表达式匹配中的空间爆炸问题,但该算法的分组个数取理想值较为困难,且其类中心向量表的每一行中连续重复转移状态出现频率较高.针对该问题,提出一种改善ClusterFA算法的方案En_ClusterFA.提取类中心向量表行与行之间相同的首尾部分,并对其进行游程编码以建立索引表,对类中心向量表余下部分的转移状态进行游程编码.利用该方案对Bro,Snort 和L7-filter规则集进行测试,实验结果表明,除了L7_2和L7_6规则集的压缩率分别提高到96.1%和98.1%之外,其他规则集的压缩率都提高到99%以上.与ClusterFA算法的压缩率相比,En_ClusterFA平均提高了4%,证明En_ClusterFA能够有效地提高DFA的压缩效率.
基于簇聚類的確定型有窮自動機(DFA)壓縮算法,即ClusterFA算法,解決瞭正則錶達式匹配中的空間爆炸問題,但該算法的分組箇數取理想值較為睏難,且其類中心嚮量錶的每一行中連續重複轉移狀態齣現頻率較高.針對該問題,提齣一種改善ClusterFA算法的方案En_ClusterFA.提取類中心嚮量錶行與行之間相同的首尾部分,併對其進行遊程編碼以建立索引錶,對類中心嚮量錶餘下部分的轉移狀態進行遊程編碼.利用該方案對Bro,Snort 和L7-filter規則集進行測試,實驗結果錶明,除瞭L7_2和L7_6規則集的壓縮率分彆提高到96.1%和98.1%之外,其他規則集的壓縮率都提高到99%以上.與ClusterFA算法的壓縮率相比,En_ClusterFA平均提高瞭4%,證明En_ClusterFA能夠有效地提高DFA的壓縮效率.
기우족취류적학정형유궁자동궤(DFA)압축산법,즉ClusterFA산법,해결료정칙표체식필배중적공간폭작문제,단해산법적분조개수취이상치교위곤난,차기류중심향량표적매일행중련속중복전이상태출현빈솔교고.침대해문제,제출일충개선ClusterFA산법적방안En_ClusterFA.제취류중심향량표행여행지간상동적수미부분,병대기진행유정편마이건립색인표,대류중심향량표여하부분적전이상태진행유정편마.이용해방안대Bro,Snort 화L7-filter규칙집진행측시,실험결과표명,제료L7_2화L7_6규칙집적압축솔분별제고도96.1%화98.1%지외,기타규칙집적압축솔도제고도99%이상.여ClusterFA산법적압축솔상비,En_ClusterFA평균제고료4%,증명En_ClusterFA능구유효지제고DFA적압축효솔.