极客时间-数据结构与算法之美（五）_针对微博用户关系,假设我们需要支持下面这样几个操作:判断用户 a 是否关注了用户

30 | 图的表示：如何存储微博、微信等社交网络中的好友关系？

如何理解“图”？

图（Graph）和树比起来，这是一种更加复杂的非线性表结构。

树中的元素称为节点，图中的元素叫作顶点（vertex）。图中的一个顶点可以与任意其他顶点建立连接关系。这种建立的关系叫作边（edge）。

社交网络，就是非常典型的图结构。拿微信举例子。把每个用户看作一个顶点。如果两个用户之间互加好友，那就在两者之间建立一条边。所以，整个微信的好友关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中，就叫作顶点的度（degree），就是跟顶点相连接的边的条数。

实际上，微博的社交关系跟微信还有点不一样。微博允许单向关注，那如何用图来表示这种单向的社交关系呢？

边有方向的图叫作“有向图”。以此类推，边没有方向的图就叫作“无向图”。

无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，度分为入度（In-degree）和出度（Out-degree）。

顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。对应到微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。

QQ 中的社交关系要更复杂的一点。QQ 不仅记录了用户之间的好友关系，还记录了两个用户之间的亲密度，如果两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。如何在图中记录这种好友关系的亲密度呢？

这里就要用到另一种图，带权图（weighted graph）。在带权图中，每条边都有一个权重（weight），可以通过这个权重来表示 QQ 好友间的亲密度。

邻接矩阵存储方法

图最直观的一种存储方法就是，邻接矩阵（Adjacency Matrix）。

邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i] [j] 和 A[j] [i] 标记为 1；对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i] [j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j] [i] 标记为 1。对于带权图，数组中就存储相应的权重。

 

用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。

对于无向图来说，如果 A[i] [j] 等于 1，那 A[j] [i] 也肯定等于 1。实际上，只需要存储一个。也就是说，无向图的二维数组中，如果将其用对角线划分为上下两部分，那只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了。

如果存储的是稀疏图，也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但是每个用户的好友并不会很多，一般也就三五百个而已。如果用邻接矩阵来存储，那绝大部分的存储空间都被浪费了。

邻接矩阵的存储方法的优点。首先，邻接矩阵的存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。其次，用邻接矩阵存储图的另外一个好处是方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。比如求解最短路径问题时会提到一个Floyd-Warshall 算法，就是利用矩阵循环相乘若干次得到结果。

邻接表存储方法

邻接表有点像散列表，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。对于有向图，每个顶点对应的链表里面，存储的是指向的顶点。对于无向图来说，也是类似的，不过，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。

邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比较耗时间。

如果要确定，是否存在一条从一个顶点到另一个顶点的边，那我们就要遍历这个顶点对应的那条链表，看链表中是否存在另一个顶点。而且，链表的存储方式对缓存不友好。所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。

在基于链表法解决冲突的散列表中，为了提高查找效率，将链表换成其他更加高效的数据结构，比如平衡二叉查找树等。邻接表长得很像散列。所以，也可以将邻接表同散列表一样进行“改进升级”。

可以将邻接表中的链表改成平衡二叉查找树。实际开发中，可以选择用红黑树。这样，就可以更加快速地查找两个顶点之间是否存在边了。这里的二叉查找树可以换成其他动态数据结构，比如跳表、散列表等。还可以将链表改成有序动态数组，通过二分查找来快速定位两个顶点之间否是存在边。

如何存储微博、微信等社交网络中的好友关系？

微博、微信是两种“图”，前者是有向图，后者是无向图。两者的解决思路差不多，拿微博来讲解。

针对微博用户关系，假设需要支持下面这样几个操作：

• 判断用户 A 是否关注了用户 B；

• 判断用户 A 是否是用户 B 的粉丝；

• 用户 A 关注用户 B；

• 用户 A 取消关注用户 B；

• 根据用户名称的首字母排序，分页获取用户的粉丝列表；

• 根据用户名称的首字母排序，分页获取用户的关注列表。

因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间。所以采用邻接表来存储。

查找某个用户关注了哪些用户非常容易，但是如果要想知道某个用户都被哪些用户关注了，也就是用户的粉丝列表，是非常困难的。

基于此，需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。如果要查找某个用户关注了哪些用户，可以在邻接表中查找；如果要查找某个用户被哪些用户关注了，从逆邻接表中查找。

选择改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。

因为需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构很合适。因为跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。

如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，可以将整个社交关系存储在内存中。但是如果像微博那样有上亿的用户，数据规模太大，就无法全部存储在内存中了。

可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。当要查询顶点与顶点关系的时候，就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。

除此之外，还有另外一种解决思路，就是利用外部存储（比如硬盘），因为外部存储的存储空间要比内存会宽裕很多。数据库是经常用来持久化存储关系数据的。

关于图，需要理解这样几个概念：无向图、有向图、带权图、顶点、边、度、入度、出度。图的两个主要的存储方式：邻接矩阵和邻接表。

邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。

课后思考

