我们在玩游戏的时候，聊天窗口经常会看到有“我**谁”等文字，其中的“**”可能是一个骂人的词语或者是政治敏感词汇，游戏审核部门会要求游戏必须屏蔽敏感词汇，否则不允许上线，所以骂人的词语或句子就被替换成*号了。
游戏项目中是如何处理这样的敏感字匹配的呢？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。