使用DFA实现文字过滤

只能重建这颗书，建完之后替换树，呵呵

这个我也考虑过
就是觉得这样的话系统有一段时间占用的内存过大
不过不这样的话
也没有什么好的办法
我测了一下我的
2w个关键字
大约需要23M内存

看了一下，不需要重新构造，只需要把新增的关键词拿出来，执行建树时for循环里的代码就可以了

删除，或者修改的时候还是比较麻烦的

20多M内存不算什么了.  这个算法应该是最快的了. O(N)的复杂度. 难道还能写出log(N)的复杂度?  这个算法唯一是在增加和删除, 内存压缩, 内存利用效率上, 看你怎么写程序了. 但是国外有不少关于这个算法增强的paper, 文化低, 看的不是很明白.

这个算法结合动态规划算法 能做出比较精确的中文分词---非专业分词使用是相当好了. 我在实现过一部分:)

很不想做文字过滤....可还是做了. 不然天朝锦衣卫天天找你家麻烦.

我用java写了一个，直接基于字符构造一个树、

public class DFA {
	private String[] arr = {"DFA", "恶心", "DA"};
	private Node rootNode = new Node('R');
	
	private String content = "Hello DFA World DFA, HaHa! 恶心";
	
	private List<String> words = new ArrayList<String>();   
	private List<String> word = new ArrayList<String>();
	int a = 0;
	
	private void searchWord() {
		char[] chars = content.toCharArray();
		Node node = rootNode;
		while(a<chars.length) {
			node = findNode(node,chars[a]);
			if(node == null) {
				node = rootNode;
				a = a - word.size();
				word.clear();
			} else if(node.flag == 1) {
				word.add(String.valueOf(chars[a]));
				StringBuffer sb = new StringBuffer();
				for(String str : word) {
					sb.append(str);
				}
				words.add(sb.toString());
				a = a - word.size() + 1;
				word.clear();
				node = rootNode;
			} else {
				word.add(String.valueOf(chars[a]));
			}
			a++;
		}
	}
	
	private void createTree() {
		for(String str : arr) {
			char[] chars = str.toCharArray();
			if(chars.length > 0)
				insertNode(rootNode, chars, 0);
		}
	}
	
	private void insertNode(Node node, char[] cs, int index) {
		Node n = findNode(node, cs[index]);
		if(n == null) {
			n = new Node(cs[index]);
			node.nodes.add(n);
		}
		
		if(index == (cs.length-1))
			n.flag = 1;
			
		index++;
		if(index<cs.length)
			insertNode(n, cs, index);
	}
	
	private Node findNode(Node node, char c) {
		List<Node> nodes = node.nodes;
		Node rn = null;
		for(Node n : nodes) {
			if(n.c==c) {
				rn = n;
				break;
			}
		}
		return rn;
	}
	
	public static void main(String[] args) {
		DFA dfa = new DFA();
		dfa.createTree();
		dfa.searchWord();
		System.out.println(dfa.words);
	}
	
	
	private static class Node {
		public char c;
		public int flag; //1：表示终结，0：延续
		public List<Node> nodes = new ArrayList<Node>();
		
		public Node(char c) {
			this.c = c;
			this.flag = 0;
		}
		
		public Node(char c, int flag) {
			this.c = c;
			this.flag = flag;
		}
	}
}

In [1]: for a in range(10):
   ...:     print a
   ...:     a = a + 5
   ...:
0
1
2
3
4
5
6
7
8
9

In [2]: for a in xrange(10):
   ...:     print a
   ...:     a = a + 5
   ...:
0
1
2
3
4
5
6
7
8
9

我并没有说xrange有bug,你要仔细看一下我的代码，那句话是有上下文的。

text.txt:
中国人
words.txt:
中国
中国人

result:
cost time :  0.0160000324249
I have find some words as  1
中国 1

这种情况有问题的,而且不能以ab,bc这种情况来回退.
请问楼主如何处理?

再复杂一点:
words.txt:
中国 国人 中国人

我期望的结果是:
中国 1
国人 1
中国人 1

请教一下要实现这种需求,应该在算法上做些什么改进?

还有个问题，我的违禁词汇是av，用户输入have，但是被检测出来了，这个该怎么改进