论坛首页 Java企业应用论坛

DFA敏感词过滤------java版

浏览 24128 次
精华帖 (3) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-10-13   最后修改:2011-10-13
首先感谢ahuaxuan 写的帖子:http://www.iteye.com/topic/336577
再首先给还在上学的朋友们个忠告,一定要打好基础,数据结构、编译原理、算法导论等课程直接决定了你的编程水平
基础学不好,解决问题的思路会大大受限
有限自动机是编译原理的基础,可惜到今天才学会
DFA应用还是挺广泛的,全文搜索就要用到,想必去百度 google面试 这是必考题吧

言归正传
原文用python实现的,我在java版中基本上是照搬了ahuaxuan 的思想
所以就直接上代码了

/**
 * @author 徐良永
 * @Date   2011-10-13 上午9:23:43
 */
public class DFA {
	private static final Logger logger = LoggerFactory.getLogger(DFA.class);
	
	/**
	 * 根节点
	 */
	private TreeNode rootNode = new TreeNode();
	
	/**
	 * 关键词缓存
	 */
	private ByteBuffer keywordBuffer = ByteBuffer.allocate(1024);	
	
	/**
	 * 关键词编码
	 */
	private String charset = "GBK";

	/**
	 * 创建DFA
	 * @param keywordList
	 * @throws UnsupportedEncodingException 
	 */
	public void createKeywordTree(List<String> keywordList) throws UnsupportedEncodingException{
		
		for (String keyword : keywordList) {
			if(keyword == null) continue;
			keyword = keyword.trim();
			byte[] bytes = keyword.getBytes(charset);
			
			TreeNode tempNode = rootNode;
			//循环每个字节
			for (int i = 0; i < bytes.length; i++) {
				int index = bytes[i] & 0xff; //字符转换成数字
				TreeNode node = tempNode.getSubNode(index);
				
				if(node == null){ //没初始化
					node = new TreeNode();
					tempNode.setSubNode(index, node);
				}
				
				tempNode = node;
				
				if(i == bytes.length - 1){
					tempNode.setKeywordEnd(true);	 //关键词结束, 设置结束标志
					logger.debug("DFA:{}", keyword);
				}
			}//end for
		}//end for
		
	}
	
	/**
	 * 搜索关键字
	 */
	public String searchKeyword(String text) throws UnsupportedEncodingException{
		return searchKeyword(text.getBytes(charset));
	}
	
	/**
	 * 搜索关键字
	 */
	public String searchKeyword(byte[] bytes){
		StringBuilder words = new StringBuilder();
		
		if(bytes == null || bytes.length == 0){
			return words.toString();
		}
		
		TreeNode tempNode = rootNode;
		int rollback = 0;	//回滚数
		int position = 0; //当前比较的位置
		
		while (position < bytes.length) {
			int index = bytes[position] & 0xFF;
			keywordBuffer.put(bytes[position]);	//写关键词缓存
			tempNode = tempNode.getSubNode(index);
			
			//当前位置的匹配结束
			if(tempNode == null){ 
				position = position - rollback; //回退 并测试下一个字节
				rollback = 0;
				tempNode = rootNode;  	//状态机复位
				keywordBuffer.clear();	//清空
			}
			else if(tempNode.isKeywordEnd()){  //是结束点 记录关键词
				keywordBuffer.flip();
				String keyword = Charset.forName(charset).decode(keywordBuffer).toString();
				logger.debug("Find keyword:{}", keyword);
				keywordBuffer.limit(keywordBuffer.capacity());
				
				if( words.length() == 0 ) words.append(keyword);
				else words.append(":").append(keyword);
				
				rollback = 1;	//遇到结束点  rollback 置为1
			}else{	
				rollback++;	//非结束点 回退数加1
			}
			
			position++;
		}
		
		return words.toString();
	}
	
	public void setCharset(String charset) {
		this.charset = charset;
	}
	
}


关键字树占用内存是以256的平方增长的
第一层 256
第二层 256 * 256
第三层 256 * 256 * 256
。。。
内存的开销是很大的
所以最好设定关键词的最大长度,以控制内存的开销

看一下节点类
/**
 * 树节点
 * 每个节点包含一个长度为256的数组
 * @author 徐良永
 * @Date   2011-10-12 上午3:11:24
 */
public class TreeNode {
	private static final int NODE_LEN = 256;
	
	/**
	 * true 关键词的终结 ; false 继续
	 */
	private boolean end = false; 
	
	private List<TreeNode> subNodes = new ArrayList<TreeNode>(NODE_LEN);
	
