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