计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
12期
177-180,194
,共5页
侯宝剑%谢飞%胡学钢%刘应玲%王海平
侯寶劍%謝飛%鬍學鋼%劉應玲%王海平
후보검%사비%호학강%류응령%왕해평
模式匹配%通配符%后缀树
模式匹配%通配符%後綴樹
모식필배%통배부%후철수
由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究的热点.针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束.采用非线性数据结构——后缀树,设计了求解模式所有解的完备算法PAST.预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合动态规划的思想,逐个匹配模式中字符,最终得到完备解.在基因序列上的实验表明,PAST比其他算法具有更好的时间性能.
由于在生物序列分析、文本索引、網絡入侵檢測等領域的應用需求,帶有通配符的模式匹配問題一直是研究的熱點.針對已有的研究工作中通配符和長度約束具有較彊的跼限性問題,研究帶有靈活通配符的模式匹配問題,其中通配符可以在模式的任意兩子串間齣現且可以指定靈活的長度約束.採用非線性數據結構——後綴樹,設計瞭求解模式所有解的完備算法PAST.預處理階段採用在線增量式算法構建具有文本先驗知識的後綴樹,搜索階段結閤動態規劃的思想,逐箇匹配模式中字符,最終得到完備解.在基因序列上的實驗錶明,PAST比其他算法具有更好的時間性能.
유우재생물서렬분석、문본색인、망락입침검측등영역적응용수구,대유통배부적모식필배문제일직시연구적열점.침대이유적연구공작중통배부화장도약속구유교강적국한성문제,연구대유령활통배부적모식필배문제,기중통배부가이재모식적임의량자천간출현차가이지정령활적장도약속.채용비선성수거결구——후철수,설계료구해모식소유해적완비산법PAST.예처리계단채용재선증량식산법구건구유문본선험지식적후철수,수색계단결합동태규화적사상,축개필배모식중자부,최종득도완비해.재기인서렬상적실험표명,PAST비기타산법구유경호적시간성능.
