當(dāng)前位置：首頁(yè) > 运维知识 > windows >内容正文

windows

构建健康游戏环境：DFA算法在敏感词过滤的应用

發(fā)布時(shí)間：2024/1/5 windows 32 coder

生活随笔收集整理的這篇文章主要介紹了构建健康游戏环境：DFA算法在敏感词过滤的应用小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

現(xiàn)在的游戲有敏感詞檢測(cè)這一點(diǎn)，相信大家也不陌生了，不管是聊天，起名，簽名還是簡(jiǎn)介，只要是能讓玩家手動(dòng)輸入的地方，一定少不了敏感詞識(shí)別，至于識(shí)別之后是拒絕修改還是星號(hào)替換，這個(gè)就各有各的做法了，但是繞不開的一定是需要高效的敏感詞檢測(cè)機(jī)制。

相信大家對(duì)于游戲里聊天框的以下內(nèi)容已經(jīng)不陌生了

"我***"
“你真牛*”
“你是不是傻*”

一個(gè)垃圾的游戲環(huán)境是非常影響玩游戲的心情的，看到這些，就知道游戲已經(jīng)幫我們屏蔽掉了那些屏蔽字了，對(duì)于玩游戲而言，心里會(huì)好受很多。敏感詞識(shí)別對(duì)于游戲的重要性不言而喻。當(dāng)然，除了游戲，也有很多業(yè)務(wù)場(chǎng)景可能需要敏感詞檢測(cè)，如果你接到這樣一個(gè)需求的時(shí)候，你會(huì)怎么做？*

一、原生API

作為Java程序員，我的第一反應(yīng)，一定是使用jdk原生的String類提供的contain或replace方法來進(jìn)行包含判斷或字符替換，這是最簡(jiǎn)單直接的方式。那我們就來看看String的實(shí)現(xiàn)方式：

contains

String在java中以char數(shù)組形式存儲(chǔ)，而String.contains的實(shí)現(xiàn)，實(shí)際上是對(duì)數(shù)組的遍歷查找匹配

// 最終調(diào)用方法
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
		// ...
}

replace

String.replace有4個(gè)接口，實(shí)現(xiàn)為正則匹配替換或直接遍歷替換

public String replace(char oldChar, char newChar) {
	// 直接進(jìn)行字符串遍歷，替換第一個(gè)匹配的字符串
}
public String replace(CharSequence target, CharSequence replacement) {
	// 創(chuàng)建Pattern，使用LITERAL模式進(jìn)行正則匹配替換replaceAll
    	// 當(dāng)設(shè)置LITERAL標(biāo)志時(shí)，輸入字符串中的所有字符都被視為普通字符。
        // 這意味著正則表達(dá)式的特殊字符，如點(diǎn)號(hào)（.）、星號(hào)（*）、加號(hào)（+）等，都將失去它們?cè)谡齽t表達(dá)式中的特殊意義，被直接視為普通字符。
}
public String replaceAll(String regex, String replacement) {
	// 創(chuàng)建Pattern，使用正則表達(dá)式模式匹配替換replaceAll
}
public String replaceFirst(String regex, String replacement) {
	// 創(chuàng)建Pattern，使用正則表達(dá)式模式匹配替換replaceFirst，僅替換第一個(gè)匹配的字符串
}

通過jdk提供的String源碼我們可以得到以下結(jié)果：

使用contains方法進(jìn)行包含判斷，它的底層實(shí)現(xiàn)原理其實(shí)就是通過遍歷目標(biāo)字符串的字符數(shù)組進(jìn)行挨個(gè)匹配；少量敏感詞檢測(cè)的時(shí)候是可行的，但如果目標(biāo)字符串很大，并且要匹配的敏感詞足夠多的時(shí)候，它的遍歷匹配效率是很低的。
replace則分兩種實(shí)現(xiàn)，其中一種是類似contains方法，也是進(jìn)行對(duì)目標(biāo)字符串進(jìn)行字符數(shù)組的遍歷替換。
replace的另一種實(shí)現(xiàn)，是通過java的正則表達(dá)式去做匹配，正則匹配相比于遍歷匹配，效率上不會(huì)有明顯提升，但對(duì)于復(fù)雜模式的解析匹配會(huì)有比較明顯的優(yōu)勢(shì)