1. 关于开篇思考题，像微信这种无向图，应该怎么存储呢？

   • 微信好友关系存储方式。无向图，也可以使用邻接表的方式存储每个人所对应的好友列表。为了支持快速查找，好友列表可以使用红黑树存储。

   • 微信社交关系的存储方式

     因为顶点的数量大且关系相对少，所以不适合用邻接矩阵来存储，应该用邻接表来存储。

     微信社交关系的相关操作：1. 判断A、B是否为好友关系 2. A删除B，断开与B的好友关系 3. 展示出A的所有好友，并按名称首字母进行排序

     因为微信的好友关系是稀疏矩阵，为了减少空间浪费，使用邻接表；为了提高查找效率，将邻接表中的链表改为支持快速查找的动态数据结构，这里使用红黑树、跳表都可以，考虑到好友列表是按照字母排序的，可以使用跳表。最后，若有n台机器可供使用，那么可以对n取余来划分这些数据到不同的机器上，毕竟微信的用户量太大，一个机器的内存应该是不够用的。

2. 除了社交网络可以用图来表示之外，符合图这种结构特点的例子还有很多，比如知识图谱（Knowledge Graph）。关于图这种数据结构，你还能想到其他生活或者工作中的例子吗？

   • 生活工作中应用图的例子。很多，互联网上网页之间通过超链接连接成一张有向图；城市乃至全国交通网络是一张加权图；人与人之间的人际关系够成一张图，著名的六度分割理论据说就是基于这个得到的。

   • 图的例子还有：操作系统的资源分配图是有向图，用来分析死锁问题。

   • 解决现实问题的时候当存储图有多种选择，例如: 1.用邻接表自己存 2.关系型库 3.图数据库 1 内存中用邻接表 2 要持久化存储就用数据库 3 超大图 并且涉及大量图计算。用专业的图数据库

31 | 深度和广度优先搜索：如何找出社交网络中的三度好友关系？

什么是“搜索”算法？

深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。

图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。具体方法有很多，比如两种最简单、最“暴力”的深度优先、广度优先搜索，还有 A* 、IDA* 等启发式搜索算法。

图有两种主要存储方法，邻接表和邻接矩阵。

深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上。

public class Graph { // 无向图
private int v; // 顶点的个数
private LinkedList<Integer> adj[]; // 邻接表
public Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i) {
adj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t) { // 无向图一条边存两次
adj[s].add(t);
adj[t].add(s);
}
}
​

广度优先搜索（BFS）

广度优先搜索（Breadth-First-Search），简称为 BFS。它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。这样求得的路径就是最短路径。

public void bfs(int s, int t) {
if (s == t) return;
boolean[] visited = new boolean[v];
visited[s]=true;
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
while (queue.size() != 0) {
int w = queue.poll();
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
if (q == t) {
print(prev, s, t);
return;
}
visited[q] = true;
queue.add(q);
}
}
}
}
private void print(int[] prev, int s, int t) { // 递归打印 s->t 的路径
if (prev[t] != -1 && t != s) {
print(prev, s, prev[t]);
}
System.out.print(t + " ");
}
​

visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。

queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，用这个队列来实现记录的功能。

prev用来记录搜索路径。当从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w] 存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，通过顶点 2 的邻接表访问到顶点 3，那 prev[3] 就等于 2。为了正向打印出路径，需要递归地来打印。

最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。

广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。

深度优先搜索（DFS）

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。

假设站在迷宫的某个岔路口，然后想找到出口。随意选择一个岔路口来走，发现走不通的时候，就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这就是一种深度优先搜索策略。

如何在图中应用深度优先搜索，来找某个顶点到另一个顶点的路径。深度优先搜索找出来的路径，并不是最短路径。

实际上，深度优先搜索用的是回溯思想，非常适合用递归来实现。

深度优先搜索代码实现里，found的作用是，当已经找到终止顶点 t 之后，就不再递归地继续查找了。

boolean found = false; // 全局变量或者类成员变量
public void dfs(int s, int t) {
found = false;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
recurDfs(s, t, visited, prev);
print(prev, s, t);
}
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found == true) return;
visited[w] = true;
if (w == t) {
found = true;
return;
}
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
recurDfs(q, t, visited, prev);
}
}
}
​

每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。

深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。

课后思考

如何找出社交网络中某个用户的三度好友关系？

这个问题适合用图的广度优先搜索算法来解决，因为广度优先搜索是层层往外推进的。首先，遍历与起始顶点最近的一层顶点，也就是用户的一度好友，然后再遍历与用户距离的边数为 2 的顶点，也就是二度好友关系，以及与用户距离的边数为 3 的顶点，也就是三度好友关系。用一个数组来记录每个顶点与起始顶点的距离，就可以找出三度好友关系。

广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，也被叫作暴力搜索算法。所这两种搜索算法仅适用于状态空间不大，也就是图不大的搜索。

广度优先搜索，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，适合用递归实现，深度优先搜索是借助栈来实现的。深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。

课后思考

1. 通过广度优先搜索算法解决了开篇的问题，能否用深度优先搜索来解决呢？

   • 可以。DFS递归时传多一个离初始节点的距离值，访问节点时，距离超过3的不再继续递归

   • 深度优先用于寻找3度好友，可以设定搜索的深度，到3就向上回溯。正如文中提到的，可能不是最短路径，所以会涉及到更新结点度的问题。

   • 可以用深度遍历，每次遍历到三度人脉，再回溯到上层节点，直到所有的三度人脉都找完。

