ac自动机算法详解,

　　00-1010工作流程介绍数据结构初始化构造字典树构造失败指针匹配执行结果

　　00-1010AC自动机是一种多模式匹配算法，广泛应用于模式匹配领域。举一个经典的例子，被禁止的词被搜索并替换为* * *。AC自动机实际上是Trie树和KMP算法的结合。首先为多模式字符串建立一棵轮胎树，然后通过KMP算法的前缀和后缀匹配来减少不必要的比较，从而高效地在字符串中找到匹配的字符串。

　　如果不知道什么是轮胎树，可以先查一下：详细讲解一下字典树(Trie tree)在Java中的图解和实现。

　　如果你不知道KMP算法，可以先看看：用Java详细讲解KMP算法的图解和实现。

　　00-1010首先看交流自动机的结构。从造型上看，和我们之前说的轮胎树差不多，只是有一条红线(这里因为画的太乱所以没有画完)。这条红线被称为故障指针。匹配规则和KMP一样，不同的是KMP匹配同一个模式串的前缀和后缀，这里是当前模式串的后缀，匹配另一个模式串的前缀。如果能匹配，因为这两个模式串的前缀肯定是不一样的(相同的前缀已经聚合了)，所以把当前匹配的后缀拿出来，比如abo，后缀是O，bo，abo。这时我们会找到另一个模式串的最长前缀来匹配当前后缀(对应kmp中最长的前缀后缀子串)，然后我们就可以找出O，那么about中O节点的失效指针就指向out的O节点，也就是说主串可以一直比较，不需要回溯(比如之前匹配过的ab已经失效到O了，其他匹配的字符串不能有ab前缀，就没有必要再匹配了，肯定是失败的)。

　　构建过程：构建一棵轮胎树，结束节点需要标记当前模式串的长度，以及构建失败指针。

　　搜索过程：从根节点开始，查找当前节点的子节点是否有与当前字符匹配的字符，如果匹配，则判断是否为尾节点，如果匹配成功，则记录。不，尾节点继续匹配。如果没有子节点匹配该字符，直接转到失败指针继续操作。

　　00-1010 A值记录当前节点的值，childNode记录当前节点的子节点(假设只出现26个小写字母，存在空间浪费，可以使用哈希表、有序二进制、跳转表进行优化)。isTail标记当前节点是否为尾节点，failNode表示失败指针，即当前节点的子节点与当前字符不匹配时，转到哪个节点继续匹配，tailLength，记录模式串的长度，以便快速取出模式串的值(根据长度和匹配索引从主串中取出)。