其他語(yǔ)言的字符串操作API大同小異，具體看源碼的實(shí)現(xiàn)方式

二、正則表達(dá)式

另外一種我們能想到的方式就是進(jìn)行正則表達(dá)式的匹配了。前面提到，在java中如果使用String的api，它有部分接口就是使用正則表達(dá)式來實(shí)現(xiàn)的。
使用正則表達(dá)式有一定優(yōu)勢(shì)，也有一定缺陷。這就不得不提正則表達(dá)式的實(shí)現(xiàn)原理：FA（Finite Automaton：有限自動(dòng)機(jī)）

DFA與NFA

FA又分為DFA和NFA，我們以正則ab|ac舉例

NFA（Nondeterministic finite automaton：非確定性有限狀態(tài)自動(dòng)機(jī)）
在NFA中表達(dá)式會(huì)構(gòu)建為以下結(jié)構(gòu)
- 非確定性：對(duì)于給定的輸入符號(hào)，NFA可以從一個(gè)狀態(tài)轉(zhuǎn)移到多個(gè)狀態(tài)。這意味著存在多種可能的狀態(tài)轉(zhuǎn)換路徑，NFA在任何時(shí)間點(diǎn)都可以處于多個(gè)狀態(tài)。
- 回溯：由于NFA在處理輸入時(shí)可以選擇多條路徑，因此可能需要回溯。當(dāng)某條路徑未能達(dá)到接受狀態(tài)時(shí)，NFA會(huì)返回并嘗試其他可能的路徑。
- 構(gòu)造：NFA相對(duì)容易構(gòu)造，特別是對(duì)于復(fù)雜的或包含多種可能的語(yǔ)言（例如正則表達(dá)式）。
- 運(yùn)行效率：由于其非確定性特性，NFA在運(yùn)行時(shí)可能需要更多的計(jì)算資源，特別是在處理長(zhǎng)輸入字符串時(shí)。
DFA（Deterministic finite automaton：確定性有限自動(dòng)機(jī)）
在DFA中表達(dá)式會(huì)構(gòu)建為以下結(jié)構(gòu)
- 確定性：對(duì)于給定的輸入符號(hào)，DFA從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)唯一確定的狀態(tài)。這意味著DFA在任何時(shí)間點(diǎn)只能處于一個(gè)狀態(tài)。
- 無(wú)回溯：由于每個(gè)輸入符號(hào)只對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換，DFA在處理輸入時(shí)不需要回溯。
- 構(gòu)造：相對(duì)于NFA，DFA可能更難直接構(gòu)造，特別是對(duì)于復(fù)雜的語(yǔ)言，但它可以通過從NFA轉(zhuǎn)換得到。
- 運(yùn)行效率：DFA在運(yùn)行時(shí)通常更高效，因?yàn)樗谔幚磔斎霑r(shí)不需要考慮多種可能的狀態(tài)路徑。

理論上，NFA和DFA等效，它們都可以識(shí)別相同的語(yǔ)言類型。但在實(shí)際應(yīng)用中，它們各有優(yōu)勢(shì)：NFA更適合于表示和構(gòu)造復(fù)雜模式，而DFA在執(zhí)行時(shí)更高效。

如果以上描述不能理解，這里其實(shí)可以做個(gè)不是特別恰當(dāng)?shù)谋扔鳎簭V度優(yōu)先搜索BFS和深度優(yōu)先搜索DFS。

NFA可以轉(zhuǎn)移到多個(gè)不同的狀態(tài)。這就像是在圖中有多條邊從一個(gè)節(jié)點(diǎn)出發(fā)一樣。如果將NFA的操作類比為一種搜索算法，它更接近于廣度優(yōu)先搜索（BFS）。在匹配過程中，NFA可以同時(shí)探索多條路徑（或狀態(tài)轉(zhuǎn)換），就像BFS在搜索時(shí)會(huì)先訪問所有鄰接節(jié)點(diǎn)。然而，NFA通常不會(huì)存儲(chǔ)所有可能的狀態(tài)轉(zhuǎn)換路徑，而是在運(yùn)行時(shí)動(dòng)態(tài)生成它們。

