计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2013年
8期
2370-2374,2382
,共6页
贺炜%郭云飞%莫涵%扈红超
賀煒%郭雲飛%莫涵%扈紅超
하위%곽운비%막함%호홍초
正则表达式%高速%多字符%精确定位%矩阵压缩
正則錶達式%高速%多字符%精確定位%矩陣壓縮
정칙표체식%고속%다자부%정학정위%구진압축
regular expression%high throughput%multi-character%precise positioning%matrix compress
基于确定性有限自动机(DFA)的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈.为提升处理速率,提出一种单周期处理多字符的匹配算法MC-DFA,该算法基于DFA实现,支持匹配位置的精确定位.MC-DFA将传统DFA中的单字符跳转合并为多字符跳转,实现了单周期处理多个输入字符.通过状态转移矩阵二阶压缩算法,MC-DFA分别对矩阵行内以及行间冗余进行消除,减少了内存使用.300条规则下,单周期处理8字符时,MC-DFA吞吐率能够达到7.88 Gb/s,内存占用小于6 MB,预处理时间为19.24 s.实验结果表明,MC-DFA能够有效提升系统吞吐率,并且保证内存占用在可接受范围之内,性能优于现有正则表达式匹配算法.
基于確定性有限自動機(DFA)的傳統正則錶達式匹配方法存在單週期處理單字符的速度瓶頸.為提升處理速率,提齣一種單週期處理多字符的匹配算法MC-DFA,該算法基于DFA實現,支持匹配位置的精確定位.MC-DFA將傳統DFA中的單字符跳轉閤併為多字符跳轉,實現瞭單週期處理多箇輸入字符.通過狀態轉移矩陣二階壓縮算法,MC-DFA分彆對矩陣行內以及行間冗餘進行消除,減少瞭內存使用.300條規則下,單週期處理8字符時,MC-DFA吞吐率能夠達到7.88 Gb/s,內存佔用小于6 MB,預處理時間為19.24 s.實驗結果錶明,MC-DFA能夠有效提升繫統吞吐率,併且保證內存佔用在可接受範圍之內,性能優于現有正則錶達式匹配算法.
기우학정성유한자동궤(DFA)적전통정칙표체식필배방법존재단주기처리단자부적속도병경.위제승처리속솔,제출일충단주기처리다자부적필배산법MC-DFA,해산법기우DFA실현,지지필배위치적정학정위.MC-DFA장전통DFA중적단자부도전합병위다자부도전,실현료단주기처리다개수입자부.통과상태전이구진이계압축산법,MC-DFA분별대구진행내이급행간용여진행소제,감소료내존사용.300조규칙하,단주기처리8자부시,MC-DFA탄토솔능구체도7.88 Gb/s,내존점용소우6 MB,예처리시간위19.24 s.실험결과표명,MC-DFA능구유효제승계통탄토솔,병차보증내존점용재가접수범위지내,성능우우현유정칙표체식필배산법.
