SpringBoot DFA實現(xiàn)敏感詞過濾功能
前言
敏感詞過濾系統(tǒng)已經(jīng)成為各大平臺的必備功能。無論是社交平臺的內容審核、電商系統(tǒng)的商品管理，還是游戲系統(tǒng)的聊天監(jiān)控，都需要高效可靠的敏感詞過濾機制來維護健康的內容生態(tài)。
傳統(tǒng)的字符串查找方式在處理大量敏感詞時性能急劇下降，而正則表達式在匹配復雜規(guī)則時更是捉襟見肘。
今天，介紹一種基于 DFA（有限狀態(tài)自動機）算法的高效敏感詞過濾方案，通過 Trie 樹數(shù)據(jù)結構實現(xiàn)毫秒級響應，輕松應對敏感內容的實時過濾需求。
為什么需要 DFA 算法
傳統(tǒng)方案的性能瓶頸
在敏感詞過濾的實際應用中，我們面臨著諸多挑戰(zhàn)。傳統(tǒng)的實現(xiàn)方式往往存在以下問題：
暴 力匹配的低效
// 時間復雜度：O(n × m × k)
// 隨著敏感詞數(shù)量增加，性能急劇下降
for (String word : sensitiveWords) {
if (text.contains(word)) {
// 處理敏感詞
}
}
這種簡單粗暴的方式在小規(guī)模應用中尚可接受，但當敏感詞數(shù)量達到數(shù)千甚至數(shù)萬時，處理一篇1000字的文章可能需要數(shù)秒時間，嚴重影響用戶體驗。
正則表達式的局限性 雖然正則表達式提供了強大的模式匹配能力，但在敏感詞過濾場景中卻存在明顯缺陷：
- 構建超大的正則表達式會導致編譯時間過長
- 動態(tài)添加敏感詞需要重新編譯正則表達式
- 內存占用隨敏感詞數(shù)量線性增長
- 匹配效率在復雜規(guī)則下大幅下降
DFA 算法的優(yōu)勢
DFA 算法通過構建狀態(tài)機模型，將敏感詞匹配過程轉化為狀態(tài)轉移，帶來了質的飛躍：
- 線性時間復雜度: O(n) - 只需遍歷文本一次，不受敏感詞數(shù)量影響
- 空間共享優(yōu)化: 敏感詞前綴共享存儲，顯著減少內存占用
- 確定性匹配: 無需回溯，避免正則表達式的回溯開銷
- 動態(tài)擴展友好: 支持運行時添加、刪除敏感詞，無需重建整個數(shù)據(jù)結構
以實際場景為例，當敏感詞庫從1000個擴展到10000個時：
- 暴力匹配算法耗時增加約10倍
- DFA算法耗時幾乎保持不變
DFA 算法原理解析
DFA 算法的數(shù)學本質
DFA（Deterministic Finite Automaton）是一種數(shù)學模型，它定義了一個五元組 M = (Q, Σ, δ, q?, F)：
- Q: 有限狀態(tài)集合
- Σ: 輸入字母表
- δ: 狀態(tài)轉移函數(shù) δ: Q × Σ → Q
- q?: 初始狀態(tài)
- F: 接受狀態(tài)集合
在敏感詞過濾中，每個狀態(tài)代表匹配到某個字符位置的狀態(tài)轉移路徑。
Trie 樹的可視化理解
Trie 樹是 DFA 的直觀實現(xiàn)，也稱為字典樹或前綴樹。讓我們通過一個具體例子來理解：
假設有以下敏感詞：["apple", "app", "application", "apply", "orange"]
構建的 Trie 樹結構如下：
root
├── a
│ └── p
│ └── p [結束] ← "app"
│ └── l
│ ├── e [結束] ← "apple"
│ ├── i
│ │ └── c
│ │ └── a
│ │ └── t
│ │ └── i
│ │ └── o
│ │ └── n [結束] ← "application"
│ └── y [結束] ← "apply"
└── o
└── r
└── a
└── n
└── g
└── e [結束] ← "orange"
Trie 樹結構的關鍵特征：
1. 前綴共享優(yōu)化：
- "app" 作為 "apple"、"application"、"apply" 的共同前綴，只存儲一次
- 從 "app" 節(jié)點分支出不同的后續(xù)字符路徑
2. 狀態(tài)轉移路徑：
- 每個
├──和└──表示一個字符狀態(tài)轉移 [結束]標記表示 DFA 的接受狀態(tài)（敏感詞結束）
3. 空間效率：
- 5個敏感詞只需要存儲 10 個字符節(jié)點（含重復字符）
- 如果單獨存儲需要 5 + 3 + 11 + 4 + 6 = 29 個字符
4. 查找效率：
- 查找 "application" 只需要 11 次字符比較
- 查找 "app" 只需要 3 次字符比較且可以提前終止
關鍵特征解釋
1. 前綴共享: "app" 作為 "apple"、"application"、"apply" 的前綴，只在樹中存儲一次
2. 節(jié)點狀態(tài): 每個節(jié)點代表 DFA 的一個狀態(tài)
3. 邊轉移: 每條邊代表一個字符輸入引起的狀態(tài)轉移
4. 接受狀態(tài): 標記 * 的節(jié)點表示敏感詞的結束狀態(tài)（接受狀態(tài)）
例如，當檢測文本 "I love apples" 時：
- 從根節(jié)點開始，遇到 'a' 轉移到 a 節(jié)點
- 遇到 'p' 轉移到 p 節(jié)點
- 遇到 'p' 轉移到 p 節(jié)點
- 遇到 'l' 轉移到 l 節(jié)點
- 遇到 'e' 轉移到 e 節(jié)點（到達接受狀態(tài)，發(fā)現(xiàn)敏感詞 "apple"）
- 繼續(xù)檢測 's' 時狀態(tài)轉移失敗，回到初始位置繼續(xù)檢測
狀態(tài)轉移的實際過程
假設我們要在文本 "I like apples and apps" 中查找敏感詞：
- 從根節(jié)點開始，遇到 'a'，轉移到 'a' 節(jié)點
- 遇到 'p'，轉移到 'p' 節(jié)點
- 遇到 'p'，轉移到 'p' 節(jié)點（此時檢測到 "app" 是敏感詞）
- 遇到 'l'，轉移到 'l' 節(jié)點
- 遇到 'e'，轉移到 'e' 節(jié)點（此時檢測到 "apple" 是敏感詞）
整個過程只需要一次線性遍歷，無需重復掃描或回溯。
核心實現(xiàn)詳解
1. Trie 節(jié)點結構設計
Trie 節(jié)點是整個 DFA 算法的基礎，每個節(jié)點代表一個狀態(tài)：
public class TrieNode {
// 子節(jié)點映射：字符 -> Trie節(jié)點
private Map<Character, TrieNode> children = new HashMap<>();
// 是否為敏感詞的結束節(jié)點
private boolean isEnd = false;
// 完整敏感詞內容（便于輸出）
private String keyword;
public TrieNode getChild(char c) {
return children.get(c);
}
public TrieNode addChild(char c) {
return children.computeIfAbsent(c, k -> new TrieNode());
}
public boolean hasChild(char c) {
return children.containsKey(c);
}
// getters and setters...
}
2. DFA 過濾器核心實現(xiàn)
以下是最精簡的 DFA 過濾器實現(xiàn)，包含了核心的匹配邏輯：
public class SensitiveWordFilter {
private TrieNode root;
private int minWordLength = 1;
public SensitiveWordFilter(List<String> sensitiveWords) {
this.root = buildTrie(sensitiveWords);
this.minWordLength = sensitiveWords.stream()
.mapToInt(String::length).min().orElse(1);
}
/**
* 構建 Trie 樹
*/
private TrieNode buildTrie(List<String> words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.addChild(c);
}
node.setEnd(true);
node.setKeyword(word);
}
return root;
}
/**
* 檢查是否包含敏感詞 - 核心 DFA 匹配算法
*/
public boolean containsSensitiveWord(String text) {
if (text == null || text.length() < minWordLength) {
return false;
}
char[] chars = text.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (dfaMatch(chars, i)) {
return true;
}
}
return false;
}
/**
* DFA 狀態(tài)轉移匹配
*/
private boolean dfaMatch(char[] chars, int start) {
TrieNode node = root;
for (int i = start; i < chars.length; i++) {
char c = chars[i];
if (!node.hasChild(c)) {
break; // 狀態(tài)轉移失敗
}
node = node.getChild(c);
if (node.isEnd()) {
return true; // 到達接受狀態(tài)
}
}
return false;
}
/**
* 查找并替換敏感詞
*/
public String filter(String text, String replacement) {
List<SensitiveWordResult> words = findAllWords(text);
// 從后往前替換，避免索引變化問題
StringBuilder result = new StringBuilder(text);
for (int i = words.size() - 1; i >= 0; i--) {
SensitiveWordResult word = words.get(i);
String stars = String.valueOf(replacement != null ? replacement : "*")
.repeat(word.getEnd() - word.getStart() + 1);
result.replace(word.getStart(), word.getEnd() + 1, stars);
}
return result.toString();
}
/**
* 查找所有敏感詞
*/
public List<SensitiveWordResult> findAllWords(String text) {
List<SensitiveWordResult> results = new ArrayList<>();
if (text == null || text.length() < minWordLength) {
return results;
}
char[] chars = text.toCharArray();
for (int i = 0; i < chars.length; i++) {
TrieNode node = root;
int j = i;
while (j < chars.length && node.hasChild(chars[j])) {
node = node.getChild(chars[j]);
j++;
if (node.isEnd()) {
results.add(new SensitiveWordResult(
text.substring(i, j), i, j - 1));
}
}
}
return results;
}
}
3. 敏感詞結果封裝
public class SensitiveWordResult {
private String word; // 敏感詞內容
private int start; // 起始位置
private int end; // 結束位置
public SensitiveWordResult(String word, int start, int end) {
this.word = word;
this.start = start;
this.end = end;
}
// getters and toString...
}
實戰(zhàn)應用場景
即時通訊系統(tǒng)中的實時過濾
在高并發(fā)的聊天系統(tǒng)中，敏感詞過濾需要滿足低延遲、高吞吐的要求：
public class ChatMessageFilter {
private SensitiveWordFilter wordFilter;
// 異步處理敏感詞檢測
private ExecutorService filterExecutor = Executors.newFixedThreadPool(10);
public CompletableFuture<Message> filterMessageAsync(Message message) {
return CompletableFuture.supplyAsync(() -> {
String content = message.getContent();
if (wordFilter.containsSensitiveWord(content)) {
// 實時替換
String filtered = wordFilter.filter(content, "***");
message.setContent(filtered);
// 記錄敏感詞統(tǒng)計
recordSensitiveWords(content);
}
return message;
}, filterExecutor);
}
private void recordSensitiveWords(String content) {
List<SensitiveWordResult> words = wordFilter.findAllWords(content);
// 統(tǒng)計敏感詞出現(xiàn)頻率，用于優(yōu)化詞庫
updateWordFrequency(words);
}
}
內容審核系統(tǒng)的多級策略
不同類型的敏感詞需要不同的處理策略：
public class ContentAuditor {
private SensitiveWordFilter highRiskFilter; // 高風險詞
private SensitiveWordFilter mediumRiskFilter; // 中風險詞
private SensitiveWordFilter lowRiskFilter; // 低風險詞
public AuditResult auditContent(String content) {
AuditResult result = new AuditResult();
// 按風險級別檢測
List<SensitiveWordResult> highRiskWords = highRiskFilter.findAllWords(content);
if (!highRiskWords.isEmpty()) {
result.setStatus(AuditStatus.REJECT);
result.setReason("包含高風險敏感詞");
return result;
}
List<SensitiveWordResult> mediumRiskWords = mediumRiskFilter.findAllWords(content);
if (!mediumRiskWords.isEmpty()) {
result.setStatus(AuditStatus.MANUAL_REVIEW);
result.setReason("包含中風險敏感詞，需要人工審核");
return result;
}
List<SensitiveWordResult> lowRiskWords = lowRiskFilter.findAllWords(content);
if (!lowRiskWords.isEmpty()) {
// 低風險詞匯直接過濾
String filtered = lowRiskFilter.filter(content, "***");
result.setFilteredContent(filtered);
result.setStatus(AuditStatus.PASS_WITH_FILTER);
} else {
result.setStatus(AuditStatus.PASS);
}
return result;
}
}
動態(tài)詞庫管理
實際項目中，敏感詞庫需要動態(tài)更新：
@Service
public class SensitiveWordManager {
private volatile SensitiveWordFilter filter;
private ScheduledExecutorService updateExecutor =
Executors.newSingleThreadScheduledExecutor();
@PostConstruct
public void init() {
loadWords();
// 定期更新詞庫
updateExecutor.scheduleAtFixedRate(this::loadWords, 0, 1, TimeUnit.HOURS);
}
public void loadWords() {
try {
// 從數(shù)據(jù)庫或配置中心加載最新詞庫
List<String> words = fetchLatestWords();
SensitiveWordFilter newFilter = new SensitiveWordFilter(words);
this.filter = newFilter;
log.info("敏感詞庫更新完成，當前詞數(shù)：{}", words.size());
} catch (Exception e) {
log.error("詞庫更新失敗", e);
}
}
public boolean containsSensitiveWord(String text) {
return filter != null && filter.containsSensitiveWord(text);
}
public String filterText(String text) {
return filter != null ? filter.filter(text, "***") : text;
}
}
高級優(yōu)化方案
對于不同規(guī)模的敏感詞過濾需求，基礎的 DFA 算法可能需要進一步優(yōu)化。以下是幾種常用的高級方案：
方案1：雙數(shù)組 Trie（Double-Array Trie）
核心思想：將 Trie 樹壓縮為兩個數(shù)組，減小內存使用。
// 雙數(shù)組結構示意 int[] base = new int[size]; // 狀態(tài)轉移基礎值 int[] check = new int[size]; // 狀態(tài)轉移檢查值 // 狀態(tài)轉移：next_state = base[current_state] + char_code // if check[next_state] == current_state: 轉移成功
適用場景：詞庫規(guī)模較大
優(yōu)點：內存占用減少 50%-80%
缺點：構建復雜度增加，動態(tài)更新困難
應用：搜索引擎、大型社交平臺的離線詞庫
方案2：AC 自動機（Aho-Corasick）
核心思想：在 Trie 基礎上增加失敗指針，實現(xiàn)一次遍歷匹配多個模式。
public class AhoCorasickAutomaton {
private Node root = new Node();
// Trie 節(jié)點結構
static class Node {
Map<Character, Node> children = new HashMap<>();
Node fail; // 失敗指針
List<String> output = new ArrayList<>(); // 輸出模式
}
// 構建自動機
public void build(List<String> patterns) {
// 1. 構建 Trie 樹
for (String pattern : patterns) {
Node node = root;
for (char c : pattern.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new Node());
}
node.output.add(pattern);
}
// 2. 添加失敗指針
Queue<Node> queue = new LinkedList<>();
// 初始化根節(jié)點的子節(jié)點
for (Node child : root.children.values()) {
child.fail = root;
queue.add(child);
}
// BFS 構建失敗指針
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Map.Entry<Character, Node> entry : current.children.entrySet()) {
char c = entry.getKey();
Node child = entry.getValue();
// 找到失敗指針
Node failNode = current.fail;
while (failNode != null && !failNode.children.containsKey(c)) {
failNode = failNode.fail;
}
child.fail = (failNode == null) ? root : failNode.children.get(c);
child.output.addAll(child.fail.output);
queue.add(child);
}
}
}
// 搜索匹配
public List<MatchResult> search(String text) {
List<MatchResult> results = new ArrayList<>();
Node node = root;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
// 失敗指針跳轉
while (node != null && !node.children.containsKey(c)) {
node = node.fail;
}
node = (node == null) ? root : node.children.get(c);
// 輸出匹配結果
for (String pattern : node.output) {
results.add(new MatchResult(pattern, i - pattern.length() + 1, i));
}
}
return results;
}
// 匹配結果
static class MatchResult {
String pattern;
int start;
int end;
public MatchResult(String pattern, int start, int end) {
this.pattern = pattern;
this.start = start;
this.end = end;
}
}
}
適用場景：多模式匹配、日志分析
優(yōu)點：可同時匹配多個敏感詞，無需多次遍歷
缺點：空間復雜度較高，實現(xiàn)相對復雜
應用：網(wǎng)絡安全、內容審核系統(tǒng)
方案3：分片 + 布隆過濾器預篩選
核心思想：通過分片降低單機壓力，用布隆過濾器快速過濾明顯不包含敏感詞的文本。
// 分片處理示例
public class ShardedFilter {
// 模擬分片
private List<SensitiveWordFilter> shards;
private BloomFilter<String> preFilter;
public boolean containsSensitive(String text) {
// 布隆過濾器預篩選
if (!preFilter.mightContain(text)) {
return false; // 肯定不包含敏感詞
}
// 分片精確匹配
int shardIndex = text.hashCode() % shards.size();
return shards.get(shardIndex).containsSensitiveWord(text);
}
}
適用場景：高并發(fā)、大規(guī)模文本處理
優(yōu)點：支持水平擴展，預處理可過濾大量無效請求
缺點：存在誤判概率，系統(tǒng)復雜度增加
應用：彈幕系統(tǒng)、即時通訊、微服務架構
總結
DFA 算法通過 Trie 樹結構，為敏感詞過濾提供了一個兼具效率和準確性的解決方案。
在實際應用中，需要根據(jù)具體的業(yè)務場景選擇合適的實現(xiàn)策略。
無論是追求極致性能的聊天系統(tǒng)，還是注重準確率的內容審核平臺，DFA 算法都能提供堅實的基礎支撐。
倉庫地址：https://github.com/yuboon/java-examples/tree/master/springboot-dfa
到此這篇關于SpringBoot DFA實現(xiàn)敏感詞過濾功能的文章就介紹到這了,更多相關SpringBoot敏感詞過濾內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要給大家介紹了關于Spring Boot對Future模式的支持的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用spring boot具有一定的參考學習價值，需要的朋友們下面來一起看看吧2019-01-01
SpringBoot?整合RabbitMq?自定義消息監(jiān)聽容器來實現(xiàn)消息批量處理
Spring Boot中提供了默認的監(jiān)聽器容器，但是有時候我們需要自定義監(jiān)聽器容器，來滿足一些特殊的需求，比如批量獲取數(shù)據(jù)，這篇文章主要介紹了SpringBoot?整合RabbitMq?自定義消息監(jiān)聽容器來實現(xiàn)消息批量處理,需要的朋友可以參考下2023-04-04
IDEA報錯"Cannot?resolve?symbol"問題的解決辦法
早上來了,打開idea發(fā)現(xiàn)注解等都變紅報錯can’t resolvesymbol,由于這個錯之前也報過,所以記錄一下,這篇文章主要給大家介紹了關于IDEA報錯"Cannot?resolve?symbol"問題的解決辦法,需要的朋友可以參考下2023-11-11
關于在IDEA中SpringBoot項目中activiti工作流的使用詳解
這篇文章主要介紹了關于在IDEA中SpringBoot項目中activiti工作流的使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
如何使用Comparator比較接口實現(xiàn)ArrayList集合排序
這篇文章主要介紹了如何使用Comparator比較接口實現(xiàn)ArrayList集合排序問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
IntelliJ IDEA 設置數(shù)據(jù)庫連接全局共享的步驟
在日常的軟件開發(fā)工作中,我們經(jīng)常會遇到需要在多個項目之間共享同一個數(shù)據(jù)庫連接的情況,默認情況下,IntelliJ IDEA 中的數(shù)據(jù)庫連接配置是針對每個項目單獨存儲的,幸運的是,IntelliJ IDEA 提供了一種方法來將數(shù)據(jù)庫連接配置設置為全局共享,從而簡化這一過程2024-10-10
SpringBoot中TypeExcludeFilter的作用及使用方式
在SpringBoot應用程序中,TypeExcludeFilter通過過濾特定類型的組件,使它們不被自動掃描和注冊為bean,這在排除不必要的組件或特定實現(xiàn)類時非常有用,通過創(chuàng)建自定義過濾器并注冊到spring.factories文件中,我們可以在應用啟動時生效2025-01-01
本文主要介紹了Java虛擬機（JVM）的內存劃分、類加載機制以及垃圾回收機制,JVM的內存劃分為程序計數(shù)器、棧、堆和方法區(qū),類加載機制包括類加載過程、加載器模型和雙親委派模型,垃圾回收機制主要包括標記-清除、標記-復制、標記-整理和分代回收算法2025-02-02
這篇文章主要介紹了maven實現(xiàn)jar包導入+導出方式,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-07-07
這篇文章主要給大家介紹了關于Java多線程之線程安全問題的相關資料,Java多線程中線程安全問題是一個常見的問題,因為多個線程可能同時訪問共享的資源,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2023-11-11