系统仿真技术
繫統倣真技術
계통방진기술
SYSTEM SIMULATION TECHNOLOGY
2014年
2期
116-120,139
,共6页
多模式匹配%时间复杂度%BM算法%AC算法
多模式匹配%時間複雜度%BM算法%AC算法
다모식필배%시간복잡도%BM산법%AC산법
multiple patterns matching%computational complexity%BM algorithm%AC algorithm
多模式匹配技术在很多领域中发挥着重要作用.在自动机多模式匹配的AC算法的基础上,结合经典跳跃式的BM算法的优点,提出了一种高效率的多模式匹配算法.该算法寻找模式串的尾字符和首字符从右向左开始匹配,尽可能多地跳跃不需要匹配目标文本串中字符,减少一些不必要的麻烦,实现快速匹配.经过实验数据表明,不管模式串数目增加,还是模式串长度增加,该算法所花费的时间最少,几乎是BM算法的1/5,是AC算法的1/3.
多模式匹配技術在很多領域中髮揮著重要作用.在自動機多模式匹配的AC算法的基礎上,結閤經典跳躍式的BM算法的優點,提齣瞭一種高效率的多模式匹配算法.該算法尋找模式串的尾字符和首字符從右嚮左開始匹配,儘可能多地跳躍不需要匹配目標文本串中字符,減少一些不必要的痳煩,實現快速匹配.經過實驗數據錶明,不管模式串數目增加,還是模式串長度增加,該算法所花費的時間最少,幾乎是BM算法的1/5,是AC算法的1/3.
다모식필배기술재흔다영역중발휘착중요작용.재자동궤다모식필배적AC산법적기출상,결합경전도약식적BM산법적우점,제출료일충고효솔적다모식필배산법.해산법심조모식천적미자부화수자부종우향좌개시필배,진가능다지도약불수요필배목표문본천중자부,감소일사불필요적마번,실현쾌속필배.경과실험수거표명,불관모식천수목증가,환시모식천장도증가,해산법소화비적시간최소,궤호시BM산법적1/5,시AC산법적1/3.