起因
要写一个敏感词过滤,开始想着就写个循环就行了,但发现敏感词还挺多,而且会越来越多,循环的效率就太差了。于是就写个简单的字典树来做关键词查找。可以用于敏感词查询,也可以用于大量关键词查找场景,比如直播弹幕的关键词查找。
代码
目前只实现了正序查找第一个匹配的关键词,后面再增加其它。
代码放到了github上:https://github.com/ligb888/trie-tree
实现代码(包含了返回找到关键词和只判断不返回):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| public class TrieTreeUtil {
private final HashMap<Character, TrieNode> children = new HashMap<>();
public void add(String word){ if(StringUtils.isBlank(word) || StringUtils.isBlank(word.trim())){ return; } word = word.trim().replace(" ", "");
char[] keys = word.toCharArray(); HashMap<Character, TrieNode> point = children; for (int i = 0; i < keys.length; i++) { TrieNode node = point.get(keys[i]); if (node == null) { node = new TrieNode(); point.put(keys[i], node); } if (i == (keys.length - 1)) { node.setWord(word); break; } if (node.getChildren() == null) { node.setChildren(new HashMap<>()); } point = node.getChildren(); } }
public String contains(String word){ if(StringUtils.isBlank(word) || StringUtils.isBlank(word.trim())){ return null; } word = word.trim().replace(" ", ""); char[] keys = word.toCharArray(); for(int i = 0; i < keys.length; i++){ String ret = contains(keys, i, children); if(ret != null){ return ret; } } return null; }
private String contains(char[] keys, int begin, HashMap<Character, TrieNode> children){ for(int i = begin; i < keys.length; i++){ TrieNode node = children.get(keys[i]); if (node == null) { return null; } if(node.getWord() != null){ return node.getWord(); } children = node.getChildren(); } return null; }
public HashMap<Character, TrieNode> getChildren() { return children; } }
|
TrieNode:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public class TrieNode implements Serializable {
private String word; private HashMap<Character, TrieNode> children;
public String getWord() { return word; }
public void setWord(String word) { this.word = word; }
public HashMap<Character, TrieNode> getChildren() { return children; }
public void setChildren(HashMap<Character, TrieNode> children) { this.children = children; } }
|
效率对比
测试设备:2014年macbook pro,i5 4258U,8G
测试参数1:2500关键词,10万次查询:
样本类型 |
for循环 |
字典树 |
前匹配-长度20 |
1308毫秒 |
96毫秒 |
不匹配-长度20 |
14186毫秒 |
149毫秒 |
不匹配-长度100 |
32715毫秒 |
556毫秒 |
测试参数2:56000关键词,10万次查询:
样本类型 |
for循环 |
字典树 |
前匹配-长度20 |
73088毫秒 |
132毫秒 |
不匹配-长度20 |
225387毫秒 |
210毫秒 |
不匹配-长度100 |
452902毫秒 |
549毫秒 |
可以看到在关键词较多时,循环的效率下降非常快,字典树的效率几乎不受关键词数量影响,但他们都受到文本长度影响。