文本是我们接触最多的一种数据格式了。随着互联网生产的UGC(user gernerate content)越来越多,对文本的处理需求也越来越多。 闲话少说,我们来看下字符串的文本匹配都有哪些有趣的算法。
Tips:
模式匹配指有一个敏感词或者叫模式 A,对于一个输入字符串B,查找B是否含有A,且A的位置。
首先来一段日常聊天
架构师玄姐问:小姚,字符串模式匹配怎么做更好呀 菜鸟小姚说:So easy, Java 自带 String.contains() 简单方便、
完美的实现! 架构师玄姐说:那你知道contains怎么实现的吗? 菜鸟小姚说:虽然不会,但我可以学,我去看下源码怎么做的。
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;
}
/*如果有没有匹配上的字符,跳出当前循环*/
}
}
KMP 算法
Tips:
KMP 主要解决暴力匹配在模式字符串中途匹配失败后,循环需要退回到开始位置的问题。
K/M/P分别是三个名字的首字母,老外的套路
为了能够解决这个问题,我们用动画模拟下理想状态
这个方法匹配一个模式,已经了解得比较透了,那如果匹配多个模式呢?也就是字符串的多模式匹配。 前辈都是很强大的,果然业界也有解决办法:AC 自动机
Tips:
AC自动机全称Aho-Corasick自动机,是一种特殊的字典树结构。
没有悬链,AC也是两位大神的名字。出自大名鼎鼎的贝尔实验室。
事后小姚惊讶的发现,AC算法的本质思想也是KMP思想。我们来一起看下:
闲话少说,直接上栗子: 针对模式集合 {"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自动机实现高并发低延迟场景下敏感词的识别的。
需求:
一、 数据设计
敏感词 | 多词标示 | 类别 |
---|---|---|
keyword | 0 | 1 |
keyword2 | 1 | 1 |
keyword3 | 1 | 1 |
二、流程设计
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;
}