《字符串匹配算法之AC自动机》课件

字符串匹配算法之自动机AC自动机是一种高效的多模式字符串匹配算法，由和AC AlfredV.Aho于年发明它结合了树和算法的思Margaret J.Corasick1975Trie KMP想，能够在线性时间内同时匹配多个模式串课程目标理解基本原理掌握自动机的核心概念和工作机制，理解它如何高效地解决多模AC式字符串匹配问题掌握构建方法学习自动机的构建步骤和实现技巧，包括树构建、失败指针AC Trie设置和输出函数定义分析算法复杂度深入分析自动机的时间复杂度和空间复杂度，了解其优势和适用AC场景学习优化策略课程大纲1字符串匹配问题概述介绍字符串匹配的基本概念、分类和应用场景，帮助理解研究此类问题的意义和价值2基础算法回顾回顾算法和树的原理和特点，为理解自动机奠定基础KMP Trie AC3自动机原理与构建AC详细讲解自动机的核心思想、组成部分、构建过程和匹配流程AC4代码实现与应用案例展示自动机的代码实现、优化技巧和在实际场景中的应用分析AC字符串匹配问题基本定义字符串匹配是计算机科学中的一个基本问题，给定文本串和模式串，要求找出中所有与匹T PT P配的位置根据模式串的数量，可分为单模式匹配和多模式匹配两类单模式匹配只需查找一个模式串，而多模式匹配则需同时查找多个模式串，这在实际应用中更为常见，也更具挑战性应用场景•网络安全入侵检测、病毒扫描字符串匹配算法分类基于比较的算法基于自动机的算法•暴力匹配逐位比较•自动机多模式匹配BFAC•利用部分匹配信息•后缀自动机所有子串处理KMP•从右向左比较•有限状态自动机正则匹配BM•基于坏字符启发Sunday其他类型算法•基于哈希Rabin-Karp•多模式位移Wu-Manber•后缀树数组特殊数据结构/暴力匹配算法BF时间复杂度空间复杂度，其中为文本串长度，为On*m nm，只需常数空间O1模式串长度不需要额外的辅助空间最坏情况下需要比较次n*m缺点优点效率低下，特别是对于长文本实现简单直观完全不适合多模式匹配场景对于短文本高效算法回顾KMP核心思想利用已匹配信息避免重复比较部分匹配表通过数组保存模式串的前缀信息next时间效率时间复杂度，显著优于暴力匹配On+m算法是一种经典的单模式字符串匹配算法，它通过构建部分匹配表（数组）来记录模式串的前缀信息，从而在匹配失败KMP next时能够利用已知信息快速移动模式串，避免不必要的重复比较虽然算法在单模式匹配中非常高效，但它不适用于多模式匹配场景，这正是自动机要解决的问题理解的思想对学习KMP AC KMP自动机有很大帮助AC树回顾Trie前缀树结构节点表示字符串表示也称字典树，是一种每个节点代表一个字从根节点到标记节点树形数据结构，专门符，从根到任一节点的完整路径表示一个用于高效存储和检索的路径对应一个字符完整的字符串字符串集合串前缀前缀匹配支持快速查找具有相同前缀的所有字符串，是词典和自动补全的理想结构树的基本操作Trie插入字符串从根节点开始，按字符顺序建立路径，标记字符串结束位置时间复杂度，为字符串长度Om m查找字符串从根节点开始，按字符顺序遍历，检查是否存在完整路径时间复杂度，与字符串长度成正比Om删除字符串查找字符串位置，移除标记或删除无用分支时间复杂度，需要特别处理共享前缀情况Om树的优缺点TrieOm26查找效率子节点数仅与字符串长度相关，不受存储字符串总英文字母情况下，每个节点最多有个26数影响子节点OL空间消耗为所有字符串长度之和，最坏情况空间L复杂度较高树具有查找效率高、支持前缀匹配的优点，特别适合需要按前缀匹配的应用场景，Trie如自动补全、拼写检查等然而，它也存在空间消耗大的缺点，尤其在字符集较大时每个节点需要大量指针此外，树本身不支持模式串在文本中的任意位置匹配，无法处理文本流中的多模式Trie匹配问题，这正是需要自动机来解决的问题AC自动机简介AC多模式匹配利器一次扫描即可匹配所有模式串算法结合融合树结构和失败转移思想Trie KMP两阶段处理预处理构建线性扫描匹配+线性时间复杂度，独立于模式串数量On+m+z自动机是一种结合了树和算法思想的多模式匹配算法，其核心优势在于能够在线性时间内完成对多个模式串的同时匹配，AC TrieKMP时间复杂度与模式串数量无关，仅与文本长度、模式串总长度和匹配结果数量有关自动机的核心组成AC树结构Trie自动机的基础架构，用于存储所有的模式串每个节点代表一个字符，从根到节点的路径表示一个前缀这一结构允许我们高效地组织和检索多个模式AC串失败指针当匹配失败时指向的下一个状态，指向具有相同后缀的最长前缀节点失败指针是自动机的关键创新，它类似于算法中的数组，确保了匹配过ACKMP next程的线性时间复杂度输出函数记录当前节点匹配的所有模式串，用于在匹配过程中快速输出结果当到达某个节点时，不仅要考虑当前节点是否是模式串的结束，还要考虑通过失败指针可达的节点自动机构建过程概述AC构建基本的树Trie将所有模式串插入树中，每个节点代表一个字符，并标记模式串的Trie结束节点这一步骤时间复杂度为，即所有模式串长度之和O∑|Pi|构建失败指针使用广度优先搜索，为每个节点构建失败指针失败指针指向BFS具有相同后缀的最长前缀节点，确保在匹配失败时能够跳转到正确的状态继续匹配构建输出函数确定每个节点上可能匹配的所有模式串不仅包括以当前节点结束的模式串，还包括通过失败指针可达节点对应的模式串，这使得匹配过程能够找出所有可能的匹配构建树Trie步骤创建根节点，表示空字符串1root步骤遍历每个模式串，从根节点开始插入2pattern步骤对中的每个字符，检查当前节点是否有标记为的子节点3pattern cc步骤如果没有，创建一个新的子节点；如果有，移动到该子节点4步骤在的最后一个字符对应的节点上，标记为模式串的结束，并存储该模式5pattern串构建树是自动机构建的第一步，也是最基础的一步这一过程非常直观我们将每个模式串按字符顺序插入到树中，并在对应的结束节点上进行标记TrieAC Trie这样构建出的树能够同时包含所有模式串，为后续的失败指针构建和模式匹配奠定基础构建过程的时间复杂度为，即所有模式串长度之和Trie O∑|Pi|失败指针的含义失败指针定义对于树中的节点，其失败指针指向另一个节点，满足从根Trie u v节点到的路径，是从根节点到的路径的最长后缀换句话说，v u v表示的字符串是表示的字符串的最长后缀，且也在树中u vTrie失败指针的核心作用是当当前字符匹配失败时，无需回退到文本起始位置重新匹配，而是跳转到失败指针指向的状态继续尝试匹配失败指针与算法中的数组有着相似的概念，都是为了避KMPnext免在匹配失败时回到起点重新开始通过失败指针，自动机能AC够保证即使在匹配失败的情况下，也能利用已有的信息继续高效匹配，从而实现线性时间复杂度构建失败指针失败指针构建示例第一层-在构建失败指针的第一步中，我们首先处理树的第一层节点，即根节点的直接子节点根据定义，对于这些第一层节点，当匹配失败时，只能回到起Trie点重新开始，因此它们的失败指针都指向根节点具体来说，假设字符集为小写英文字母，根节点可能有最多个子节点对于每个第一层节点，我们设置这一规则简单明了，为后续更26u fail[u]=root复杂层次的失败指针构建奠定了基础在实现中，我们通常使用队列来进行广度优先搜索，首先将所有第一层节点入队，然后逐个处理，设置它们的失败指针并将它们的子节点入队，以此类推失败指针构建示例第二层及以下-1获取父节点失败指针对于节点，首先找到其父节点的失败指针父节点的失败指针在之前的层次中uv已经计算完成2查找对应子节点检查节点是否有与相同字符标记的子节点如果有，则的失败指针应该指向v uw u，因为表示的字符串是表示的字符串的最长后缀w wu3回溯处理如果没有对应的子节点，则继续查找的失败指针，并重复步骤这个过程可能v v2需要多次回溯，直到找到合适的节点或到达根节点4设置指向根节点如果直到根节点都没有找到合适的节点，则将的失败指针设置为指向根节点，表u示完全重新开始匹配输出函数的构建输出函数定义构建方法应用价值输出函数用于记录节点上可能匹配的所在构建失败指针的同时更新输出函数输出函数使得自动机能够在一次扫描AC有模式串对于节点，其输出函数不仅当设置节点的失败指针指向节点时，中找出文本中所有与任何模式串匹配的u uv包括以结束的模式串，还包括通过沿着如果的输出函数非空，则将的输出函位置，是多模式匹配的关键特性在实uvv失败指针可达的所有节点上的模式串数中的所有模式串添加到的输出函数现中，通常使用链表或集合来存储每个u中节点的输出函数构建过程完整示例模式串集合树构建Trie插入所有模式串，标记结束节点{he,she,his,hers}输出函数构建失败指针构建结合失败指针更新每个节点的输出函使用按层次计算每个节点的失败BFS数指针以模式串集合为例，我们首先构建包含这些模式串的树然后使用计算失败指针根节{he,she,his,hers}Trie BFS点的失败指针为；第一层节点和的失败指针指向根；对于的子节点，查找根节点是否有子节点，没有则指向NULL h s he e根；对于的子节点，其失败指针指向已有的节点，依此类推s hh自动机匹配过程AC初始状态从树的根节点开始，准备读取文本Trie读取字符逐个读取文本串中的字符，尝试沿树转移Trie状态转移如无法直接转移，沿失败指针继续尝试输出结果检查当前节点输出函数，记录匹配结果自动机的匹配过程是一个线性扫描的过程我们从树的根节点开始，依次读取文AC Trie本串中的每个字符对于每个字符，尝试在当前状态下进行转移如果无法直接转移（即当前节点没有对应字符的子节点），则沿着失败指针继续尝试，直到能够转移或回到根节点匹配示例文本-ushers位置当前字当前状下一状失败转输出符态态移根无根无0u根无需无1s s无需无2hs sh无需3e shshe she无无4r shehe无根无5s he-s让我们详细跟踪自动机在文本中的匹配过程开始时，当前状态AC ushers是根节点对于第一个字符，根节点没有对应的子节点，状态保持在根节点u对于第二个字符，找到了对应的子节点，状态转移到节点ss自动机的时间复杂度分析AC构建树构建失败指针Trie遍历每个模式串，将其插入使用按层次计算每个节点的Trie BFS树失败指针时间复杂度，即所有时间复杂度O∑|Pi|O∑|Pi|模式串长度之和每个节点的失败指针计算需要常这一步骤的时间与模式串的数量数次操作，节点总数与模式串总和长度成正比长度相关匹配过程线性扫描文本串，沿树进行状态转移Trie时间复杂度，为文本长度，为匹配结果数On+z nz每个字符最多被检查常数次，总体时间与文本长度和输出规模成正比自动机的空间复杂度分析AC树空间失败指针空间Trie，存储所有模式串的节点，每个节点一个失败指针O∑|Pi|O∑|Pi|总空间复杂度输出函数空间，与模式串总长度成正比，存储所有可能的匹配结果O∑|Pi|O∑|Pi|自动机的空间复杂度主要来自三个部分树结构、失败指针和输出函数树需要存储所有模式串的节点，每个节点ACTrieTrie还需要额外的空间来存储失败指针和可能的输出结果总体来看，空间复杂度与所有模式串的长度之和成正比自动机的代码实现框架ACclass AhoCorasick{//节点结构struct Node{Map children;Node*fail;vector outputs;Node:failnullptr{}};Node*root;//构建Trie树void buildTrievectorpatterns;//构建失败指针void buildFailPointers;//构建输出函数void buildOutputFunction;//进行匹配vector matchstringtext;public:AhoCorasickvector patterns{root=new Node;buildTriepatterns;buildFailPointers;}vector searchstringtext{return matchtext;}};数据结构定义节点属性说明存储当前节点的所有子节点，通常使用哈希children表或数组实现指向当前节点的失败指针，表示匹配失败时fail应转移到的状态标记当前节点是否是某个模式串的结束isEnd存储当前节点匹配的所有模式串的索引outputs可选属性，表示从根到当前节点的深度，用depth于确定匹配位置在自动机的实现中，节点结构是最基础的组成部分每个节点至少需要三个关键属性AC用于构建树结构，存储失败指针，记录匹配的模式串根据具体需求，children Triefail outputs还可以添加其他辅助属性，如深度、字符值等节点结构的设计直接影响自动机的性能和内存消耗在实际应用中，可以根据字符集大小和内AC存限制选择适当的实现方式，例如对于小字符集可以使用固定大小的数组，对于大字符集则使用哈希表。