本文简单介绍下敏感词或者脏词检测算法。
经典的AC算法由三部分构成,goto表,fail表和output表,共包含四种具体的算法,分别是计算三张查找表的算法以及AC算法本身。
goto表就是一棵trie树
)这个表是trie树没有的,加了这个表,AC自动机就看起来不像一棵树,而像一个图
)确定性有穷自动机,用于正则表达式的匹配,最长左子式匹配
public void createKeyWord(String keyWord) {
Map nowMap = sensitiveWordMap;
for (Character c : keyWord.toCharArray()) {
Object obj = nowMap.get(c);
if (obj == null) {
Map<String, Object> childMap = new HashMap<>();
childMap.put("isEnd", "false");
nowMap.put(c, childMap);
nowMap = childMap;
} else {
nowMap = (Map) obj;
}
}
nowMap.put("isEnd", "true");
}
public class WordNode {
private int value; // 节点名称
private List<WordNode> subNodes; // 子节点
private boolean isLast;// 默认false
public WordNode(int value) {
this.value = value;
}
public WordNode(int value, boolean isLast) {
this.value = value;
this.isLast = isLast;
}
//......
}