计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2013年
12期
2699-2706
,共8页
串匹配%多模式%自动机%失败函数%高级AC
串匹配%多模式%自動機%失敗函數%高級AC
천필배%다모식%자동궤%실패함수%고급AC
string matching%multi-patterns%automaton%failure function%advanced AC
高级AC(advanced AC,AAC)是一种基于自动机的多模式串匹配算法,应用极为广泛.在大规模匹配时AAC自动机构建耗时较大,改进了经典精确单模式匹配算法——DFA算法自动机构建过程,并将其扩展到多模式匹配领域,提出Set DFA自动机,并证明Set DFA自动机和AAC自动机一致.该自动机构建方法简单清晰,无需计算失败函数,自动机内每个状态在生成后只需访问一次即可完成自动机构建.实验表明Set DFA构建时间只有AAC自动机的一半左右.
高級AC(advanced AC,AAC)是一種基于自動機的多模式串匹配算法,應用極為廣汎.在大規模匹配時AAC自動機構建耗時較大,改進瞭經典精確單模式匹配算法——DFA算法自動機構建過程,併將其擴展到多模式匹配領域,提齣Set DFA自動機,併證明Set DFA自動機和AAC自動機一緻.該自動機構建方法簡單清晰,無需計算失敗函數,自動機內每箇狀態在生成後隻需訪問一次即可完成自動機構建.實驗錶明Set DFA構建時間隻有AAC自動機的一半左右.
고급AC(advanced AC,AAC)시일충기우자동궤적다모식천필배산법,응용겁위엄범.재대규모필배시AAC자동궤구건모시교대,개진료경전정학단모식필배산법——DFA산법자동궤구건과정,병장기확전도다모식필배영역,제출Set DFA자동궤,병증명Set DFA자동궤화AAC자동궤일치.해자동궤구건방법간단청석,무수계산실패함수,자동궤내매개상태재생성후지수방문일차즉가완성자동궤구건.실험표명Set DFA구건시간지유AAC자동궤적일반좌우.