DFA只能轉(zhuǎn)移到一個(gè)唯一確定的狀態(tài)。這就像是圖中的每個(gè)節(jié)點(diǎn)僅有一條出邊一樣。盡管DFA在每一步只選擇一條路徑，但將其類比為深度優(yōu)先搜索（DFS）并不準(zhǔn)確。DFS是一種搜索算法，用于探索所有可能的路徑直到它達(dá)到目標(biāo)或結(jié)束條件。DFA則是一種確定性的狀態(tài)機(jī)，它不需要“搜索”；它只是在狀態(tài)之間單一確定地轉(zhuǎn)換。

在正則表達(dá)式的實(shí)現(xiàn)中，有的基于DFA，有的基于NFA；盡管DFA的搜索路徑比NFA短，但實(shí)際場(chǎng)景中，NFA更適合復(fù)雜模式的正則搜索。因此大多數(shù)正則實(shí)現(xiàn)還是基于NFA。
java中的正則表達(dá)式是基于NFA的實(shí)現(xiàn)

使用局限

當(dāng)然了，正則表達(dá)式的實(shí)現(xiàn)到底是NFA還是DFA，并不是今天討論的重點(diǎn)。

資源消耗
無(wú)論是NFA還是DFA，它們?cè)谄ヅ渲埃紩?huì)先構(gòu)造基于圖的數(shù)據(jù)結(jié)構(gòu)，因此，使用正則表達(dá)式進(jìn)行敏感詞匹配，一定逃不開構(gòu)建這個(gè)數(shù)據(jù)結(jié)構(gòu)的性能消耗和內(nèi)存占用。
回溯陷阱
在使用正則表達(dá)式進(jìn)行敏感詞匹配時(shí)，如果是基于NFA實(shí)現(xiàn)的正則算法，則很有可能出現(xiàn)回溯陷阱。上面提到NFA在匹配時(shí)是會(huì)進(jìn)行回溯的，因?yàn)樗恢篮竺嬗袥]有可能還會(huì)匹配成功，但是DFA從一開始就是確定的有限自動(dòng)機(jī)，DFA是知道所有的匹配成功的情況，所以在使用NFA時(shí)，如果表達(dá)式寫的不注意，很可能出現(xiàn)大量回溯。這樣大量的回溯很可能造成在進(jìn)行正則表達(dá)式的匹配時(shí)，CPU會(huì)飚高的情況。

解決方案

資源消耗很好解決：對(duì)于服務(wù)器來說，只需要在啟動(dòng)服務(wù)器之前，對(duì)配置好的敏感詞做好正則表達(dá)式的初始化即可，即便是需要靈活配置，也可以通過動(dòng)態(tài)加載再進(jìn)行內(nèi)存替換來解決。
要解決NFA回溯問題，也有很多方式：比如表達(dá)式中盡可能提取公共部分、適當(dāng)拆分、不要量詞嵌套、使用非貪婪模式等多種優(yōu)化手段。這些優(yōu)化手段都是從表達(dá)式本身入手，這意味著所有人在編寫敏感詞匹配的正則表達(dá)式時(shí)，都需要時(shí)刻注意回溯陷阱，并且對(duì)每一個(gè)表達(dá)式都要做好性能測(cè)試。

如果注意好以上點(diǎn)，使用正則表達(dá)式進(jìn)行敏感詞匹配在業(yè)務(wù)場(chǎng)景中也是可行的。甚至于對(duì)于復(fù)雜語(yǔ)義的敏感詞配置來說，只有正則表達(dá)式能實(shí)現(xiàn)需求

三、DFA

上文中其實(shí)已經(jīng)提到，相比于NFA的不確定性，DFA是具有確定性的有限自動(dòng)機(jī)。它之所以具有確定性，從結(jié)構(gòu)上來說，它的每一個(gè)狀態(tài)都只對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換，因此它也無(wú)需進(jìn)行回溯，因此它的匹配性能也比NFA要高。

當(dāng)然了DFA的缺點(diǎn)就是它很難處理復(fù)雜的語(yǔ)義。但是對(duì)于敏感詞來說，為了效率，我們其實(shí)可以把那些復(fù)雜的語(yǔ)義簡(jiǎn)單化；另外一個(gè)和正則匹配一樣的點(diǎn)，就是構(gòu)建DFA有向圖所帶來的開銷和內(nèi)存占用，這一點(diǎn)也能通過服務(wù)器啟動(dòng)加載和動(dòng)態(tài)內(nèi)存替換解決。
所以其實(shí)一旦我們解決掉DFA的痛點(diǎn)，便能揚(yáng)長(zhǎng)避短，既享受DFA高效率，又使其能勝任業(yè)務(wù)場(chǎng)景。

