计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2012年
11期
173-176
,共4页
模式匹配%自动机%动态规划%Trie树
模式匹配%自動機%動態規劃%Trie樹
모식필배%자동궤%동태규화%Trie수
Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态.为此,提出一种快速多模式匹配算法.该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率.算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息.实验结果表明,该算法匹配精确、效率高,且支持在线操作.
Aho-Corasick自動機算法在模式匹配失配時,需要多次迴溯纔轉移到有效的後繼狀態.為此,提齣一種快速多模式匹配算法.該算法為每箇狀態建立失配時的後繼指針,在模式匹配失配時,可以通過失配後繼指針快速找到有效後繼狀態,從而避免Aho-Corasick自動機失配時的過多迴溯,提高匹配效率.算法在自動機建立時採用動態規劃的方法,為每箇狀態建立匹配長度和匹配量等信息,在模式匹配過程中,基于這些信息統計模式串在主串中的重複次數、最早齣現模式串位置等信息.實驗結果錶明,該算法匹配精確、效率高,且支持在線操作.
Aho-Corasick자동궤산법재모식필배실배시,수요다차회소재전이도유효적후계상태.위차,제출일충쾌속다모식필배산법.해산법위매개상태건립실배시적후계지침,재모식필배실배시,가이통과실배후계지침쾌속조도유효후계상태,종이피면Aho-Corasick자동궤실배시적과다회소,제고필배효솔.산법재자동궤건립시채용동태규화적방법,위매개상태건립필배장도화필배량등신식,재모식필배과정중,기우저사신식통계모식천재주천중적중복차수、최조출현모식천위치등신식.실험결과표명,해산법필배정학、효솔고,차지지재선조작.