　　publistaticlassnode {//当前节点值privatecharvalue//当前节点的子节点，private node[]child node；//标记当前节点是否为单词privatebooleanisTail的结尾；//失败指针privateNodefailNode//匹配字符串的长度，当isTail==true时，表示从root开始的当前位置是一个完整的匹配字符串。记录下这个匹配字符串的长度，以便以后快速找到匹配字符串privateIntegertailLengthpublic node(char value){ this . value=value；} }

　　00-1010仅用根初始化根节点。根的失败指针和长度为空。

　　Noderootpublicfoidinit(){ root=new node( 0 )；root . child node=new node[26]；}

　　00-1010这个过程之前在轮胎树里已经描述过了，这里就不赘述了。唯一不同的是，当前模式字符串的长度需要标记在结束节点上。

　　public insertstr(char[]chars){//首先判断第一个字符是否已经在字典树中，然后判断第二个字符，依次进行判断。找到第一个不存在的字符，插入子节点Nodep=root//指示当前正在处理哪个字符intchIndex=0；while(chindex chars . length){ while(chindex chars . length null！=p){ Node[]children=p . child Node；booleanfi

　　nd = false;               for (Node child : children) {                   if (null == child) {continue;}                   if (child.value == chars[chIndex]) {                       //当前字符已经存在，不需要再进行存储                       //从当前节点出发，存储下一个字符                       p = child;                       ++ chIndex;                       find = true;                       break;                  }              }               if (Boolean.TRUE.equals(find)) {                   //在孩子中找到了 不用再次存储                   break;              }               //如果把孩子节点都找遍了，还没有找到这个字符，直接将这个字符加入当前节点的孩子节点               Node node = new Node(chars[chIndex]);               node.childNode = new Node[26];               children[chars[chIndex] - a] = node;               p = node;               ++ chIndex;          }      }       //字符串中字符全部进入tire树中后，将最后一个字符所在节点标志为结尾节点       p.isTail = true;       p.tailLength = chars.length;  }

构建失败指针

从根节点开始层序遍历树结构，构建失败指针。一个节点的子节点的失败指针可以根据当前节点的失败指针得到，因为我们是用后缀去与前缀匹配，所以如果我们采用层序遍历，与当前后缀的前缀一定在上层，已经匹配出来了。那么当前节点的子节点的失败指针则可以根据当前节点的失败指针，查找失败指针指向的节点的子节点是否有与当前节点的子节点相等的，相等则这个子节点的失败指针直接指向，不相等则继续找，找不到直接指向root。根据上面的图，我们来举一个例子，我们已经找到about中o节点（o1）的失败指针是out中的o节点（o2），接下来我们怎么找u（u1）的失败指针呢？首先根据o1的失败指针我们找到了o2，o2的子节点为u（u2），恰好与我们u1的值相等，此时我们就可以将u1的失败指针指向u2。以此类推，如果访问到最后为空（root的失败指针为空），则直接将失败指针指向root。

public void madeFailNext() {       //层序遍历，为了保证求解这个节点失败指针的时候，它的父节点的失败指针以及失败指针的失败指针。。。。已经求得，可以完全根据这个找       Deque<Node> nodes = new LinkedList<>();       nodes.add(root);       while (!nodes.isEmpty()) {           Node current = nodes.poll();           Node[] children = current.childNode;           for (Node child : children) {               if (null == child) {                   continue;              }               Node failNode = current.failNode;               while (null != failNode) {                   //找到当前节点的失败指针，查看失败指针子节点是否有==                   Node[] failChildren = failNode.childNode;                   Node node = failChildren[child.value - a];                   if (null == node) {                       //找当前指针的下一个指针                       failNode = failNode.failNode;                       continue;                  }                   //已经找到匹配的                   //将失败指针指向node                   child.failNode = node;                   break;              }               //如果找完还没有找到，指向root               if (null == failNode) {                   child.failNode = root;              }               nodes.add(child);          }      }  }

匹配

从首字符，字典树从root节点开始进行匹配，如果字符与节点值匹配，则判断是否为尾字符，如果是匹配上一个违禁词，记录下来，如果不匹配则转移到失败指针继续进行匹配。

/**    * 匹配出str中所有出现的关键词    * @param str    * @return    */   public List<String> match(String str) {       //遍历当前子串串，从根节点出发，如果匹配就一直往下进行匹配，同时需要看匹配的节点是否为结尾节点，如果是，匹配上一个       //如果不匹配则通过失败指针转移到下一个节点       this.dfs(root, 0, str);       return machStr;  }   //abcdeasdabcebcd   List<String> machStr = new ArrayList<>();   private void dfs(Node node, int chIndex, String chars) {       if (chIndex >= chars.length()) {           return;      }       //从将当前字符与当前node的孩子节点进行匹配，如果当前字符与node的孩子节点.value匹配，判断当前字符是否为尾节点，是，则记录，匹配到了一个       //继续匹配（子节点，与下一个元素进行匹配）       //如果不匹配，则转到失败指针       Node[] children = node.childNode;       Node child = children[chars.charAt(chIndex) - a];       if (null == child) {           //不匹配，转到失败指针           //如果当前node==root，从root匹配，root的失败指针是null           if (node == root) {               dfs(root, ++ chIndex, chars);          } else {               dfs(node.failNode, chIndex, chars);          }      } else {           //匹配到了           if (child.isTail) {               //并且是结尾节点，取从child.value到child.tailLength的字符               machStr.add(chars.substring(chIndex - child.tailLength  + 1, chIndex + 1));          }           dfs(child, ++ chIndex, chars);      }  }

执行结果

public static void main(String[] args) {       ACAutomaton acAutomaton = new ACAutomaton();       //初始化一个仅有根节点的字典树       acAutomaton.init();       //构建Tire树       acAutomaton.insertStr("out".toCharArray());       acAutomaton.insertStr("about".toCharArray());       acAutomaton.insertStr("act".toCharArray());       //构建失败指针       acAutomaton.madeFailNext();       System.out.println("ces");       //匹配       List<String> result = acAutomaton.match("abcdeasactdaboutcebcd");  }

　　到此这篇关于详解Java中AC自动机的原理与实现的文章就介绍到这了,更多相关Java AC自动机内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。