java实现基于Trie树的敏感词过滤算法

思想

载入敏感词文件，构造敏感词trie树，对输入文本按照trie树的单个字符进行依次比对，若相等，则输入文本和树都向下一个字符移动，直到不相等时（为非敏感词，结束该处比对），或者直到相等时（为敏感词汇，对其进行替换）。从下一个字符开始与树从根处进行重复比对。

进行一次过滤时间的复杂度：O(n)

图解流程

构造前缀树

敏感词：xy，ab，ac
待匹配字符：aacxd

初始化
依次匹配

从待匹配字符串中选取position指向的字符，去前缀树中查找，tempNode下子节点是否有该字符。有则将position+1，将tempNode指向该关键字。

例：positon指向开始的a，去root下查找，有子节点a，将position指向position+1，将tempNode指向a。

重复上述步骤，从待匹配字符串中选取position指向的字符，去前缀树中查找，tempNode下子节点是否有该字符。没有则将position指向begin+1，之后begin指向begin+1，将tempNode重新指回root。

例：继续向下寻找，此时position为a，tempNode为a，tempNode下的子节点为c/d，子节点中不存在positon，因此将position和begin都指向begin+1,tempNode指回root。

继续向下匹配，情况如步骤1.

例：position为a，tempNode下有节点a，相同，tempNode指向a，position = position+1

继续向下匹配，position和tempNode中的子节点相同时，并且该子节点为叶子结点，则匹配到敏感词，关键词为begin到position处的字符。将其替换，然后begin和position都指向position+1，tempNode重新指回root，对后续字符串依次匹配。

例：positon为c，tempNode的子节点中有c，并且为叶子结点，匹配到该关键词，对其进行处理。然后将tempNode指回root，begin和position指向position+1

定义trie树

private class TrieNode{
	//当前节点是否为词末
	private boolean end = false;
	//存放
	Map<Character,TrieNode> subNode = new HashMap<>();
	public void addNode(Character key,TrieNode node){
		subNode.put(key,node);
	}
	TrieNode getsubNode(Character key){
		return subNod.get(key);
	}
	void setKeywordEnd(boolean end){
		this.end = end;
	}
	boolean isKeywordEnd(){
		return end;
	}
}

构造关键词前缀树

private TrieNode root = new TrieNode();
private void addWord(String lineText){
	TrieNode tempNode = root;
	for (int i=;i<lineText.length();i++){
		Character word = lineText.charAt(i);
		TrieNode node = tempNode.getsubNode(word);
		if (node==null){
			node = new TrieNode ();
			tempNode.addNode(word,node);
		}
		tempNode = node;
		if (i==lineText.length-1){
			tempNode.setKeywordEnd(true);
		}
	}
}

实现过滤

public String filter(String text){
	if(text==null||String.length==0)
		return text;
	StringBuilder result = new StringBuilder();
	String replace = "**";
	TrieNode tempNode = root;
	int begin = 0;
	int position = 0;
	while(position<text.length()){
		char word = text.charAt(position);
		tempNode = tempNode.getsubNode(word);
		if (tempNode == null){
			result.append(text.charAt(begin));
			position = begin+1;
			begin = position;
		} else if (tempNode.isKeywordEnd()){
			result.append(replace);
			position = position+1;
			begin = position;
			tempNode = root;
		} else{
			position++;
		}
	}
	result.append(text.subString(begin));
	return result.toString();
}

扩展

敏感词文件读取：

使用外部文件保存敏感词信息，在初始化时每取一个置入树结构中。

分隔符过滤：

在实现过滤的过程中，对输入字符串的当前字符进行判别是否为东亚文字，根据当前tempNode位置是否指向root上决定是将该字符跳过还是替换。

思想
图解流程
1. 构造前缀树
2. 依次匹配
定义trie树
构造关键词前缀树
实现过滤
扩展
1. 敏感词文件读取：
2. 分隔符过滤：

思想