［数据结构］AC自动机和A*搜索算法简单概述

「爱情、让人受尽委屈。」 2022-03-10 11:28 129阅读 0赞

玩吃鸡－＞谩骂词语->会变成\*\*\*\*－＞如何实现的？

实际上，这些功能最基本的原理就是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容之后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“\*\*\*”把它替代掉。

我们前面讲过好几种字符串匹配算法了，它们都可以处理这个问题。但是，对于访问量巨大的网站来说，比如淘宝，用户每天的评论数有几亿、甚至几十亿。这时候，我们对敏感词过滤系统的性能要求就要很高。毕竟，我们也不想，用户输入内容之后，要等几秒才能发送出去吧？我们也不想，为了这个功能耗费过多的机器吧？**那如何才能实现一个高性能的敏感词过滤系统呢**？这就要用到今天的**多模式串匹配算法**。

###### 前言：基于单模式串和 Trie 树实现的敏感词过滤 ######

我们前面几节讲了好几种字符串匹配算法，有 BF 算法、RK 算法、BM 算法、KMP 算法，还有 Trie 树。前面四种算法都是单模式串匹配算法，只有 Trie 树是多模式串匹配算法。

*  单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。
 *  多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

尽管，单模式串匹配算法也能完成多模式串的匹配工作。例如开篇的思考题，我们可以针对每个敏感词，通过单模式串匹配算法（比如 KMP 算法）与用户输入的文字内容进行匹配。但是，这样做的话，**每个匹配过程都需要扫描一遍用户输入的内容。整个过程下来就要扫描很多遍用户输入的内容**．如果敏感词很多，比如几千个，并且用户输入的内容很长，假如有上千个字符，那我们就需要扫描几千遍这样的输入内容。很显然，这种处理思路比较低效。

与单模式匹配算法相比，**多模式匹配算法在这个问题的处理上就很高效了。它只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在**，从而大大提高匹配效率。我们知道，Trie 树就是一种多模式串匹配算法。那如何用 Trie 树实现敏感词过滤功能呢？

我们可以对敏感词字典进行预处理，构建成 Trie 树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，那我们只需要动态更新一下 Trie 树就可以了。

当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是**从字符 C 的下一个字符开始，重新在 Trie 树中匹配。**

基于 Trie 树的这种处理方法，有点类似单模式串匹配的 BF 算法。我们知道，单模式串匹配算法中，KMP 算法对 BF 算法进行改进，**引入了 next 数组，让匹配失败时，尽可能将模式串往后多滑动几位。借鉴单模式串的优化改进方法，能否对多模式串 Trie 树进行改进，进一步提高 Trie 树的效率呢？这就要用到 AC 自动机算法了。**

# 1.经典的多模式串匹配算法：AC 自动机 #

AC 自动机算法，全称是 Aho-Corasick 算法。其实，Trie 树跟 AC 自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟 KMP 算法之间的关系一样，只不过前者针对的是多模式串而已。所以，**`AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了`**。如果代码表示，就是下面这个样子：

public class AcNode { 
      public char data; 
      public AcNode[] children = new AcNode[26]; // 字符集只包含 a~z 这 26 个字符
      public boolean isEndingChar = false; // 结尾字符为 true
      public int length = -1; // 当 isEndingChar=true 时，记录模式串长度
      public AcNode fail; // 失败指针
      public AcNode(char data) { 
        this.data = data;
      }
    }

所以，AC 自动机的构建，包含两个操作：

*  将多个模式串构建成 Trie 树；
 *  在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

这里假设已经知道了失败指针的计算！！！

所以之后就会通过失败指针向前滑动尽可能多的距离啦！！！

时间复杂度：O(n\*要做匹配的字符串的长度)

--------------------

魔兽世界、仙剑奇侠传这类 MMRPG 游戏，不知道你有没有玩过？在这些游戏中，有一个非常重要的功能，那就是人物角色自动寻路。当人物处于游戏地图中的某个位置的时候，我们用鼠标点击另外一个相对较远的位置，人物就会自动地绕过障碍物走过去。玩过这么多游戏，不知你是否思考过，这个功能是怎么实现的呢？

实际上，这是一个非常典型的搜索问题。人物的起点就是他当下所在的位置，终点就是鼠标点击的位置。我们需要在地图中，找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物，并且看起来要是一种非常聪明的走法。所谓“聪明”，笼统地解释就是，走的路不能太绕。理论上讲，最短路径显然是最聪明的走法，是这个问题的最优解。

不过，如果图非常大，那 Dijkstra 最短路径算法的执行耗时会很多。在真实的软件开发中，我们面对的是超级大的地图和海量的寻路请求，算法的执行效率太低，这显然是无法接受的。

实际上，像出行路线规划、游戏寻路，这些真实软件开发中的问题，一般情况下，我们都**不需要非得求最优解（也就是最短路径**）。在权衡路线规划质量和执行效率的情况下，我们只需要**寻求一个次优解就足够了。那如何快速找出一条接近于最短路线的次优路线呢？ 这个快速的路径规划算法，就是我们今天要学习的A\* 算法**

# A\* 搜索算法 #

A\* 算法就是对 Dijkstra 算法的简单改造。实际上，代码实现方面，我们也只需要稍微改动几行代码，就能把 Dijkstra 算法的代码实现，改成 A\* 算法的代码实现。

跟 Dijkstra 算法的代码实现，主要有 3 点区别：

*  优先级队列构建的方式不同。A\* 算法是根据 f 值（也就是刚刚讲到的 f(i)=g(i)+h(i)）来构建优先级队列，而 Dijkstra 算法是根据 dist 值（也就是刚刚讲到的 g(i)）来构建优先级队列；
 *  A\* 算法在更新顶点 dist 值的时候，会同步更新 f 值；
 *  循环结束的条件也不一样。Dijkstra 算法是在终点出队列的时候才结束，A\* 算法是一旦遍历到终点就结束。

### 重点： ###

*  Dijkstra　　回溯+DP

> Dijkstra 算法在此基础之上，利用动态规划的思想，对回溯搜索进行了剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但它**实际上也考察到了所有从起点到终点的路线，所以才能得到最优解**。

*  A\* 　　　单纯贪心

> A\* 算法利用贪心算法的思路，每次都找 f 值最小的顶点出队列，**一旦搜索到终点就不在继续考察其他顶点和路线了**。所以，它并没有考察所有的路线，也就不可能找出最短路径了。

##### 实例：利用A\*算法实现游戏寻路的问题 #####

把整个地图分割成一个一个的小方块。在某一个方块上的人物，只能往上下左右四个方向的方块上移动。我们可以把每个方块看作一个顶点。两个方块相邻，我们就在它们之间，连两条有向边，并且边的权值都是 1。所以，这个问题就转化成了，在一个有向有权图中，找某个顶点到另一个顶点的路径问题。将地图抽象成边权值为 1 的有向图之后，我们就可以套用 A\* 算法，来实现游戏中人物的自动寻路功能了。

有障碍物就不进行连线即可

A\* 算法属于一种启发式搜索算法（Heuristically Search Algorithm）。实际上，启发式搜索算法并不仅仅只有 A\* 算法，还有很多其他算法，比如 IDA\* 算法、蚁群算法、遗传算法、模拟退火算法等。如果感兴趣，你可以自行研究下。

参考：极客时间－数据结构与算法之美