2. 今天的内容中提到，迷宫可以抽象成图，走迷宫可以抽象成搜索算法，你能具体讲讲，如何将迷宫抽象成一个图吗？或者换个说法，如何在计算机中存储一个迷宫？

   • 初始化两个顶点为迷宫起点和终点，从起点开始，遇到分叉点，为每个分支都新建一个节点，并和前一节点连接，递归每个分支直到终点

   • 关于迷宫存储问题。类似于欧拉七桥问题，需要将迷宫抽象成图，每个分叉路口作为顶点，顶点之间连成边，构成一张无向图，可以存储在邻接矩阵或邻接表中。

   • 迷宫，选一个入口作为起始顶点，遇到岔路口，将岔路口作为顶点，并建立连接关系（边），终止条件应该是：到出口 或者 到下一个路口之后不能再前进为止。这里仍然用深度优先搜索的方法实现。

   • 将迷宫的每个岔口记为"顶点"，岔口之间的路径记为"边"，可以用邻接表存储，也可以用邻接矩阵存储。但是个人感觉，像那种标准的方格迷宫，适合用邻接矩阵存储，因为稠密度比较高。

老师的图如果看不懂，可以看看这个图的基本算法（BFS和DFS） - 简书

32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？

RK 算法是 BF 算法的改进，那RK 算法是如何借助哈希算法来实现高效字符串匹配的呢？

BF 算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

主串和模式串。比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。主串的长度记作 n，模式串的长度记作 m。因为是在主串中查找模式串，所以 n>m。

BF 算法的思想就是，在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

在极端情况下，比如主串是“aaaaa…aaaaaa”，模式串是“aaaaab”。每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。但在实际的开发中，它却是一个比较常用的字符串匹配算法。为什么呢？原因有两点。

• 第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

• 第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是KISS（Keep it Simple and Stupid）设计原则](https://zh.wikipedia.org/wiki/KISS原则)。

RK 算法

BF 算法每次检查主串与子串是否匹配，需要依次比对每个字符，所以时间复杂度就比较高，是 O(n*m)。对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。

RK 算法的思路是这样的：通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

不过，通过哈希算法计算子串的哈希值的时候，需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。有没有方法可以提高计算子串哈希值的效率呢？

假设要匹配的字符串的字符集中只包含 K 个字符，可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。比如要处理的字符串只包含 a～z 这 26 个小写字母，那就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字。

在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，只需要把进位从 10 改成 26 就可以。

 

这种哈希算法有一个特点，在主串中，相邻两个子串 s[i-1] 和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，可以使用 s[i-1] 的哈希值很快的计算出 s[i] 的哈希值。如果用公式表示的话，就是下面这个样子：

 

26(m-1) 这部分的计算，可以通过查表的方法来提高效率。先计算好 260、261……26(m-1)，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。当需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。

模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。

模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？

刚刚设计的哈希算法是没有散列冲突的，也就是说，一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样。因为是基于进制来表示一个字符串的。实际上，为了能将哈希值落在整型数据范围内，可以牺牲一下，允许哈希冲突。这个时候哈希算法该如何设计呢？

假设字符串中只包含 a～z 这 26 个英文字母，那每个字母对应一个数字，比如 a 对应 1，以此类推，z 对应 26。把字符串中每个字母对应的数字相加，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多了。不过，这种哈希算法的哈希冲突概率也是挺高的。

当然，还有很多更加优化的方法，比如将每一个字母从小到大对应一个素数，而不是 1，2，3……这样的自然数，这样冲突的概率就会降低一些。

之前只需要比较一下模式串和子串的哈希值，如果两个值相等，那这个子串就一定可以匹配模式串。但是，当存在哈希冲突的时候，有可能子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。这时只需要再对比一下子串和模式串就好了。当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。

所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。

BF 算法是最简单、粗暴的字符串匹配算法，它的实现思路是，拿模式串与主串中是所有子串匹配，看是否有能匹配的子串。时间复杂度是 O(n*m)，n、m 表示主串和模式串的长度。不过，在实际的软件开发中，因为这种算法实现简单，对于处理小规模的字符串匹配很好用。

RK 算法是借助哈希算法对 BF 算法进行改造，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间。所以，理想情况下，RK 算法的时间复杂度是 O(n)。不过如果存在冲突，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。

字符串匹配

课后思考

今天讲的都是一维字符串的匹配方法，实际上，这两种算法都可以类比到二维空间。假设有一个二维字符串矩阵，借助今天讲的处理思路，如何在其中查找另一个二维字符串矩阵（图中的模式串）呢？

• 假设二维主串和模式串的维度分别是 m* n 和 i* j，横向在[0, m-i]，纵向在[0, n-j]取起始点，然后取同样的子串窗口对比，共有(m-i+1)*(n-j+1)个子串。 ps： 文中计算子串哈希值h[i]的公式中，第二个h[i-1]和后面的h[i+m-1]，应该是主串中的第i-1个和第i+m-1个字符的哈希值…

• 以模式串矩阵的大小，去匹配主串矩阵，每个小矩阵可以构建成字符串，就能用 RK 算法做字符串匹配了。 如果主串的大小是 M * N，模式串大小为 m * n，则时间复杂度为 (M - m + 1) * (N - n + 1)。

• 可以在比较时，将二维串矩阵看作是字符串来处理，至于怎么转换成一维字符串，应该有很多方法，比如子串矩阵和模式串矩阵都用同样的规则来组成一个字符串，从左到右，再从上到下遍历取矩阵的元素a[i] [j]。转换为一维字符后，就可以用BF或者RK算法了 。 复杂度分析，假设二维主串矩阵和模式串矩阵的维度分别是 m* n 和 i*j，按一个个矩阵来看子串的话，共有(m-i+1) * (n-j+1)个子串矩阵。 用RK算法的话，复杂度就是O((m-i+1) * (n-j+1))

33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？

对于查找功能是重要功能的软件来说，比如一些文本编辑器，它们的查找功能都是用哪种算法来实现的呢？有没有比 BF 算法和 RK 算法更加高效的字符串匹配算法呢？

BM 算法的核心思想

把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。

 

在这个例子里，主串中的 c，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 c 与模式串有重合，肯定无法匹配。所以，可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面。

BM 算法，本质上其实就是在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

BM 算法原理分析

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来看，这两个规则分别都是怎么工作的。

1. 坏字符规则

BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。

从模式串的末尾往前倒着匹配，当某个字符没法匹配的时候。把这个没有匹配的字符叫作坏字符（主串中的字符）。

拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 c 与模式串中的任何字符都不可能匹配。这个时候，可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。

 

这个时候，模式串中最后一个字符 d，还是无法跟主串中的 a 匹配，这个时候，不能将模式串往后滑动三位。因为坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

当不匹配的时候，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi。如果不存在，把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。

如果坏字符在模式串里多处出现，那在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。

不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。

2. 好后缀规则

好后缀规则实际上跟坏字符规则的思路很类似。当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。

 

这个时候该如何滑动模式串呢？好后缀规则是怎么工作的？

把已经匹配的 bc 叫作好后缀，记作{u}。拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u* }，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。

 

