AC经典多模式匹配算法.pdfVIP

AC 经典多模式匹配算法 多模式匹配 AC 算法（ Aho and Corasick ），BM 、Wu-Manber 算法， WM 由 BM 派生，不过 AC 与它们无染，是另外一种匹配思路。 1. 初识 AC 算法 Step1: 将由 patterns 组成的集合（要同时匹配多个 patterns 嘛）构成一个有限 状态自动机。 Step2: 将要匹配的 text 作为自动机输入， 输出含有哪些 patterns 及 patterns 在 全文中位置。 自动机的执行动作由三个部分组成： （1） 一个 goto function （2 ） 一个 failure function （3 ） 一个 output function 我们先通过一个具体实例来了解一下这三个部分，及该自动机的运作方 式。先有个大概印象，后面会具体讲解。 patterns 集合 {he, she, his ,hers} ，我 们要在 ”ushers中查找并匹配。” 第 1 页，共 9 页 文档来源于互联网 |若有侵权联系必删 (1) goto function i 1 2 3 4 5 6 7 8 9 f(i) 0 0 0 1 2 0 3 0 3 （发现没？貌似 i 和 f(i) 有相 同前缀哦 ^_^ ） (2) failure function i output(i) 2 {he} 5 {she,he} 7 {his} 9 {hers} (3) output function 首先我们从状态 0开始，接收匹配字符串的第一个字符 u ，在 goto （简称 goto function ）中可以看到回到状态 0，接着第二个字符 s，发现转到状态 3， 在 output 中查找一下 output(3) 为空字符串，说明没有匹配到 patterns。继续匹 配 h，转到状态 4 ，查找 output 发现仍然没有匹配， 继续字符 e，状态转到了 5， 查找 output ，发现 output(5) 匹配了两个字符串 she 和 he，并输出在整个字符 串中的位置。 然后接着匹配 r ，但发现 g(5,r)=fail ，这时候我们需要查找 failure ， 发现 f(5)=2 ，所以就转到状态 2，并接着匹配 r，状态转移到了 8，接着匹配 s， 状态转移到了 9，查看 output ，并输出 output(9):hers ，记录下匹配位置。至此 字符串 ushers 匹配完毕。 具体的匹配算法如下： 算法 1. Pattern matching machine 输入： text