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

原创
2013/04/01 10:17
阅读数 2.8K
    上个周末出去和姑娘们看电影,各种娱乐,忘记写博客了(话说我觉得前者更美好),这周没事儿,写一篇。
    先扯几句,说实话,我至今搞不懂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,有什么问题大家可以留言~~愚人节发帖子,很有喜感啊~

展开阅读全文
打赏
2
14 收藏
分享
加载中
路小磊博主

引用来自“temporary”的评论

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

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

暂时不知道你谁。不过我猜测是Ocean。
DFA的理论来自于我文章里提的那个博客。
没办法,没学扎实那会儿
2013/04/01 19:09
回复
举报
路小磊博主

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

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

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

你的应该是查找树,说是dfa很勉强,dfa一般是通用的状态转移,参见regexp实现。
2013/04/01 17:05
回复
举报
搞错了。。你这个应该是词法分析生成器吧,把它想得简单了。
2013/04/01 14:51
回复
举报
http://www.cnblogs.com/Ninputer/default.html?page=2这里有些关于DFA的资料,可以去看看。DFA完全不需要用树来表示。计算机程序就是状态机。你完全可以用switch控制结构来实现状态的转换。
2013/04/01 14:00
回复
举报
更多评论
打赏
5 评论
14 收藏
2
分享
返回顶部
顶部