如果在模式串中找不到另一个等于{u}的子串，就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。

不过，当模式串中不存在等于{u}的子串时，直接将模式串滑动到主串{u}的后面。这样做是否有点太过头呢？来看下面这个例子。这里面 bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果我们将模式串移动到好后缀的后面，那就会错过模式串和主串可以匹配的情况。

 

如果好后缀在模式串中不存在可匹配的子串，那在一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。

 

所以，针对这种情况，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，然后将模式串滑动。

当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？

可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

BM 算法代码实现

当遇到坏字符时，要计算往后移动的位数 si-xi，如何求得 xi 呢？或者说，如何查找坏字符在模式串中出现的位置呢？

可以将模式串中的每个字符及其下标都存到散列表中，从而快速找到坏字符在模式串的位置下标了。

关于这个散列表，只实现一种最简单的情况，假设字符串的字符集不是很大，每个字符长度是 1 字节，用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。

 

变量 b 是模式串，m 是模式串的长度，bc 表示刚刚讲的散列表。

private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化 bc
}
for (int i = 0; i < m; ++i) {
int ascii = (int)b[i]; // 计算 b[i] 的 ASCII 值
bc[ascii] = i;
}
}
​

BM 算法代码的大框架，先不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况。

public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int i = 0; // i 表示主串与模式串对齐的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
// 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位
i = i + (j - bc[(int)a[i+j]]); 
}
return -1;
}

​

好后缀的处理规则中最核心的内容：

• 在模式串中，查找跟好后缀匹配的另一个子串；

• 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；

在不考虑效率的情况下，这两个操作都可以用很“暴力”的匹配查找方式解决。但是，如果想要 BM 算法的效率很高，这部分就不能太低效。如何来做呢？

因为好后缀也是模式串本身的后缀子串，所以可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。

如何表示模式串中不同的后缀子串呢？因为后缀子串的最后一个字符的位置是固定的，下标为 m-1，只需要记录长度就可以了。通过长度，可以确定一个唯一的后缀子串。引入最关键的变量 suffix 数组。suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。

如果模式串中有多个子串跟后缀子串{u}匹配，为了避免模式串往后滑动得过头了，suffix 数组存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。实际上，仅仅是选最靠后的子串片段来存储是不够的。

不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。

如果只记录 suffix，实际上，只能在模式串中，查找跟好后缀匹配的另一个子串。所以，除了 suffix 数组之外，还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。

 

 

如何来计算并填充这两个数组的值？

拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，就记录 prefix[k]=true。

 

suffix 数组和 prefix 数组的计算过程

// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
for (int i = 0; i < m; ++i) { // 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) { // b[0, i]
int j = i;
int k = 0; // 公共后缀子串长度
while (j >= 0 && b[j] == b[m-1-k]) { // 与 b[0, m-1] 求公共后缀子串
--j;
++k;
suffix[k] = j+1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标
}
i
if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
}
}
​

在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？

假设好后缀的长度是 k。先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k] 不等于 -1（-1 表示不存在匹配的子串），那就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k] 等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。可以用下面这条规则来处理。

 

