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) 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匹配完毕。
Read full article from Aho-Corasick自动机算法原理与详解-colwater-ChinaUnix博客
No comments:
Post a Comment