字符串模式匹配趣味算法
场景
文本是我们接触最多的一种数据格式了。随着互联网生产的UGC(user gernerate content)越来越多，对文本的处理需求也越来越多。 闲话少说，我们来看下字符串的文本匹配都有哪些有趣的算法。
Tips：
模式匹配指有一个敏感词或者叫模式 A，对于一个输入字符串B，查找B是否含有A，且A的位置。程序员解法
首先来一段日常聊天
架构师玄姐问：小姚，字符串模式匹配怎么做更好呀 菜鸟小姚说：So easy, Java 自带 String.contains() 简单方便、
完美的实现！ 架构师玄姐说：那你知道contains怎么实现的吗？ 菜鸟小姚说：虽然不会，但我可以学，我去看下源码怎么做的。
下面是小姚的探索历程：
- 查看contains源码，底层是使用的indexOf 函数
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* 查找第一个匹配字符 */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* 第一个已经匹配上，匹配剩余的字符 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j]== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
/*如果有没有匹配上的字符，跳出当前循环*/
}
}- 勤奋的小姚还特地模仿流程做了个动画
- 敏锐的小姚发现字母D不匹配后，红框往回跳很别扭，极端情况下及其影响效率
- 架构师玄姐微笑的指出这种匹配方式是暴力匹配，缺点也是匹配失败后，需要丢弃已匹配的信息，极大的降低了匹配效率
好奇的小姚开始新方法探索：
KMP 算法
Tips:
KMP 主要解决暴力匹配在模式字符串中途匹配失败后，循环需要退回到开始位置的问题。
K/M/P分别是三个名字的首字母，老外的套路为了能够解决这个问题，我们用动画模拟下理想状态
- 如果匹配失败后，比对位置不往回跳，那么就能提高效率了
- 从图中可以看出，如果输入位置不变，模式位置就需要进行调整，不能从第一个字符开始比对
- 解决方法：对模式字符串进行预处理，生成一个"错误查找数组",记录匹配失败后，模式字符串调整位置，可以看出这个错误查找数组只和自己构成相关
- KMP 循环次数不超过输入字符串长度，时间复杂度是 O(m+n)
小姚又有了新的想法
这个方法匹配一个模式，已经了解得比较透了，那如果匹配多个模式呢？也就是字符串的多模式匹配。 前辈都是很强大的，果然业界也有解决办法：AC 自动机
Tips:
AC自动机全称Aho-Corasick自动机，是一种特殊的字典树结构。
没有悬链，AC也是两位大神的名字。出自大名鼎鼎的贝尔实验室。AC算法
事后小姚惊讶的发现，AC算法的本质思想也是KMP思想。我们来一起看下：
- AC算法主要三个步骤：
- 建立Trie字典树
- 给Trie 添加失败路径，形成AC自动机（类似KMP方案）
- 根据AC自动机，搜索待处理的稳步
闲话少说，直接上栗子： 针对模式集合 {"ash","shex","bcd","sha"} 构建AC自动机
- 生成字典树
- 添加失败路径
广度优先遍历Trie（BFS） 首字符指向根节点 其他字符指向他父亲节点fail指向的那个节点具有相同字母的子节点 使用上图为例
例子：
ash 的s节点查找父节点(a),a指向的根节点下相同的字符串s
因此ash的s的失败指针指向shex分支的s整体的失败指针添加动图：
最后，AC自动机怎么实现多模匹配呢？ 使用上面的AC自动机处理输入字符串 比如：ashaxx，结果是：ash 和 sha
答案：
a.使用Trie数匹配到ash，h节点是一个完整的词， 因此匹配出第一个词 ash
b.匹配a时，从h的失败指向找到sh节点，继续往下.找到sha,a节点是一个完整的词，
因此匹配出第二个词 sha
c.匹配x时，a的失败节点是ash分支，x无法匹配，返回到跟节点。
d.继续匹配x，根节点，结束匹配业务应用
知道AC自动机算法后，我们来看下在小姚怎么用AC自动机实现高并发低延迟场景下敏感词的识别的。
需求：
- 需要针对敏感词有不同的分类，比如色情、违法等
- 为了更灵活匹配，需要设定A、B两个词同时出现才算命中敏感词
一、 数据设计
- 为了满足业务需求，在数据设计上，我们给没个词都增加了多个维度的属性
- 通过在每个词上新增属性来区分词的类别及是否多词匹配
敏感词 | 多词标示 | 类别 |
|---|---|---|
keyword | 0 | 1 |
keyword2 | 1 | 1 |
keyword3 | 1 | 1 |
二、流程设计
- AC自动机一次性取出所有命中的关键词
2. 如果有命中，需要通过命中的词去查询词的属性特征
3. 从属性中判断是否包含多词命中情况
4. 查出词库中所有多词词组
5. 验证命中的多词和定义的多词是否一致
6. 得出结论
三、最终效果
- 线上每天处理亿级别的匹配需求
- 词库管理上万条敏感词
- 需求得到完美的满足
附KMP错误查找数组构建关键代码
public static int[] next(String target) {
char[] t = target.toCharArray();
int[] next = new int[t.length];
next[0] = -1;
int k = -1;
int j = 0;
while (j < next.length - 1) {
if (k == -1 || t[j] == t[k]) {
k++;
j++;
// 较优化前的next数组求法，改变在以下四行代码。
if (t[j] != t[k]) {
next[j] = k;// 优化前只有这一行。
} else {
next[j] = next[k];
}
// ===============
} else {
k = next[k];
}
}
return next;
}