通过Trie实现违禁词过滤

敏感词过滤

生活在天朝的网站，必须要有保持和谐的工具。根据网站的规模不同选择不同的技术方案：
1.前期上一个敏感词过滤系统，发的文章只要命中敏感词就不让发。
2.后期可以通过机器学习来自动识别一篇简历是否是正常简历，一篇正常简历的特征还是很明显的，通过训练机器识别正常简历的语料，能让机器自动判断是否是违规信息。


敏感词过滤系统
比如检测用户输入的一篇文章中是否含有网安给的违禁词列表。现在正常的做法都是通过Trie 树来实现。Trie 树的基本原理基于这样一个事实：假设我从文本中查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。

以“中华人民”为例显示在Trie树中字典的存储结构：


上图中每一个节点都表示一个TrieNode，每个TrieNode有一个dict和val,root是一个打平的dict，包含违禁词中所有开头的第一个字。

比如词典在文本中保存格式是：

中华
中华书局
中华书库
中华人民
国家
国家专利
国家专利局

 那么root这个节点中dict的key包含['中','国']。

 

python的实现：

#!/usr/bin/python 
# -*- encoding: UTF-8 -*-

import codecs
import time

class TrieNode:
    
    def __init__ (self):
        self.val = 0
        self.trans = {}

class Trie (object):
    def __init__ (self):
        self.root = TrieNode()
        
    def __walk (self, trienode, ch):
        if ch in trienode.trans:
            trienode = trienode.trans[ch]
            return trienode, trienode.val
        else:
            return None, 0
    
    def add (self, word, value=1):
        curr_node = self.root
        for ch in word:
            try: 
                curr_node = curr_node.trans[ch]
            except:
                curr_node.trans[ch] = TrieNode()
                curr_node = curr_node.trans[ch]

        curr_node.val = value
     
     
    def _find_ch(self,curr_node,ch,word,start,limit):
           curr_node, val = self.__walk (curr_node, ch)
           if val:
               return val
           while curr_node is not None and start<(limit-1):
               start= start+1
               ch = word[start]
               curr_node, val = self.__walk (curr_node, ch)
               if val:
                   return val
           
    def match_all (self, word):
        ret = []
        curr_node = self.root
        index = 0
        size = len(word)
        while index<size:
            val = self._find_ch(curr_node,word[index], word, index, size)
            if val:
                ret.append(val)
            index=index+1
        return ret

class Dict (Trie):
    def __init__(self, fname):
        super (Dict, self).__init__()
        self.load(fname)

    def load(self, fname):
        file = codecs.open(fname, 'r', 'utf-8')
        for line in file:
            word = line.strip()
            self.add(word, word)
        file.close()
            
if __name__ == "__main__":
        dic = Dict("/home/yunpeng/test3/data/words-forbidden-1_.dic")

        for x in range(100):
            starttime = time.time()
            test_str = u"大庆让胡路喇嘛甸哪里有找小姐服务１８６－５５５５－２５５７娜娜【ＱＱ１９６８４５４６８８空间选小姐】哪里有小姐服务１８６－５５５５－２５５７【ＱＱ１９６８４５４６８８空间选小姐】哪里有小姐服务１８６－５５５５－２５５７娜娜【ＱＱ１９６８４５４６８８空间看照片】无论朋友你常住本市。。 哪里找小姐服务娜娜【１８６－５５５５－２５５７娜娜】还是阁下才来我市。这些都不重要。。哪里找小姐服务１８６－５５５５－２５５７娜娜因为找我们在寂寞的深夜你不在感到孤单和寂寞。。"
            ret = dic.match_all(test_str)
            endtime = time.time()
            exe_time = (endtime - starttime)*1000
            print  "find forbidden %s  cost:%s" %(" ".join(ret),exe_time)