	public TreeNode(){
		for (int i = 0; i < NODE_LEN; i++) {
			subNodes.add(i, null);
		}
	}
	
	/**
	 * 向指定位置添加节点树
	 * @param index
	 * @param node
	 */
	public void setSubNode(int index, TreeNode node){
		subNodes.set(index, node);
	}
	
	public TreeNode getSubNode(int index){
		return subNodes.get(index);
	}
	

	public boolean isKeywordEnd() {
		return end;
	}

	public void setKeywordEnd(boolean end) {
		this.end = end;
	}
}


每个节点包含一个标志,标示此节点是不是关键词的结束
另外包含256个子节点


测试结果
加载了16000个关键词,短的一个汉字 最长的有20个汉字的 
共占用内存 190M吧

速度:
从数据库中取了 5w 条信息 需要10s左右
10w条信息 16s左右

   发表时间:2011-10-14  
xly_971223 写道
首先感谢ahuaxuan 写的帖子:http://www.iteye.com/topic/336577
再首先给还在上学的朋友们个忠告,一定要打好基础,数据结构、编译原理、算法导论等课程直接决定了你的编程水平
基础学不好,解决问题的思路会大大受限
有限自动机是编译原理的基础,可惜到今天才学会
DFA应用还是挺广泛的,全文搜索就要用到,想必去百度 google面试 这是必考题吧



有个疑问,为何非要学编译原理,知道编译、链接的大致原理不就成了吗?
0 请登录后投票
   发表时间:2011-10-14  
ustcter 写道
xly_971223 写道
首先感谢ahuaxuan 写的帖子:http://www.iteye.com/topic/336577
再首先给还在上学的朋友们个忠告,一定要打好基础,数据结构、编译原理、算法导论等课程直接决定了你的编程水平
基础学不好,解决问题的思路会大大受限
有限自动机是编译原理的基础,可惜到今天才学会
DFA应用还是挺广泛的,全文搜索就要用到,想必去百度 google面试 这是必考题吧



有个疑问,为何非要学编译原理,知道编译、链接的大致原理不就成了吗?


学的是思想和解决问题的思路。刚刚学过有限自动机,没想到能用在这里,谢谢提醒了,以后认真学专业课
0 请登录后投票
   发表时间:2011-10-14  
我的理解是 4个汉字 8个 byte  那么最后一层将是  18446744073709551616个节点

如果真是这样..那这个东西根本不能用


还有一些地方

int index = bytes[i] & 0xff; //字符转换成数字   



byte 转 int 需要这么干么?这么干的好处是?


铭感词不建议这么干的..楼主可适当参考下分词的算法
0 请登录后投票
   发表时间:2011-10-14  
敏感词过滤一般用多模式匹配
0 请登录后投票
   发表时间:2011-10-14  
ansjsun 写道


int index = bytes[i] & 0xff; //字符转换成数字   



byte 转 int 需要这么干么?这么干的好处是?


避免符号扩展
0 请登录后投票
   发表时间:2011-10-14  
自动机什么的学了都还给老师了。。。好文,正好复习一下~
0 请登录后投票
   发表时间:2011-10-14   最后修改:2011-10-14
ansjsun 写道
我的理解是 4个汉字 8个 byte  那么最后一层将是  18446744073709551616个节点

如果真是这样..那这个东西根本不能用


还有一些地方

int index = bytes[i] & 0xff; //字符转换成数字   



byte 转 int 需要这么干么?这么干的好处是?


铭感词不建议这么干的..楼主可适当参考下分词的算法






我应该可以回答 byte 转 int的 这个问题,

byte 转int 是由8位 转到32位的,这样就有了两种扩展方式,0扩展 和1扩展,这要取决去最高位(符号位)是0 还是1

这样的话 如果是 1扩展,那前面的24位就全是1了,这样转换过去的 int  跟原 byte是不一样的,所以

必须 要&0xff 也就是保存 最低的8位

例如:byte x=(byte)0xa0; 然后x转为int后 会变成0xffffffa0,必须要&0xff

PS:刚开始 做服务器底层数据传输的时候,不知道byte转int必须要这个样子,
底层收到的 是byte数据,然后 解析计算的时候就出问题了
0 请登录后投票
   发表时间:2011-10-14   最后修改:2011-10-14
关键词过滤就是个杯具。有些要求严格,但是真要写无论你怎么过滤都难以干净。干脆直接禁言吧!!  关键词过滤还可以参考lucene中的词法分析
0 请登录后投票
   发表时间:2011-10-14  
和谐功能 还真是参考 lucene比较好 lz
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics