`
buddie
  • 浏览: 185551 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论
阅读更多

文章大约分为以下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);
	}
}

 

  • 大小: 100.8 KB
  • 大小: 101.7 KB
  • 大小: 96.5 KB
分享到:
评论
1 楼 buddie 2018-08-30  
不知道为什么图片丢了,又重新补的图片

相关推荐

    java版的AC多模式匹配算法

    AC多模式匹配算法 特点:应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点:一是扫描文本时完全不需要回溯,二是时间复杂度为O(n)与关键字的数目和长度无关,但所需时间和文本长度以及所有关键字...

    PHP版的AC多模式匹配算法

    AC多模式匹配算法 特点:应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点:一是扫描文本时完全不需要回溯,二是时间复杂度为O(n)与关键字的数目和长度无关,但所需时间和文本长度以及所有关键字...

    AC多模式匹配算法论文研究报告

    AC多模式匹配算法,也是由贝尔实验室的传奇人物AHO(阿霍)开创的基于前缀自包含的模式匹配算法,本ppt从一个系统的角度阐释了本论文的重点。关于完全规避失败转换的部分,PPT中并没有明确说明。复现代码在PPT中嵌入...

    AC-BM 多模式匹配算法

    **AC-BM 多模式匹配算法** AC-BM(Aho-Corasick-BM)算法是一种结合了Aho-Corasick算法和Boyer-Moore算法的字符串匹配方法,主要用于在一个大文本串中高效地查找多个模式串。这种算法提高了在大量模式下搜索文本的...

    多模式匹配算法实现及测试代码

    本文将深入探讨两种经典的多模式匹配算法:Aho-Corasick (AC) 算法和 Wu-Manber (WM) 算法,并提供相关的实现及测试代码。 首先,我们来了解**Aho-Corasick (AC) 算法**。AC算法是在1975年由Aho、Corasick两位科学...

    多模式匹配算法 AC_BM

    在计算机科学领域,多模式匹配算法是用于在一个文本串中搜索多个模式串的高效方法。AC_BM算法,即Aho-Corasick自动机与Boyer-Moore算法的结合,是这类问题的一个强大解决方案。它结合了两种经典的字符串搜索算法,以...

    多模式匹配算法及硬件实现.docx

    现有的多模式匹配算法主要包括 AC 自动机算法、基于后缀树的多模式匹配算法和基于后缀数组的多模式匹配算法等。 AC 自动机算法是一种经典的多模式匹配算法,它基于 Aho-Corasick 自动机模型实现。AC 自动机算法的...

    一种面向科技文献元数据增量数据规范的多模式匹配算法.docx

    多模式匹配算法主要分为三类:基于有限状态自动机(FSA)的算法,如Aho-Corasick(AC)算法;基于Hash散列的算法,如Wu-Manber(WM)算法;以及其他技术实现的算法,如位并行算法。AC算法虽然匹配效率高,无需回溯,...

    多模式匹配算法 AC

    AC自动机,全称为Aho-Corasick算法,是由Aho和Corasick在1975年提出的,主要用于字符串的多模式匹配。它在KMP算法的基础上进行了扩展,能够一次性处理多个模式串,极大地提高了在文本中查找多个目标字符串的效率。 ...

    一种存储优化的多模式匹配算法

    AC(Aho-Corasick)自动机是经典的多模式匹配算法,但在模式串字符集较大的情况下,AC自动机的存储开销较大。为降低存储开销提出了存储优化的多模式匹配算法SMMA,该算法在Trie树建立阶段利用正向表来存储每个状态的...

    AC自动机算法(Aho-Corasick 多模式匹配算法)

    AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现

    无回溯的模式匹配算法源程序

    在实际应用中,无回溯的模式匹配算法不仅可以用于简单的文本查找,还可以结合其他数据结构和算法,如Trie树、后缀数组或AC自动机,进一步提升性能。例如,对于大规模文本库的搜索,可以预先构建这些数据结构,将模式...

    论文研究-病毒特征检测中改进的多模式匹配算法.pdf

    针对病毒特征检测中码串长度对模式匹配算法性能影响的问题, 结合基于码串长度的特征集自适应分类思路, 提出了两种改进的多模式精确匹配算法, 即NAC_BM和NWM_QS。改进算法通过引入文本窗口的前缀字符块WB增加了跳跃...

Global site tag (gtag.js) - Google Analytics