不過需要注意的是，這里我們就不再使用正則表達(dá)式進(jìn)行敏感詞匹配了，而是直接實(shí)現(xiàn)一套基于DFA的敏感詞匹配算法。你可能會(huì)有疑問，既然正則表達(dá)式也可以使用DFA，那我們?yōu)槭裁床皇褂没贒FA的正則表達(dá)式呢？
這也很好理解，使用正則表達(dá)式，我們只能把每一條表達(dá)式單獨(dú)構(gòu)建成一個(gè)個(gè)圖的數(shù)據(jù)結(jié)構(gòu)，它的粒度只能到每一條表達(dá)式。而我們自己實(shí)現(xiàn)DFA，則可以把所有的敏感詞全部構(gòu)建成同一個(gè)大的DFA圖，它維度則是全服所有敏感詞。這樣既可以省去一定的內(nèi)存空間，也可以減少匹配次數(shù)。

使用原理

使用DFA來實(shí)現(xiàn)敏感詞匹配的原理，其實(shí)是在初始化時(shí)，把所有的敏感詞拆成一個(gè)個(gè)的字，然后組織成一個(gè)很大的有向圖的結(jié)構(gòu)。其實(shí)也是用到編程思想中的空間換時(shí)間思想。比如有以下敏感詞：

打死你
打死他
打他
揍他
經(jīng)過DFA的樹組織，最終會(huì)得到以下結(jié)構(gòu)：

其中，綠色的Entry代表入口節(jié)點(diǎn)，而藍(lán)色的代表中止節(jié)點(diǎn)，當(dāng)玩家輸入一句話時(shí)，會(huì)通過遍歷玩家發(fā)的每一個(gè)字，再去這個(gè)DFA有向圖中去匹配
如果玩家發(fā)送“我要揍他”，那么“揍他”兩個(gè)字就能通過“Entry->揍->他”這樣的路徑匹配上
如果玩家發(fā)送“我要揍你”，那么“揍”字能通過“Entry->揍”這樣的路徑匹配上，但因?yàn)椤?strong>揍”不是中止節(jié)點(diǎn)，所以這句話不能算敏感詞

邏輯實(shí)現(xiàn)

1. DFA初始化

這一步作用是構(gòu)建DFA圖

	public boolean initialize(String[] keyWords) {
		clear();
		// 構(gòu)造DFA
		for (int s = 0; s < keyWords.length; s++) {
			String _keyword = keyWords[s];
			if (_keyword == null || (_keyword = _keyword.trim()).length() == 0) {
				continue;
			}
			char[] patternTextArray = _keyword.toCharArray();
			DFANode currentDFANode = dfaEntrance;
			for (int i = 0; i < patternTextArray.length; i++) {
				final char _c = patternTextArray[i];
				// 逐點(diǎn)加入DFA
				final Character _lc = toLowerCaseWithoutConfict(_c);
				DFANode _next = currentDFANode.dfaTransition.get(_lc);
				if (_next == null) {
					_next = new DFANode();
					currentDFANode.dfaTransition.put(_lc, _next);
				}
				currentDFANode = _next;
			}
			if (currentDFANode != dfaEntrance) {
				currentDFANode.isTerminal = true;
			}
		}

		buildFailNode();
		return true;
	}

2. DFA匹配檢測(cè)

匹配字檢測(cè)，一旦檢測(cè)到中止節(jié)點(diǎn)，則返回true

	public boolean contain(final String inputMsg) {
		char[] input = inputMsg.toCharArray();
		DFANode currentDFANode = dfaEntrance;
		DFANode _next = null;
		for (int i = 0; i < input.length; i++) {
			final Character _lc = this.toLowerCaseWithoutConfict(input[i]);
			if (!isIgnore(_lc)) {
				_next = currentDFANode.dfaTransition.get(_lc);
				while (_next == null && currentDFANode != dfaEntrance) {
					currentDFANode = currentDFANode.failNode;
					_next = currentDFANode.dfaTransition.get(_lc);
				}
			}
			if (_next != null) {
				// 找到狀態(tài)轉(zhuǎn)移，可繼續(xù)
				currentDFANode = _next;
			}
			// 看看當(dāng)前狀態(tài)可退出否
			if (currentDFANode.isTerminal) {
				// 可退出，記錄，可以替換到這里
				return true;
			}
		}

		return false;
	}

