我们在玩游戏的时候，聊天窗口经常会看到有“我**谁”等文字，其中的“**”可能是一个骂人的词语或者是政治敏感词汇，游戏审核部门会要求游戏必须屏蔽敏感词汇，否则不允许上线，所以骂人的词语或句子就被替换成*号了。

游戏项目中是如何处理这样的敏感字匹配的呢？KMP？还是Boyer-Moore算法？其实都不是，基本上这类匹配用的都是字典树的方式， 字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种，它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

它有3个基本性质：
1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

因为现在大多数项目都是使用Lua版本进行热更新，逻辑都写在lua上，所以使用Lua实现字典树是很有必要的。

核心代码如下：

local WordTree ={}

--树节点创建
function WordTree.CreateNode(self, char, flag, childs)
	local node = {}
	node.char = char or nil		--字符
	node.flag = flag or 0		--是否结束标志，0：继续，1：结尾
	node.childs = childs or {}	--保存子节点
	node.isleaf = true --childs数量为0则是叶子节点
	return node
end

//创建根结点
WordTree.m_RootNode = WordTree.CreateNode('root') 

//更新字典树
function WordTree.UpdateNodes(self, words)
	for i, v in pairs(words) do
		local chars = self:GetCharList(string.lower(v))
		if #chars > 0 then
			self:InsertNode(self.m_RootNode, chars, 1)
		end
	end
end

--插入节点
function WordTree.InsertNode(self, parent, chars, index)
	local node = self:FindNode(parent, chars[index])
	if node == nil then
		node = self:CreateNode(chars[index])
		parent.isleaf = false
		table.insert(parent.childs, node)
	end
	local len = #chars
	if index == len then
		node.flag = 1
	else
		index = index + 1
		if index <= len then
			self:InsertNode(node, chars, index)
		end
	end
end

--节点中查找子节点
function WordTree.FindNode(self, node, char)
	local childs = node.childs
	for i, child in ipairs(childs) do
		if child.char == string.lower(char) then 
			return child
		end
	end

end

function WordTree.GetCharList(self, str)
	local list = {}
	while str do
		local utf8 = string.byte(str,1)
		if utf8 == nil then
			break
		end
		--utf8字符1byte,中文3byte
		if utf8 > 127 then
			local tmp = string.sub(str,1,3)
			table.insert(list,tmp)
			str = string.sub(str,4)
		else
			local tmp = string.sub(str,1,1)
			table.insert(list,tmp)
			str = string.sub(str,2)
		end
	end
	return list
end

--将字符串中敏感字用*替换返回
-- flag == true，替换的 * 的数量 = 敏感词长度；flag == false，默认使用 *** 替换
function WordTree.ReplaceMaskWord(self, str, flag)
	local chars = self:GetCharList(str)
	local index = 1
	local node = self.m_RootNode
	local prenode = nil
	local matchs = {}
	local isReplace = false
	local lastMatchLen = nil
	local totalLen = #chars
	local function replace(chars, list, last, flag)
        local stars = ""
		for i=1, last do
			local v = list[i]
			if flag then
				chars[v] = "*"
				isReplace = true
			else
				if isReplace then
					chars[v] = ""
				else
					chars[v] = "***"
					isReplace = true
				end
			end
		end
	end
	while totalLen >= index do
		prenode = node
		node = self:FindNode(node, chars[index])
		if chars[index] == " " then
			if #matchs then
				table.insert(matchs, index)
				node = prenode
			else
				node = self.m_RootNode
			end
		elseif node == nil then
			index = index - #matchs
			if lastMatchLen then
				replace(chars, matchs, lastMatchLen, flag)
				index = index + (lastMatchLen - 1)
				lastMatchLen = nil
			else
				isReplace = false
			end
			node = self.m_RootNode
			matchs = {}
		elseif node.flag == 1 then
			table.insert(matchs, index)
			if node.isleaf or totalLen == index then
				replace(chars, matchs, #matchs, flag)
				lastMatchLen = nil
				matchs = {}
				node = self.m_RootNode
			else
				lastMatchLen = #matchs
			end
		else
			table.insert(matchs, index)
		end
		index = index + 1
	end
	local str = ''
	for i, v in ipairs(chars) do
		str = str..v
	end
	return str
end

--字符串中是否含有敏感字
function WordTree.IsContainMaskWord(self, str)
	local sCheck = string.gsub(str, " ", "")
	local chars = self:GetCharList(sCheck)
	local index = 1
	local node = self.m_RootNode
	local masks = {}
	while #chars >= index do
		node = self:FindNode(node, chars[index])
		if node == nil then
			index = index - #masks 
			node = self.m_RootNode
			masks = {}
		elseif node.flag == 1 then
			return true
		else
			table.insert(masks,index)
		end
		index = index + 1
	end
	return false
end


return WordTree

假如有一组屏蔽字为：

local data={“二货”,  “傻B”,   “二B”}

首先根据屏蔽字表创建字典树：WordTree.UpdateNodes(data);

然后就可以判断是否存在敏感字,如WordTree .IsContainMaskWord(“你是 二货 “)返回true。