好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k] 等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。

 

如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，就将整个模式串后移 m 位。

 

BM 算法的完整版代码实现。

// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b, m, suffix, prefix);
int i = 0; // j 表示主串与模式串匹配的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
int x = j - bc[(int)a[i+j]];
int y = 0;
if (j < m-1) { // 如果有好后缀的话
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
int k = m - 1 - j; // 好后缀长度
if (suffix[k] != -1) return j - suffix[k] +1;
for (int r = j+2; r <= m-1; ++r) {
if (prefix[m-r] == true) { //有前缀
return r;
}
}
return m;
}
​

BM 算法的性能分析及优化

BM 算法的内存消耗。整个算法用到了额外的 3 个数组，其中 bc 数组的大小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。

如果处理字符集很大的字符串匹配问题，bc 数组对内存的消耗就会比较多。因为好后缀和坏字符规则是独立的，如果运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bc 数组过多的内存消耗。不过，单纯使用好后缀规则的 BM 算法效率就会下降一些了。

对于执行效率来说，可以先从时间复杂度的角度来分析。比如模式串是 aaaaaaa 这种包含很多重复的字符的模式串，预处理的时间复杂度就是 O(m2)。

BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM 算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，可以只用好后缀规则来实现 BM 算法。

课后思考

你熟悉的编程语言中的查找函数，或者工具、软件中的查找功能，都是用了哪种字符串匹配算法呢？

一个文档：http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

BM算法的核心思想是通过将模式串沿着主串大踏步的向后滑动，从而大大减少比较次数，降低时间复杂度。而算法的关键在于如何兼顾步子迈得足够大与无遗漏，同时要尽量提高执行效率。这就需要模式串在向后滑动时，遵守坏字符规则与好后缀规则，同时采用一些技巧。

何时使用坏字符规则和好后缀规则呢？

首先在每次匹配过程中，一旦发现坏字符，先执行坏字符规则，如果发现存在好后缀，还要执行好后缀规则，并从两者中选择后移距离最大的方案执行。

技巧： 1.通过散列表实现，坏字符在模式串中下标位置的快速查询。 2.每次执行好后缀原则时，都会计算多次能够与模式串前缀子串相匹配的好后缀的最长后缀子串。为了提高效率，可以预先计算模式串的所有后缀子串，在模式串中与之匹配的另一个子串的位置。同时预计算模式串中（同长度的）后缀子串与前缀子串是否匹配并记录。在具体操作中直接使用，大大提高效率。 3.如何快速记录模式串后缀子串匹配的另一个子串位置，以及模式串（相同长度）前缀与后缀子串石否匹配呢？先用一个suffix数组，下标值k为后缀子串的长度，从模式串下标为i（0~m-2）的字符为最后一个字符，查找这个子串是否与后缀子串匹配，若匹配则将子串起始位置的下标值j赋给suffix[k]。若j为0，说明这个匹配子串的起始位置为模式串的起始位置，则用一个数组prefix，将prefix[k]设为true，否则设为false。k从0到m（模式串的长度）于是就得到了模式串所有前缀与后缀子串的匹配情况。

34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？

KMP 算法基本原理

KMP 算法的核心思想，跟BM 算法非常相近。假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，希望可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。

当遇到坏字符的时候，就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。

 

KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否将模式串一次性滑动很多位？

只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。

 

好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

 

如何来求好前缀的最长可匹配前缀和后缀子串呢？

类似 BM 算法中的 bc、suffix、prefix 数组，KMP 算法也可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。把这个数组定义为next 数组，叫失效函数（failure function）。

数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。

 

假设 next 数组已经计算好了，先给出 KMP 算法的框架代码。

// a, b 分别是主串和模式串；n, m 分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) { // 一直找到 a[i] 和 b[j]
j = next[j - 1] + 1;
}
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到匹配模式串的了
return i - m + 1;
}
}
return -1;
}
​

失效函数计算方法

next 数组是如何计算出来的？

按照下标从小到大，依次计算 next 数组的值。计算 next[i] 的时候，前面的 next[0]，next[1]，……，next[i-1] 应该已经计算出来了。利用已经计算出来的 next 值，是否可以快速推导出 next[i] 的值呢？

如果 next[i-1]=k-1，也就是说，子串 b[0, k-1] 是 b[0, i-1] 的最长可匹配前缀子串。如果子串 b[0, k-1] 的下一个字符 b[k]，与 b[0, i-1] 的下一个字符 b[i] 匹配，那子串 b[0, k] 就是 b[0, i] 的最长可匹配前缀子串。所以，next[i] 等于 k。但是，如果 b[0, k-1] 的下一字符 b[k] 跟 b[0, i-1] 的下一个字符 b[i] 不相等呢？这个时候就不能简单地通过 next[i-1] 得到 next[i] 了。这个时候该怎么办呢？

假设 b[0, i] 的最长可匹配后缀子串是 b[r, i]。如果把最后一个字符去掉，那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然 b[0, i-1] 最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]，那么就可以考察 b[0, i-1] 的次长可匹配后缀子串 b[x, i-1] 对应的可匹配前缀子串 b[0, i-1-x] 的下一个字符 b[i-x] 是否等于 b[i]。如果等于，那 b[x, i] 就是 b[0, i] 的最长可匹配后缀子串。

 

