文章大约分为以下3个部分:
1、应用背景;
2、AC算法介绍及其原理;
3、AC算法的Java实现;
1、应用背景
在互联网应用中,通常会用到关键词检测功能,以防止用户发表包括了指定关键词的内容。如游戏的聊天系统、角色名称检测,论坛发帖、直播弹幕等,都需要对用户发布的内容进行检测,以检测是否包含敏感的关键字。
通常需要检测的关键词,会有很多很多,比如侮辱人的关键词,政治敏感的关键词,系统相关的特定关键词等。毫不夸张的说,通常要检测的关键词会有几千个,甚至过万。这时效率都变得尤为突出,如果检测关键词的效率低下,对大型互联网应用来说,很可能有是致命的。
以8000个关键词为例,如果使用正则表达式,则需要对用户发布的内容遍历8000遍。如果同一秒中,有100位,1000位,10000位...用户发布内容,可想而知仅仅在关键词检测方面服务器上CPU的开销。
AC多模式匹配算法,可以有效的解决关键词检测的效率问题。时间复杂度为O(n),n为用户发布内容的长度n。基本与关键词的数量无关。
2、AC算法介绍及其原理
AC算法是Alfred V.Aho(《编译原理》的作者),和Margaret J.Corasick于1974年提出(与KMP算法同年)的一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,...pm},在O(n)时间复杂度内,找到文本中的所有目标模式,而与模式集合的规模m无关。
AC算法实现原理,大体上可分为三步:
1)、构建敏感词树型结构,并标注结束节点(即是否是一个敏感词的结束);
2)、为树上的结点,构建匹配失败时的跳转-失败结点(即匹配失败时,跳转到哪个结点继续匹配);
3)、对用户内容进行一次遍历,对于每个字符(字节)都去敏感词树型结构中,从当前结点位置开始匹配。
如果匹配成功,则当前结点,下移到对应的结点。如果当前结点为“结束节点”,则表示匹配成功;
如果匹配失败,则当前结点,跳转到该结点的失败结点,继续匹配,直到匹配成功或当前结点为根结点;
1)构建敏感词树型结构,并标注结束节点(即是否是一个敏感词的结束)
首先要有一个根结点;
遍历所有的敏感词,将每个敏感词的每一个字节,放到树上,成为一个结点。每一个字节的前一字节所对应的结点,都为该字节所对应结点的父结点。如果字节所对应的结点已存在,则不再添加新的结点。如果该字节为敏感词的最后一个字节,则将对应结点,设置为结束结点。
如敏感词:he,hers,his,erase
2)为树上的结点,构建匹配失败时的跳转-失败结点(即匹配失败时,跳转到哪个结点继续匹配)
第一层子节点的失败节点,直接指定是根结点;
其它子节点的失败节点,是其父结点的失败点中查找相应的路径。如果查不到,则继续在当前结点的失败结点中查找相应的路径。直到找相应的节点,或失败节点为根结点。
3)对用户内容进行一次遍历,对于每个字符(字节)都去敏感词树型结构中,从当前结点位置开始匹配。
如果匹配成功,则当前结点,下移到对应的结点。如果当前结点为“结束节点”,则表示匹配成功;
如果匹配失败,则当前结点,跳转到该结点的失败结点,继续匹配,直到匹配成功或当前结点为根结点;
以herase为类,演示
3、AC算法的Java实现
数据结构,关键词树上的结点Node.java
package cn.buddie.ac.model;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
/**
* 结点类
*
* @author buddie
*
*/
public class Node {
// 当前结点的层级
private int level;
// 当前结点后子结点,Key为小写字母
private Map<Character, Node> subNodes;
// 当前结果匹配失败时的跳转结点
private Node failNode;
// 当前结点是否是终结结点
private boolean terminal;
/**
* 当前结点是否已包含指定Key值的子结点
*
* @param c
* @return
*/
public boolean containSubNode(Character c) {
if (this.subNodes == null || this.subNodes.isEmpty()) {
return false;
}
return subNodes.containsKey(c);
}
/**
* 获取指定Key值的子结点
*
* @param c
* @return
*/
public Node getSubNode(Character c) {
if (this.subNodes == null || this.subNodes.isEmpty()) {
return null;
}
return subNodes.get(c);
}
/**
* 添加子结点
*
* @param c
* @param node
*/
public void addSubNode(Character c, Node node) {
if (this.subNodes == null) {
this.subNodes = new HashMap<Character, Node>();
}
this.subNodes.put(c, node);
}
// getter & setter
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
public Map<Character, Node> getSubNodes() {
return subNodes == null ? Collections.emptyMap() : subNodes;
}
public void setSubNodes(Map<Character, Node> subNodes) {
this.subNodes = subNodes;
}
public Node getFailNode() {
return failNode;
}
public void setFailNode(Node failNode) {
this.failNode = failNode;
}
public boolean isTerminal() {
return terminal;
}
public void setTerminal(boolean terminal) {
this.terminal = terminal;
}
}
构建关键词树,关构建失败结点
package cn.buddie.ac.tree;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import cn.buddie.ac.model.Node;
public class ACTree {
private Node rootNode;
public ACTree(String[] keyWords) {
// 初始树
initTree(keyWords);
// 构建失败跳转
buildFailLink();
}
/**
* 初始树
*
* @param keyWords
*/
private void initTree(String[] keyWords) {
rootNode = new Node();
rootNode.setSubNodes(new HashMap<Character, Node>());
char[] charArray;
for (String keyWord : keyWords) {
if (keyWord.isEmpty()) {
continue;
}
charArray = keyWord.toLowerCase().toCharArray();
buildKeyMap(charArray);
}
}
/**
* 构建指定字符数组的结点
*
* @param charArray
*/
private void buildKeyMap(char[] charArray) {
Character c;
Node curNode = rootNode;
Node node;
for (int i = 0; i < charArray.length; i++) {
c = charArray[i];
if (curNode.containSubNode(c)) {
node = curNode.getSubNode(c);
} else {
node = new Node();
node.setLevel(i + 1);
curNode.addSubNode(c, node);
}
if (i == charArray.length - 1) {
node.setTerminal(true);
}
curNode = node;
}
}
/**
* 构建失败跳转
*/
private void buildFailLink() {
buildFirstLevelFailLink();
buildOtherLevelFailLink();
}
/**
* 根结点的所有第一级子结点,失败跳转均为根结点
*/
private void buildFirstLevelFailLink() {
Collection<Node> nodes = rootNode.getSubNodes().values();
for (Node node : nodes) {
node.setFailNode(rootNode);
}
}
/**
* 根结点、第一级结点以外的所有结点,失败跳转均为其父结点的失败结点的对应子结点
*/
private void buildOtherLevelFailLink() {
Queue<Node> queue = new LinkedList<Node>(rootNode.getSubNodes().values());
Node node;
while (!queue.isEmpty()) {
node = queue.remove();
buildNodeFailLink(node, queue);
}
}
/**
* 构建指定结点的下一层结点的失败跳转
*
* @param node
*/
private void buildNodeFailLink(Node node, Queue<Node> queue) {
if (node.getSubNodes().isEmpty()) {
return;
}
queue.addAll(node.getSubNodes().values());
Node failNode = node.getFailNode();
Set<Character> subNodeKeys = node.getSubNodes().keySet();
Node subFailNode;
for (Character key : subNodeKeys) {
subFailNode = failNode;
while (subFailNode != rootNode && !subFailNode.containSubNode(key)) {
subFailNode = subFailNode.getFailNode();
}
subFailNode = subFailNode.getSubNode(key);
if (subFailNode == null) {
subFailNode = rootNode;
}
node.getSubNode(key).setFailNode(subFailNode);
}
}
// getter
public Node getRootNode() {
return rootNode;
}
}
过滤、替换工具类
package cn.buddie.ac.filter;
import org.apache.commons.lang.StringUtils;
import cn.buddie.ac.model.Node;
import cn.buddie.ac.tree.ACTree;
public class ACFilter {
public static final Character REPLACE_CHAR = '*';
private ACTree tree;
public ACFilter(ACTree tree) {
this.tree = tree;
}
/**
* 过滤
*
* @param word
* @return
*/
public String filter(String word) {
if (StringUtils.isEmpty(word)) {
return "";
}
char[] words = word.toLowerCase().toCharArray();
char[] result = null;
Node curNode = tree.getRootNode();
Node subNode;
Character c;
int fromPos = 0;
for (int i = 0; i < words.length; i++) {
c = words[i];
subNode = curNode.getSubNode(c);
while (subNode == null && curNode != tree.getRootNode()) {
curNode = curNode.getFailNode();
subNode = curNode.getSubNode(c);
}
if (subNode != null) {
curNode = subNode;
}
if (curNode.isTerminal()) {
int pos = i - curNode.getLevel() + 1;
if (pos < fromPos) {
pos = fromPos;
}
if (result == null) {
result = word.toLowerCase().toCharArray();
}
for (; pos <= i; pos++) {
result[pos] = REPLACE_CHAR;
}
fromPos = i + 1;
}
}
if (result == null) {
return word;
}
return String.valueOf(result);
}
}
Demo
package cn.buddie.ac;
import cn.buddie.ac.filter.ACFilter;
import cn.buddie.ac.tree.ACTree;
public class WordFilterTest {
public static void main(String[] args) {
String[] keyWords = new String[] { "he", "hers", "his", "erase" };
ACTree tree = new ACTree(keyWords);
ACFilter filter = new ACFilter(tree);
String str = "herase";
str = filter.filter(str);
System.out.println(str);
}
}
相关推荐
AC多模式匹配算法 特点:应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点:一是扫描文本时完全不需要回溯,二是时间复杂度为O(n)与关键字的数目和长度无关,但所需时间和文本长度以及所有关键字...
AC多模式匹配算法 特点:应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点:一是扫描文本时完全不需要回溯,二是时间复杂度为O(n)与关键字的数目和长度无关,但所需时间和文本长度以及所有关键字...
AC多模式匹配算法的优化与应用,孙强,辛阳,针对Aho-Corasick(AC)多模式匹配算法使用大的空间复杂度代价换取小的时间复杂度,提出一种改进算法降低AC多模式匹配算法的空间复杂度,
多模式匹配算法 AC_BM算法 算法很经典 欢迎下载
多模式匹配算法效率直接影响入侵检测系统的性能和效率。在分析研究经典的AC算法、WM算法和ExB算法 的基础上。通过上机实验测试这些算法的模式匹配时间,为改进多模式匹配算法提供有益的借鏊。
多模式匹配算法 AC算法 C实现 还有数据用例
全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
针对Aho-Corasick(AC)多模式匹配算法使用大的空间复杂度代价换取小的时间复杂度,提出一种改进算法降 低AC多模式匹配算法的空间复杂度,使AC多模式匹配算法的空间复杂度减少10%,并实现AC多模式匹配算法在深层 报文解析...
【模式匹配】之——多模匹配 上篇(AC算法),具体讲解参阅下文: http://blog.csdn.net/sun2043430/article/details/8821089
AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
AC(Aho-Corasick)自动机是经典的多模式匹配算法,但在模式串字符集较大的情况下,AC自动机的存储开销较大。为降低存储开销提出了存储优化的多模式匹配算法SMMA,该算法在Trie树建立阶段利用正向表来存储每个状态的...
不知道是自己的搜索能力太差还是怎么的,在CSDN上多花了6分下载这些资源,这是我上传的不需要分的资源,enjoy it...
针对病毒特征检测中码串长度对模式匹配算法性能影响的问题, 结合基于码串长度的特征集自适应分类思路, 提出了两种改进的多模式精确匹配算法, 即NAC_BM和NWM_QS。改进算法通过引入文本窗口的前缀字符块WB增加了跳跃...
基于NFA状态和基于DFA状态的AC(Aho—Corasiek)算法,WM(Wu-Manber)算法
本论文讲解了面向中英文混合环境的多模式匹配算法,比较现有的4个主流的多模式匹配算法的性能和效率,非常的详细和实用,可以作为参考
在预处理阶段,AC自动机算法建立了三个函数,转向函数goto,失效函数failure和输出函数output,由此构造了一个树型有限自动机。 在搜索查找阶段,则通过这三个函数的交叉使用扫描文本,定位出关键字在文本中的所有...
AC-BM多模式匹配算法的研究与改进 ,张慧,罗守山,随着互联网行业的发展,信息的多渠道获得,信息的安全性得到了社会的广泛关注。本文对作为防火墙核心技术之一的模式匹配算法进行
模式匹配算法包括AC自动解 多模式匹配算法和KMP单模式匹配算法详解
多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 ...