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

首先感谢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左右

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

学的是思想和解决问题的思路。刚刚学过有限自动机，没想到能用在这里，谢谢提醒了，以后认真学专业课

我的理解是 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数据，然后 解析计算的时候就出问题了

关键词过滤就是个杯具。有些要求严格，但是真要写无论你怎么过滤都难以干净。干脆直接禁言吧！！  关键词过滤还可以参考lucene中的词法分析

和谐功能 还真是参考 lucene比较好 lz