可是，如何求得 b[0, i-1] 的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是，查找 b[0, i-1] 的次长可匹配后缀子串，这个问题就变成，查找 b[0, y] 的最长匹配后缀子串的问题了。

 

按照这个思路，可以考察完所有的 b[0, i-1] 的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i] 就是 b[0, i] 的最长可匹配后缀子串。

// b 表示模式串，m 表示模式串的长度
private static int[] getNexts(char[] b, int m) {
int[] next = new int[m];
next[0] = -1;
int k = -1;
for (int i = 1; i < m; ++i) {
while (k != -1 && b[k + 1] != b[i]) {
k = next[k];
}
if (b[k + 1] == b[i]) {
++k;
}
next[i] = k;
}
return next;
}
​

KMP 算法复杂度分析

KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。

KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，要分别从这两部分来分析。

计算 next 数组的代码中，可以找一些参照变量，i 和 k。i 从 1 开始一直增加到 m，而 k 并不是每次 for 循环都会增加，所以，k 累积增加的值肯定小于 m。而 while 循环里 k=next[k]，实际上是在减小 k 的值，k 累积都没有增加超过 m，所以 while 循环里面 k=next[k] 总的执行次数也不可能超过 m。因此，next 数组计算的时间复杂度是 O(m)。

分析第二部分的时间复杂度。i 从 0 循环增长到 n-1，j 的增长量不可能超过 i，所以肯定小于 n。而 while 循环中的那条语句 j=next[j-1]+1，不会让 j 增长的，也不能让 j 不变呢。因为 next[j-1] 的值肯定小于 j-1，所以 while 循环中的这条语句实际上也是在让 j 的值减少。而 j 总共增长的量都不会超过 n，那减少的量也不可能超过 n，所以 while 循环中的这条语句总的执行次数也不会超过 n，所以这部分的时间复杂度是 O(n)。

所以，综合两部分的时间复杂度，KMP 算法的时间复杂度就是 O(m+n)。

KMP 算法和BM 算法的本质类似，都是根据规律在遇到坏字符的时候，把模式串往后多滑动几位。

BM 算法有两个规则，坏字符和好后缀。KMP 算法借鉴 BM 算法的思想，可以总结成好前缀规则。这里面最难懂的就是 next 数组的计算，按照下标 i 从小到大，依次计算 next[i]，并且 next[i] 的计算通过前面已经计算出来的 next[0]，next[1]，……，next[i-1] 来推导

35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？

什么是“Trie 树”？

Trie 树，也叫“字典树”。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

Trie 树构造的分解过程。构造过程的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了。

当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。

如果我们要查找的是字符串“he”呢？还用上面同样的方法，从根节点开始，沿着某条路径来匹配，但是，路径的最后一个节点“e”并不是红色的。也就是说，“he”是某个字符串的前缀子串，但并不能完全匹配任何字符串。

如何实现一棵 Trie 树？

Trie 树主要有两个操作，一个是将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

如何存储一个 Trie 树？

Trie 树是一个多叉树。二叉树中，一个节点的左右子节点是通过两个指针来存储的，如下所示 Java 代码。那对于多叉树来说，怎么存储一个节点的所有子节点的指针呢？

class BinaryTreeNode {
char data;
BinaryTreeNode left;
BinaryTreeNode right;  
}
​

借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针

假设字符串中只有从 a 到 z 这 26 个小写字母，在数组中下标为 0 的位置，存储指向子节点 a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，就在对应的下标的位置存储 null。

class TrieNode {
char data;
TrieNode children[26];
}
​

当在 Trie 树中查找字符串的时候，就可以通过字符的 ASCII 码减去“a”的 ASCII 码，迅速找到匹配的子节点的指针。

在 Trie 树中，查找某个字符串的时间复杂度是多少？

如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。

每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

Trie 树真的很耗内存吗？

“Trie 树是非常耗内存的，用的是一种空间换时间的思路”。这是什么原因呢？

Trie 树用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符，那每个节点都要存储一个长度为 26 的数组，并且每个数组存储一个 8 字节指针（或者是 4 字节，这个大小跟 CPU、操作系统、编译器等有关）。而且，即便一个节点只有很少的子节点，远小于 26 个，比如 3、4 个，我们也要维护一个长度为 26 的数组。

Trie 树的本质是避免重复存储一组字符串的相同前缀子串，但是现在每个字符（对应一个节点）的存储远远大于 1 个字节。按照我们上面举的例子，数组长度为 26，每个元素是 8 字节，那每个节点就会额外需要 26*8=208 个字节。而且这还是只

