ActionScript 3敏感词过滤算法

最简单的敏感词查找办法应是

for each(var i in 敏感词列表){
        if(原字符串.indexOf(i)!=-)return true;
}//end for
return false;
           

也包括使用正则的简单查找办法

我们需要了解的是，即使正则和indexOf是flash自带方法、效率较高，它们仍然需要逐字查询字符串

对单个敏感词，时间代价是O(n);//n是原字符串长度

而敏感词有m个时，时间代价变成O(m*n);

下面办法通过预计算将敏感词做成树型结构，方便查询。能将运行时时间代价降低到O(n)左右，藉此提高发现敏感词的速度。

下面第一个类是用来测试结果的，使用时可以根据具体要求进行变化：

package
{
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.net.URLLoader;
    import flash.net.URLRequest;
    import flash.utils.Dictionary;

    public class SensitiveWordFilter extends Sprite
    {
        private var loader:URLLoader = new URLLoader();

        private var wordsVec:Vector.<String> = new Vector.<String>;
        private var testFilter:WordFilter = new WordFilter;
        public function SensitiveWordFilter()
        {
            loader.addEventListener(Event.COMPLETE,OnComplete);
            loader.load(new URLRequest("load_config_complete.txt"));
        }
        private function OnComplete(e:Event):void
        {
            var txt:String = loader.data;
            var arr:Array = txt.split("\r\n");

            arr.sort(onSort);
            for each (var str:String in arr) 
            {
                wordsVec.push(str);
            }
            //trace(wordsVec);
            testFilter.regSensitiveWords(wordsVec);
            var strTest:String = "总理是朱八重，朱鎔基shi总理。曾经朱鎔基是总理，曾经有个恐怖组织叫做东突厥斯坦恐怖组织";
            trace(testFilter.findSensitiveWordsIn(strTest));
        }
        private function onSort(a:String, b:String):int
        {
            if(a.length > b.length)
            {
                return ;
            } else {
                return -;
            }
        }
    }
}
           

下面这个类主要是建立敏感词库的存储数结构：

// ActionScript file
package
{
    public class TreeNode
    {
        private var data:Object;
        public var isLeaf:Boolean;
        public var parent:TreeNode;
        public var value:String;
        public function TreeNode(){
            data={};
            isLeaf=true;
        }//end of Function
        public function getChild(name:String):TreeNode{
            return data[name];
        }//end of Function
        public function setChild(key:String):TreeNode{
            var node:TreeNode = new TreeNode;
            data[key]=node;
            node.value=key;
            node.parent=this;
            return node;
        }//end of Function
        public function getFullWord():String{
            var rt:String = this.value;
            var node:TreeNode = this.parent;
            while(node){
                rt=node.value+rt;
                node=node.parent;
            }//end while
            return rt;
        }//end of Function
    }//end of class
}
           

建立好树结构以后就可以从文本中读取数据，然后将数据存储成树结构即可：

package
{
    import flash.events.Event;
    import flash.net.URLLoader;
    import flash.net.URLRequest;
    import flash.utils.Dictionary;
    public class WordFilter 
    {
        private var treeRoot:TreeNode;

        public function regSensitiveWords(words:Vector.<String>):void{
            //这是一个预处理步骤，生成敏感词索引树，功耗大于查找时使用的方法，但只在程序开始时调用一次。
            treeRoot=new TreeNode();
            treeRoot.value="";
            var words_len:int = words.length;
            for(var i:int = ;i<words_len;i++){
                var word:String = words[i];
                var len:int = word.length;
                var currentBranch:TreeNode = treeRoot;
                for(var c:int = ;c<len;c++){
                    currentBranch.isLeaf=false;
                    var char:String = word.charAt(c);
                    var tmp:TreeNode = currentBranch.getChild(char);
                    if(tmp){
                        if(tmp.isLeaf){
                            throw new Error("长词在短词后被注册。已经有以("+tmp.getFullWord()+")开头的敏感词存在,当前正在注册第"+i+"个词("+word+")");
                        }//end if
                        currentBranch=tmp;
                    }else {
                        currentBranch=currentBranch.setChild(char);
                    }//end if
                }//end for
                if(!currentBranch.isLeaf){
                    throw new Error("短词在长词后被注册。已经有以("+word+")开头的敏感词存在,当前正在注册第"+i+"个词");
                }//end if
                //trace(currentBranch.value);
            }//end for
        }//end of Function
        public function findSensitiveWordsIn(og:String):String{
            var ptrs:Array = new Array//嫌疑列表，但凡前几个字匹配成功的节点都放在这里
            var len:int = og.length;
            var tmp:TreeNode;
            for(var c:int = ;c < len; c++){
                var char:String = og.charAt(c);
                //如果嫌疑列表内有数据，先对其进行检验，检查char是否是嫌疑列表中某节点的下一个字
                var p:int = ptrs.length;
                while(p--){
                    var node:TreeNode = ptrs.shift();
                    tmp=node.getChild(char);
                    if(tmp){
                        if(tmp.isLeaf){
                            var tmpLength:int = tmp.getFullWord().length;
                            trace(tmp.getFullWord());
                            var tmpStr:String;
                            for(var i:int = ; i < tmpLength; ++i)
                            {
                                tmpStr += "*";
                            }
                            tmpStr = tmpStr.substr(tmpStr.length - tmpLength, tmpStr.length - );
                            og = og.replace(tmp.getFullWord(), tmpStr);
                            //return tmp.getFullWord()+" @["+c+"]" + "######" + og;
                        }//end if
                        //从node开始，敏感词的下一个字也被匹配到，并且已经完整地匹配了一个敏感词，可以返回
                        ptrs.push(tmp);
                        //trace(og.replace( , "*"));
                        //从node开始，下一个字也匹配到了，但还没有完整地匹配一个敏感词，那么将下一个字的节点压入嫌疑列表
                    }//end if
                }//end while
                //之后从treeRoot开始查找。因treeRoot的子项是所有敏感词的第一个字，这里在尝试匹配是否有与char相同的敏感词第一字
                tmp=treeRoot.getChild(char);
                if(tmp){
                    //var tempLength:int = tmp.getFullWord().length;
                    //var tempStr:String = null;
                    //for(var j:int; j < tempLength; ++j)
                    //{
                    //tempStr += "*";
                    //}
                    //trace(tempStr);
                    //og = og.replace(tmp.getFullWord(), tempStr);
                    if(tmp.isLeaf){
                        return char+" @["+c+"]" + "######" + og;
                    }//end if
                    //如果是一个字的敏感词，直接返回
                    ptrs.push(tmp);
                    //如果匹配上了非单字敏感词的第一个字，那么将其加入嫌疑列表
                }//end if
            }//end for
            return og;
        }//end of Function
    }//end of class
}//end of file
           

大致算法如此，以后有时间再来优化。