文档章节

common-tools(3)之基于DFA的敏感词查找

路小磊
 路小磊
发布于 2013/04/01 10:17
字数 513
阅读 1022
收藏 14
    上个周末出去和姑娘们看电影,各种娱乐,忘记写博客了(话说我觉得前者更美好),这周没事儿,写一篇。
    先扯几句,说实话,我至今搞不懂DFA(有限状态自动机)是个怎样的东西,大学那会儿昏昏沉沉,除了漂亮的计算机老师,啥也没记住……刚才搜搜维基百科,一堆奇形怪状的符号的也懒的看了,就说说我的理解吧(只针对需求)。应该说,这种方法是一种“空间换时间”的方法,将一堆敏感词构建成一棵树,然后载入文本来查找这棵树,据说效率很高。


    OK,进入主题。这个工具方法其实来自网上搜的一篇博文,地址:


    http://ahuaxuan.iteye.com/blog/336577?


    博客中应该对DFA理论作了一些介绍,有兴趣的可以去看看,并且博主提供了源代码。我的工具类中这个功能就是根据其源码改进而来的。先说使用方法,给出Demo源码。

package com.baijob.commonTools.wordSraech;

import org.junit.Assert;
import org.junit.Test;

import com.baijob.commonTools.wordSearch.Words;

public class WordSearchTest {
	@Test
	public void wordSearchTest() {
		Words words = new Words();
		//----------------------------添加敏感词 start
		words.addWord("敏感词1");
		words.addWord("敏感词2");
		words.addWord("敏感词3");
		words.addWord("敏感词4");
		words.addWord("敏感词5");
		//----------------------------添加敏感词 end
		
		String content = "我是一句话,我包含了敏感词2,你能找到敏感词2吗?还有敏  感  词4";
		//给定文本是否包含敏感词
		Assert.assertTrue(words.contains(content));
		//返回第一个找到的敏感词
		System.out.println(words.getFindedFirstWord(content)); //敏感词2
		//返回找到的所有敏感词
		System.out.println(words.getFindedAllWords(content));	    //[敏感词2, 敏感词2, 敏感词4]
	}
}

源码请看这里https://github.com/looly/common-tools/tree/master/src/main/java/com/baijob/commonTools/wordSearch

除了基本的方法,此类还有一些重载方法,多个一个Type参数,方便区分不同类型的敏感词从而分分别查找。

OK,有什么问题大家可以留言~~愚人节发帖子,很有喜感啊~

© 著作权归作者所有

共有 人打赏支持
路小磊

路小磊

粉丝 357
博文 54
码字总数 41709
作品 5
乌海
程序员
私信 提问
加载中

评论(5)

路小磊
路小磊

引用来自“temporary”的评论

你的问题简单说就是带跳过特殊字符的字符串搜索问题。
对于单串,我可以先全文trim掉特殊字符,然后kmp。
对于多串,我可以先全文trim掉特殊字符,然后构建静态查找树查找。

你的应该是查找树,说是dfa很勉强,dfa一般是通用的状态转移,参见regexp实现。

暂时不知道你谁。不过我猜测是Ocean。
DFA的理论来自于我文章里提的那个博客。
没办法,没学扎实那会儿
路小磊
路小磊

引用来自“优游幻世”的评论

搞错了。。你这个应该是词法分析生成器吧,把它想得简单了。

恩,没用到那么深入,只是简单的查找树。以后有机会深入研究下吧~
多谢你给的帖子~~
temporary
temporary
你的问题简单说就是带跳过特殊字符的字符串搜索问题。
对于单串,我可以先全文trim掉特殊字符,然后kmp。
对于多串,我可以先全文trim掉特殊字符,然后构建静态查找树查找。

你的应该是查找树,说是dfa很勉强,dfa一般是通用的状态转移,参见regexp实现。
优游幻世
优游幻世
搞错了。。你这个应该是词法分析生成器吧,把它想得简单了。
优游幻世
优游幻世
http://www.cnblogs.com/Ninputer/default.html?page=2这里有些关于DFA的资料,可以去看看。DFA完全不需要用树来表示。计算机程序就是状态机。你完全可以用switch控制结构来实现状态的转换。
双数组字典树关键词查询匹配和替换

大家在进行关键词匹配和替换的时候都是用的什么算法?很多人都可能有这样的需求,比如聊天文本中的敏感词替换、html文本中的关键词加超链接等。不深入技术算法和时刻关注程序性能的人来说,就...

银杏果果
2016/12/24
174
1
基于DFA敏感词查询的算法简析

文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/ 1.背景 项目中需要对敏感词做一个过滤,首先有几个方案可以选择: a.直接将敏感词组织成S...

李晓晖
2016/10/14
0
0
层级hashmap过滤敏感词思路

https://blog.csdn.net/gotohailang/article/details/38257627 敏感词过滤-使用hashmap实现dfa算法 假设敏感词有 中国人 中国男人 法轮 1、构建一个如下的数据结构 2、使用敏感词数据结构过滤...

ka_ko
2018/08/25
0
0
关于java中敏感词检测的一些总结

Tek_Eternal
2014/09/01
0
0
基于DFA的敏感词检测和替换模块--SmallGFW

smallgfw: 一个基于DFA的敏感词检测和替换模块,用法如doctest所示。 >>> gfw = GFW() >>> gfw.set(["sexy","girl","love","shit"])#设置敏感词列表 >>> s = gfw.replace("shit!,Cherry is a......

fxsjy
2012/03/07
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

智能合约编程/Dapp漏洞 -- 小心使用构造函数

构造函数是一个比较特殊的函数,在构造函数里会执行一些初始化合约是比较关键的功能。在Solidity 版本0.4.22之前,构造函数是一个和合约同名的函数。所以如果在开发过程中,合约名变了的话,...

怎当她临去时秋波那一转
22分钟前
0
0
JDK8发送邮件报错:Network is unreachable -- preferIPv4Stack

摘要: 使用javamail发送邮件时,老是提示Network is Network: ? 1 2 3 4 com.sun.mail.util.MailConnectException: Couldn't connect to host, port: smtp. com.sun.mail.util.MailConnec......

spinachgit
28分钟前
0
0
spring cloud feign 上传文件报关于not a type supported by this encoder解决方案

转载自:https://blog.csdn.net/qq_32786873/article/details/79756720

yan_liu
39分钟前
0
0
架构的“一小步”,业务的一大步

前言: 谈到“架构”这两个字,会有好多的名词闪现,比如:分层架构、事件驱动架构、DDD、CQRS等。亦或者一堆的软件设计原则,如:KISS原则(Keep it Simple and Stupid)、SOLID原则(单一责任...

阿里云官方博客
41分钟前
1
0
倒计时

DynamicConfig Utils CustomCountDownTimer CountdownView BaseCountdown BackgroundCountdown

lsy999
45分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部