public class Trie {
private TrieNode root = new TrieNode('/'); // 存储无意义字符
// 往 Trie 树中插入一个字符串
public void insert(char[] text) {
TrieNode p = root;
for (int i = 0; i < text.length; ++i) {
int index = text[i] - 'a';
if (p.children[index] == null) {
TrieNode newNode = new TrieNode(text[i]);
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
}
// 在 Trie 树中查找一个字符串
public boolean find(char[] pattern) {
TrieNode p = root;
for (int i = 0; i < pattern.length; ++i) {
int index = pattern[i] - 'a';
if (p.children[index] == null) {
return false; // 不存在 pattern
}
p = p.children[index];
}
if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
else return true; // 找到 pattern
}
public class TrieNode {
public char data;
public TrieNode[] children = new TrieNode[26];
public boolean isEndingChar = false;
public TrieNode(char data) {
this.data = data;
}
}
}
​

包含 26 个字符的情况。

如果字符串中不仅包含小写字母，还包含大写字母、数字、甚至是中文，那需要的存储空间就更多了。所以，也就是说，在某些情况下，Trie 树不一定会节省存储空间。在重复的前缀并不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

可以稍微牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点的子节点指针。比如有序数组、跳表、散列表、红黑树等。

假设用有序数组，数组中的指针按照所指向的子节点中的字符的大小顺序排列。查询的时候，可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。但是，在往 Trie 树中插入一个字符串的时候，为了维护数组中数据的有序性，就会稍微慢了点。

实际上，Trie 树的变体有很多，都可以在一定程度上解决内存消耗的问题。比如，缩点优化，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并。这样可以节省空间，但却增加了编码难度。

 

Trie 树与散列表、红黑树的比较

实际上，字符串的匹配问题，笼统上讲，其实就是数据的查找问题。对于支持动态数据高效操作的数据结构，比如散列表、红黑树、跳表等等。实际上，这些数据结构也可以实现在一组字符串中查找字符串的功能。散列表和红黑树，跟 Trie 树比较一下，看看它们各自的优缺点和应用场景。

在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。

第一，字符串中包含的字符集不能太大。如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。

第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。

第三，如果要用 Trie 树解决问题，那就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。

第四，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

综合这几点，针对在一组字符串中查找字符串的问题，更倾向于用散列表或者红黑树。因为这两种数据结构，都不需要自己去实现，直接利用编程语言中提供的现成类库就行了。

实际上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串。

如何利用 Trie 树，实现搜索关键词的提示功能？

假设关键词库由用户的热门搜索关键词组成。将这个词库构建成一个 Trie 树。当用户输入其中某个单词的时候，把这个词作为一个前缀子串在 Trie 树中匹配。假设词库里只有 hello、her、hi、how、so、see 这 6 个关键词。当用户输入了字母 h 的时候，就把以 h 为前缀的 hello、her、hi、how 展示在搜索提示框内。当用户继续键入字母 e 的时候，就把以 he 为前缀的 hello、her 展示在搜索提示框内。这就是搜索关键词提示的最基本的算法原理。

实际上，搜索引擎的搜索关键词提示功能远非这么简单。上面的解决办法遇到下面几个问题：

• 刚讲的思路是针对英文的搜索关键词提示，对于更加复杂的中文来说，词库中的数据又该如何构建成 Trie 树呢？

• 如果词库中有很多关键词，在搜索提示的时候，用户输入关键词，作为前缀在 Trie 树中可以匹配的关键词也有很多，如何选择展示哪些内容呢？

• 像 Google 这样的搜索引擎，用户单词拼写错误的情况下，Google 还是可以使用正确的拼写来做关键词提示，这个又是怎么做到的呢？

实际上，Trie 树的这个应用可以扩展到更加广泛的一个应用上，就是自动输入补全，比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。

Trie 树是一种解决字符串快速匹配问题的数据结构。如果用来构建 Trie 树的这一组字符串中，前缀重复的情况不是很多，那 Trie 树这种数据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。

尽管比较耗费内存，但是对内存不敏感或者内存消耗在接受范围内的情况下，在 Trie 树中做字符串匹配还是非常高效的，时间复杂度是 O(k)，k 表示要匹配的字符串的长度。

但是，Trie 树的优势并不在于，用它来做动态集合数据的查找，因为，这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie 树最有优势的是查找前缀匹配的字符串，比如搜索引擎中的关键词提示功能这个场景，就比较适合用它来解决，也是 Trie 树比较经典的应用场景。

36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？

那如何才能实现一个高性能的敏感词过滤系统呢？这就要用到今天的多模式串匹配算法。

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

BF 算法、RK 算法、BM 算法、KMP 算法都是单模式串匹配算法，只有 Trie 树是多模式串匹配算法。

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

如何用 Trie 树实现敏感词过滤功能呢？

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

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

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

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 数组）。

构建好 Trie 树之后，如何在它之上构建失败指针？

Trie 树中的每一个节点都有一个失败指针，它的作用和构建过程，跟 KMP 算法中的 next 数组极其相似。

假设沿 Trie 树走到 p 节点，也就是下图中的紫色节点，那 p 的失败指针就是从 root 走到紫色节点形成的字符串 abc，跟所有模式串前缀匹配的最长可匹配后缀子串，就是箭头指的 bc 模式串。

字符串 abc 的后缀子串有两个 bc，c，拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，那就把这个后缀子串叫作可匹配后缀子串。

从可匹配后缀子串中，找出最长的一个，就是最长可匹配后缀子串。将 p 节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点，就是下图中箭头指向的节点。

 

如果把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。

可以像 KMP 算法那样，当要求某个节点的失败指针的时候，通过已经求得的、深度更小的那些节点的失败指针来推导。也就是说，可以逐层依次来求解每个节点的失败指针。所以，失败指针的构建过程，是一个按层遍历树的过程。

首先 root 的失败指针为 NULL，也就是指向自己。当已经求得某个节点 p 的失败指针之后，如何寻找它的子节点的失败指针呢？

假设节点 p 的失败指针指向节点 q，看节点 p 的子节点 pc 对应的字符，是否也可以在节点 q 的子节点中找到。如果找到了节点 q 的一个子节点 qc，对应的字符跟节点 pc 对应的字符相同，则将节点 pc 的失败指针指向节点 qc。

 

如果节点 q 中没有子节点的字符等于节点 pc 包含的字符，则令 q=q->fail（fail 表示失败指针），继续上面的查找，直到 q 是 root 为止，如果还没有找到相同字符的子节点，就让节点 pc 的失败指针指向 root。

 

public void buildFailurePointer() {
Queue<AcNode> queue = new LinkedList<>();
root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcNode p = queue.remove();
for (int i = 0; i < 26; ++i) {
AcNode pc = p.children[i];
if (pc == null) continue;
if (p == root) {
pc.fail = root;
} else {
AcNode q = p.fail;
while (q != null) {
AcNode qc = q.children[pc.data - 'a'];
if (qc != null) {
pc.fail = qc;
break;
}
q = q.fail;
}
if (q == null) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}

最后构建完成之后的 AC 自动机就是下面这个样子：

 

如何在 AC 自动机上匹配主串？

在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始，假设模式串是 b，主串是 a。

• 如果 p 指向的节点有一个等于 b[i] 的子节点 x，就更新 p 指向 x，这个时候需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。处理完之后，将 i 加一，继续这两个过程；

• 如果 p 指向的节点没有等于 b[i] 的子节点，那失败指针就派上用场了，让 p=p->fail，然后继续这 2 个过程。

public void match(char[] text) { // text 是主串
int n = text.length;
AcNode p = root;
for (int i = 0; i < n; ++i) {
int idx = text[i] - 'a';
while (p.children[idx] == null && p != root) {
p = p.fail; // 失败指针发挥作用的地方
}
p = p.children[idx];
if (p == null) p = root; // 如果没有匹配的，从 root 开始重新匹配
AcNode tmp = p;
while (tmp != root) { // 打印出可以匹配的模式串
if (tmp.isEndingChar == true) {
int pos = i-tmp.length+1;
System.out.println(" 匹配起始下标 " + pos + "; 长度 " + tmp.length);
}
tmp = tmp.fail;
}
}
}
​

这已经是一个敏感词过滤的原型代码了。它可以找到所有敏感词出现的位置（在用户输入的文本中的起始下标）。只要稍加改造，再遍历一遍文本内容（主串），就可以将文本中的所有敏感词替换成“***”。

AC 自动机实现的敏感词过滤系统，是否比单模式串匹配方法更高效呢？

首先，需要将敏感词构建成 AC 自动机，包括构建 Trie 树以及构建失败指针。

Trie 树构建的时间复杂度是 O(m*len)，其中 len 表示敏感词的平均长度，m 表示敏感词的个数。那构建失败指针的时间复杂度是多少呢？

假设 Trie 树中总的节点个数是 k，每个节点构建失败指针的时候，最耗时的环节是 while 循环中的 q=q->fail，每运行一次这个语句，q 指向节点的深度都会减少 1，而树的高度最高也不会超过 len，所以每个节点构建失败指针的时间复杂度是 O(len)。整个失败指针的构建过程就是 O(k*len)。

不过，AC 自动机的构建过程都是预先处理好的，构建好之后，并不会频繁地更新，所以不会影响到敏感词过滤的运行效率。

用 AC 自动机做匹配的时间复杂度是多少？

跟刚刚构建失败指针的分析类似，for 循环依次遍历主串中的每个字符，for 循环内部最耗时的部分也是 while 循环，而这一部分的时间复杂度也是 O(len)，所以总的匹配的时间复杂度就是 O(n*len)。因为敏感词并不会很长，而且这个时间复杂度只是一个非常宽泛的上限，实际情况下，可能近似于 O(n)，所以 AC 自动机做敏感词过滤，性能非常高。

从时间复杂度上看，因为失效指针可能大部分情况下都指向 root 节点，所以绝大部分情况下，在 AC 自动机上做匹配的效率要远高于刚刚计算出的比较宽泛的时间复杂度。只有在极端情况下，如图所示，AC 自动机的性能才会退化的跟 Trie 树一样。

 

单模式串匹配算法是为了快速在主串中查找一个模式串，而多模式串匹配算法是为了快速在主串中查找多个模式串。

AC 自动机是基于 Trie 树的一种改进算法，它跟 Trie 树的关系，就像KMP 算法与 BF 算法的关系一样。KMP 算法中有一个非常关键的 next 数组，类比到 AC 自动机中就是失败指针。而且，AC 自动机失败指针的构建过程，跟 KMP 算法中计算 next 数组极其相似。

整个 AC 自动机算法包含两个部分，第一部分是将多个模式串构建成 AC 自动机，第二部分是在 AC 自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成 Trie 树，另一个是在 Trie 树上构建失败指针。