前綴樹的基本性質
1.根節(jié)點不包含字符熔掺，除根節(jié)點外每一個節(jié)點都只包含一個字符架曹。
2.從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應的字符串。
3.每個節(jié)點的所有子節(jié)點包含的字符都不相同。
數(shù)據(jù)結構：每一個TrieNode中定義一個哈希表，含有孩子節(jié)點的，即下一個字符的TrieNode炬称。
private class TrieNode {
// true 關鍵詞的終結 ； false 繼續(xù)
private boolean end = false;
// key下一個字符鸡号，value是對應的節(jié)點
private Map<Character, TrieNode> subNodes = new HashMap<>();
// 向指定位置添加節(jié)點樹
void addSubNode(Character key, TrieNode node) {
subNodes.put(key, node);
}
// 獲取下個節(jié)點
TrieNode getSubNode(Character key) {
return subNodes.get(key);
}
boolean isKeywordEnd() {
return end;
}
void setKeywordEnd(boolean end) {
this.end = end;
}
public int getSubNodeCount() {
return subNodes.size();
}
}
類中設置成員變量转砖，根節(jié)點，不包含任何字符鲸伴。
private TrieNode rootNode = new TrieNode();
添加敏感詞到前綴樹中
注意構造樹時如果根節(jié)點沒有孩子節(jié)點府蔗，要初始化再添加到哈希表中。
private void addWord(String lineTxt) {
TrieNode tempNode = rootNode;
// 循環(huán)每個字節(jié)
for (int i = 0; i < lineTxt.length(); ++i) {
Character c = lineTxt.charAt(i);
// 過濾空格
if (isSymbol(c)) {
continue;
}
TrieNode node = tempNode.getSubNode(c);
if (node == null) { // 沒初始化
node = new TrieNode();
tempNode.addSubNode(c, node);
}
tempNode = node;
if (i == lineTxt.length() - 1) {
// 關鍵詞結束汞窗， 設置結束標志
tempNode.setKeywordEnd(true);
}
}
}
過濾敏感詞
設置了三個指針幫助判斷姓赤。
如果字符是空格類型，并且是根節(jié)點情況仲吏，直接添加字符不铆，移動begin，pos指針裹唆，temp不變誓斥。相當于直接跳過再接著尋找。非根節(jié)點則只用移動pos指針许帐。因為非根節(jié)點情況相當于已經(jīng)再尋找敏感詞的過程中了劳坑，只需要跳過該空格繼續(xù)尋找即可。
在當前節(jié)點的哈希表中尋找是否有對應字符的孩子節(jié)點成畦，如果未找到距芬，當前字符不是敏感詞。直接添加當前字符循帐。pos框仔，begin指針后移一位，temp指針回到根節(jié)點拄养。
如果找到并且不是關鍵字結尾离斩，只需要pos指針移動。
如果找到并且是關鍵字結尾瘪匿，添加關鍵字跛梗。pos指針后移一位，begin指向pos柿顶，temp返回根節(jié)點茄袖。
注意最后還要添加result.append(text.substring(begin));因為當最后循環(huán)不是敏感詞時候操软，只會移動Pos而沒有添加嘁锯。所以最后一次遍歷不能漏掉。
public String filter(String text) {
if (StringUtils.isBlank(text)) {
return text;
}
String replacement = DEFAULT_REPLACEMENT;
StringBuilder result = new StringBuilder();
TrieNode tempNode = rootNode;
int begin = 0; // 回滾數(shù)
int position = 0; // 當前比較的位置
while (position < text.length()) {
char c = text.charAt(position);
// 空格直接跳過
if (isSymbol(c)) {
if (tempNode == rootNode) {
result.append(c);
++begin;
}
++position;
continue;
}
tempNode = tempNode.getSubNode(c);
// 當前位置的匹配結束
if (tempNode == null) {
// 以begin開始的字符串不存在敏感詞
result.append(text.charAt(begin));
// 跳到下一個字符開始測試
position = begin + 1;
begin = position;
// 回到樹初始節(jié)點
tempNode = rootNode;
} else if (tempNode.isKeywordEnd()) {
// 發(fā)現(xiàn)敏感詞， 從begin到position的位置用replacement替換掉
result.append(replacement);
position = position + 1;
begin = position;
tempNode = rootNode;
} else {
++position;
}
}
result.append(text.substring(begin));
return result.toString();
}
因為有可能存在敏感詞中間夾著宮格家乘，非法字符等形式蝗羊，所以必須對這種類型進行判斷。判斷邏輯可以不同仁锯。
private boolean isSymbol(char c) {
int ic = (int) c;
// 0x2E80-0x9FFF 東亞文字范圍
return !CharUtils.isAsciiAlphanumeric(c) && (ic < 0x2E80 || ic > 0x9FFF);
}
具體項目中耀找，可以將關鍵字保存到文件，然后讀取文件構建前綴樹
@Override
public void afterPropertiesSet() throws Exception {
rootNode = new TrieNode();
try {
InputStream is = Thread.currentThread().getContextClassLoader()
.getResourceAsStream("SensitiveWords.txt");
InputStreamReader read = new InputStreamReader(is);
BufferedReader bufferedReader = new BufferedReader(read);
String lineTxt;
while ((lineTxt = bufferedReader.readLine()) != null) {
lineTxt = lineTxt.trim();
addWord(lineTxt);
}
read.close();
} catch (Exception e) {
logger.error("讀取敏感詞文件失敗" + e.getMessage());
}
}
