最近看代码，发现了一个敏感词检测是用前缀树写的，看起来速度蛮快，毕竟是拿空间换时间，LOG倍速。但是缺点也很明显，待检测文本需要与敏感词词库中的值完全匹配。所以对于简短的词法比较合适。
原理：
每一个节点可以有多个子节点
节点“存储”字符， 节点与节点之间的连线自动形成单词。 如a节点与d节点，之间的连线就是单词 ad
节点可能是叶子节点，此时也是一个单词的“终点”，否则是其他拥有相同前缀的节点的“过客”， wordcount要加一。
删除一个单词，则对应节点上的“过客”都要减一，直至减至叶子节点。
# coding: utf8
MAX_TREE_WIDTH = 26
INIT_CHAR = 'a'
forbiddenwords = """
fuck
fucker
damn
silly
"""
class TrieNode(object):
def __init__(self):
self.nodes = [None] * MAX_TREE_WIDTH
self.wordcount = 0
self.isend = 0
class TrieTree(object):
def __init__(self):
self.root = TrieNode()
def add(self, word):
word = word.lower()
curnode = self.root
for char in word:
index = ord(char) - ord(INIT_CHAR)
if curnode.nodes[index] is None:
curnode.nodes[index] = TrieNode()
curnode = curnode.nodes[index]
curnode.wordcount += 1
curnode.isend = 1
def search(self, word):
word = word.lower()
curnode = self.root
for char in word:
index = ord(char) - ord(INIT_CHAR)
if curnode.nodes[index] is None:
return -1
curnode = curnode.nodes[index]
return curnode.wordcount
def countstartswith(self, prefix):
curnode = self.root
for char in prefix:
index = ord(char) - ord(INIT_CHAR)
if curnode.nodes[index] is None:
return -1
curnode = curnode.nodes[index]
return curnode.wordcount
def delete(self, word):
if self.countstartswith(word) > 0:
curnode = self.root
for char in word:
index = ord(char) - ord(INIT_CHAR)
curnode.nodes[index].wordcount -= 1
if curnode.nodes[index].wordcount == 0:
curnode.nodes[index] = None
return
curnode = curnode.nodes[index]
curnode.isend = 0
if __name__ == "__main__":
print("hello trie tree.")
tree = TrieTree()
tree.add("h")
tree.add("He")
tree.add("hEl")
tree.add("helL")
tree.add("hello")
print(tree.search('he'))
print(tree.countstartswith("h"))
print(tree.countstartswith("hel"))
tree.delete("hel")
print(tree.countstartswith("hel"))
print(tree.countstartswith("guo"))
words = [item for item in forbiddenwords.strip("").split("\n") if item != '']
for word in words:
print("adding word: {}".format(word))
tree.add(word)
# test sequence
teststr = "you a silly mother fucker"
tests = teststr.split(" ")
for test in tests:
print("{} --> {}".format(test, tree.search(test)))
运行结果：
hello trie tree.
4
5
3
2
-1
adding word: fuck
adding word: fucker
adding word: damn
adding word: silly
you --> -1
a --> -1
silly --> 1
mother --> -1
fucker --> 1
相较于之前 基于朴素贝叶斯分类算法 的golang 与PHP结合的例子，效率，准确性，适用性都很逊。这也跟场景息息相关，选对了场景，前缀树会给出一个令人满意的答复的。