计算机工程
計算機工程
계산궤공정
Computer Engineering
2015年
10期
280-285
,共6页
多模式匹配%AC算法%漏检%移动距离%模式树
多模式匹配%AC算法%漏檢%移動距離%模式樹
다모식필배%AC산법%루검%이동거리%모식수
multiple pattern matching%AC algorithm%omission%shift distance%pattern tree
在分析AC算法及其相关算法的基础上,提出一种改进的多模式匹配算法AC _TE.利用该算法构建1个字符串跳跃表和2个哈希表,字符串表存储模式树中两两相邻字符组成的字符串及其位置,2个哈希表分别存储模式树末层字符串和字符.采用多层跳跃规则依次查找这3个表,在不发生漏检的情况下,使模式树的最大移动距离为最短模式串长度加3.从模式树移动次数、匹配阶段时间、各种跳跃距离的概率3个方面测试算法性能.实验结果表明,与AC算法相比,AC_TE算法具有更大的模式树移动距离,消耗的时间更少.
在分析AC算法及其相關算法的基礎上,提齣一種改進的多模式匹配算法AC _TE.利用該算法構建1箇字符串跳躍錶和2箇哈希錶,字符串錶存儲模式樹中兩兩相鄰字符組成的字符串及其位置,2箇哈希錶分彆存儲模式樹末層字符串和字符.採用多層跳躍規則依次查找這3箇錶,在不髮生漏檢的情況下,使模式樹的最大移動距離為最短模式串長度加3.從模式樹移動次數、匹配階段時間、各種跳躍距離的概率3箇方麵測試算法性能.實驗結果錶明,與AC算法相比,AC_TE算法具有更大的模式樹移動距離,消耗的時間更少.
재분석AC산법급기상관산법적기출상,제출일충개진적다모식필배산법AC _TE.이용해산법구건1개자부천도약표화2개합희표,자부천표존저모식수중량량상린자부조성적자부천급기위치,2개합희표분별존저모식수말층자부천화자부.채용다층도약규칙의차사조저3개표,재불발생루검적정황하,사모식수적최대이동거리위최단모식천장도가3.종모식수이동차수、필배계단시간、각충도약거리적개솔3개방면측시산법성능.실험결과표명,여AC산법상비,AC_TE산법구유경대적모식수이동거리,소모적시간경소.