3. DFA字符替換

根據(jù)節(jié)點(diǎn)搜索匹配，走到中止節(jié)點(diǎn)則回溯依次替換

	public String filt(String s) {
		char[] input = s.toCharArray();
		char[] result = s.toCharArray();
		boolean _filted = false;

		DFANode currentDFANode = dfaEntrance;
		DFANode _next = null;
		int replaceFrom = 0;
		int ignoreLength = 0;
		boolean endIgnore = false;
		for (int i = 0; i < input.length; i++) {
			final Character _lc = this.toLowerCaseWithoutConfict(input[i]);
			_next = currentDFANode.dfaTransition.get(_lc);
			while (_next == null && !isIgnore(_lc) && currentDFANode != dfaEntrance) {
				currentDFANode = currentDFANode.failNode;
				_next = currentDFANode.dfaTransition.get(_lc);
			}
			if (_next != null) {
				// 找到狀態(tài)轉(zhuǎn)移，可繼續(xù)
				currentDFANode = _next;
				if(currentDFANode.level == 1) {
					ignoreLength = 0;
				}
			}
			if (!endIgnore && currentDFANode != dfaEntrance && isIgnore(_lc)) {
				ignoreLength++;
			}
			// 看看當(dāng)前狀態(tài)可退出否
			if (currentDFANode.isTerminal) {
				endIgnore = true;
				// 可退出，記錄，可以替換到這里
				int j = i - (currentDFANode.level - 1) - ignoreLength;
				if (j < replaceFrom) {
					j = replaceFrom;
				}
				replaceFrom = i + 1;
				for (; j <= i; j++) {
					result[j] = this.subChar;
					_filted = true;
				}
				currentDFANode = dfaEntrance;
				ignoreLength = 0;
				endIgnore = false;
			}
		}
		if (_filted) {
			return String.valueOf(result);
		} else {
			return s;
		}
	}

怎么選擇

使用原生api進(jìn)行遍歷匹配在數(shù)據(jù)達(dá)到一定量級(jí)時(shí)一定會(huì)有性能問題的，一般不采用這種方式。
使用正則表達(dá)式優(yōu)勢(shì)在于靈活配置，但需注意回溯陷阱問題；正則表達(dá)式預(yù)編譯會(huì)占用一定內(nèi)存空間。
使用DFA在簡(jiǎn)單確定的語(yǔ)義中優(yōu)勢(shì)明顯，但難以處理復(fù)雜語(yǔ)義；DFA初始化構(gòu)建有向圖會(huì)占用內(nèi)存空間，一般敏感詞數(shù)量是會(huì)達(dá)到二三十萬(wàn)的量級(jí)的，有向圖大小會(huì)達(dá)到M級(jí)別，好在現(xiàn)在內(nèi)存并不值錢，空間換時(shí)間是一個(gè)可取的辦法。

DFA應(yīng)用場(chǎng)景

編譯器設(shè)計(jì)：DFA常用于詞法分析器，用于識(shí)別關(guān)鍵字、運(yùn)算符、標(biāo)識(shí)符等
字符串搜索和匹配：常用于字符串匹配算法，比如文本編輯器，敏感詞等
網(wǎng)絡(luò)安全檢測(cè)：DFA用快速識(shí)別惡意流量模式
自然語(yǔ)言（NPL）處理：用于文本分析和處理任務(wù)
正則表達(dá)式引擎：雖然很多正則表達(dá)式引擎基于非確定性有限自動(dòng)機(jī)（NFA），但也有一些引擎或工具使用DFA來提高匹配效率，特別是在匹配簡(jiǎn)單模式時(shí)
更多...

更多技術(shù)干貨，歡迎關(guān)注我！

總結(jié)

以上是生活随笔為你收集整理的构建健康游戏环境：DFA算法在敏感词过滤的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：高三生如何做好两手准备？高考+国际本科两
下一篇： Freezable ---探索WPF中F