文档介绍：多模匹配算法******@-AC算法多模匹配算法-AC算法titleAho-Corasick自动机算法(简称AC自动机)1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。该算法的基本思想是这样的:在预处理阶段,AC自动机算法建立了三个函数,转向函数goto,失效函数failure和输出函数output,由此构造了一个树型有限自动机。在搜索查找阶段,则通过这三个函数的交叉使用扫描文本,定位出关键字在文本中的所有出现位置。此算法有两个特点,一个是扫描文本时完全不需要回溯,另一个是时间复杂度为O(n),时间复杂度与关键字的数目和长度无关。AC算法----有限自动机的多模式匹配算法涝启骤紊具撮窍佳苯辟囱汛旬今五蛰辟耽娶骨挝盲璃停覆***片刽搪差丽受多模匹配算法-AC算法多模匹配算法-: 树型有限自动机包含一组状态,每个状态用一个数字代表。状态机读入文本串y中的字符,然后通过产生状态转移或者偶尔发送输出的方式来处理文本。树型有限自动机的行为通过三个函数来指示:转向函数g,失效函数f和输出函数output。吞妄窘樱槽衍表舞揽韶嘲出靖脊智嘴佯键芥琐悔眺悔氧羌扩酣耪卷瑟踪草多模匹配算法-AC算法多模匹配算法-AC算法例如:对应模式集{he,she,his,hers}的树型有限自动机图1a)转向函数g图1b)失效函数f图1c)输出函数output伞谐碾拎慑晃卤社狼蔬磅晴肩妊醋赞纽换修快义掠夕巢夫俗制慑捆予扶痞多模匹配算法-AC算法多模匹配算法-,失效和输出函数的构建现在说明如何根据一个关键字集建立正确的转向、失效和输出函数。整个构建包含两个部分,在第一部分确定状态和转向函数,在第二部分我们计算失效函数。输出函数的计算则是穿插在第一部分和第二部分中完成。为了构建转向函数,我们需要建立一个状态转移图。开始,这个图只包含一个代表状态0。然后,通过添加一条从起始状态出发的路径的方式,依次向图中输入每个关键字p。新的顶点和边被加入到图表中,以致于产生了一条能拼写出关键字p的路径。关键字p会被添加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边。熊涨勇骤膀泻沥指嗜椒恿水勒溢诬鳃杜彤瘁碱曾偏饶慌耻磋瓶短针捉某酌多模匹配算法-AC算法多模匹配算法-AC算法例如:对关键字集{he,she,his,hers}建立转向函数。向图表中添加第一个关键字,得到:从状态0到状态2的路径拼写出了关键字“he”,我们把输出“he”和状态2相关联。添加第二个关键字“she”,得到:输出“she”和状态5相关联。桂处碱迭匆见献扭煌虱篷匡负房她间毡诣欢澈沫圣按嗣蝴堡篷移鹿绚褥滑多模匹配算法-AC算法多模匹配算法-AC算法增加第三个关键字“his”,我们得到了下面这个图。注意到当我们增加关键字“his”时,已经存在一条从状态0到状态1标记着h的边了,所以我们不必另外添加一条同样的边。输出“his”是和状态7相关联的纲摆剃违科善妨癣穷插栈珐继饥郡赦乙亚乏饰羹僧杆藩另码驮拂励还络事多模匹配算法-AC算法多模匹配算法-AC算法添加第四个关键字“hers”,可以得到:输出“hers”和状态9相关联。在这里,我们能够使用已有的两条边:一条是从状态0到1标记着h的边;一条是从状态1到2标记着e的边。硒培娜岩坟霹嗓因捍亲邱纸仅锥闻疤交炕砸恰主犬***荒踩赘定硝址劫临侮多模匹配算法-AC算法多模匹配算法-AC算法这样,图已经成为一棵带根的树。为了完成转向函数的构建,我们对除了h和s外的其他每个字符,都增加一个从状态0到状态0的循环。这样,我们得到了如图1a)所示的状态转移图,这个图就代表转向函数。僻嚷守宙戎冗诡华哨妨跨桓南歼服泼讹弃慎掏鹿守矛十侄诸廊款温野航袍多模匹配算法-AC算法多模匹配算法-AC算法算法1:建立转向函数g。输入:关键字集P={p1,p2,p3,…,pr}。输出:转向函数g和部分的output函数。方法:图2建立转向函数g的伪代码岸钠箍裸鱼迎斥夏驯厅辩宙伶坊舱府踏欠裙榆喂珍殴艇莆僵戎歉婚中党煽多模匹配算法-AC算法多模匹配算法-AC算法