精华内容
下载资源
问答
  • DFA敏感词过滤算法

    万次阅读 2017-09-04 14:12:58
    运用DFA算法加密。 首先我先对敏感词库初始化,若我的敏感词库为 冰毒 白粉 大麻 大坏蛋 初始化之后得到的是下面这样。: {冰={毒={isEnd=1}, isEnd=0}, 白={粉={isEnd=1}, isEnd=0}, 大={麻={isEnd=1}, isEnd=0, 坏...

    目录

    一、准备工作

    二、初始化数据

    三、解析数据

    四、测试


    一、准备工作

    首先我要把DB里的敏感词初始化,DB中的数据是这样子的

    CREATE TABLE `sensitive_word` (
      `word_id` varchar(16) NOT NULL,
      `word_content` varchar(64) DEFAULT NULL,
      PRIMARY KEY (`word_id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='敏感词表';
    
    INSERT INTO `maple`.`sensitive_word`(`word_id`, `word_content`) VALUES ('1', '冰毒');
    INSERT INTO `maple`.`sensitive_word`(`word_id`, `word_content`) VALUES ('2', '白粉');
    INSERT INTO `maple`.`sensitive_word`(`word_id`, `word_content`) VALUES ('3', '大麻');
    INSERT INTO `maple`.`sensitive_word`(`word_id`, `word_content`) VALUES ('4', '大坏蛋');
    

    二、初始化数据

    通过实现InitializingBean接口,在项目启动的时候,拿到敏感词做处理,处理之后会保存到一个Map中,格式是这样子的:

    {冰={毒={isEnd=1}, isEnd=0}, 白={粉={isEnd=1}, isEnd=0}, 大={麻={isEnd=1}, isEnd=0, 坏={蛋={isEnd=1}, isEnd=0}}}

    三、解析数据

    当一段文本去做敏感词检测时,需要解析上面这个Map,具体代码如下:

    package com.gane.maple.sensitiveword;
    
    import com.gane.maple.entity.SensitiveWord;
    import com.gane.maple.service.SensitiveWordService;
    import org.springframework.beans.factory.InitializingBean;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.context.annotation.Configuration;
    
    import java.util.*;
    
    /**
     * @author ODC-WHB
     * @date 2021/3/8
     */
    @Configuration
    public class SensitiveWordFilter implements InitializingBean {
    
        @Autowired
        private SensitiveWordService sensitiveWordService;
    
        // {冰={毒={isEnd=1}, isEnd=0}, 白={粉={isEnd=1}, isEnd=0}, 大={麻={isEnd=1}, isEnd=0, 坏={蛋={isEnd=1}, isEnd=0}}}
        private static Map<Object, Object> sensitiveWordMap;
    
        public static int minMatchType = 1; //最小匹配规则
        public static int maxMatchType = 2; //最大匹配规则
    
        /**
         * 是否包含敏感词
         *
         * @param txt
         * @return
         */
        public boolean isSensitive(String txt) {
            return isSensitive(txt, minMatchType);
        }
    
        /**
         * 是否包含敏感词
         *
         * @param txt
         * @param matchType
         * @return
         */
        public boolean isSensitive(String txt, int matchType) {
            boolean flag = false;
            for (int i = 0; i < txt.length(); i++) {
                int matchFlag = this.checkSensitiveWord(txt, i, matchType);
                if (matchFlag > 0) {
                    flag = true;
                }
            }
            return flag;
        }
    
        /**
         * 获取文本中的敏感词
         *
         * @param txt
         * @return
         */
        public Set<String> getSensitiveWord(String txt) {
            return getSensitiveWord(txt, maxMatchType);
        }
    
        /**
         * 获取文本中的敏感词
         *
         * @param txt
         * @param matchType
         * @return
         */
        public Set<String> getSensitiveWord(String txt, int matchType) {
            Set<String> sensitiveWordList = new HashSet<>();
            for (int i = 0; i < txt.length(); i++) {
                int length = checkSensitiveWord(txt, i, matchType);
                if (length > 0) {
                    sensitiveWordList.add(txt.substring(i, i + length));
                    i = i + length - 1; //减1的原因,是因为for会自增
                }
            }
            return sensitiveWordList;
        }
    
        /**
         * 替换文本中的敏感词
         *
         * @param txt
         * @param replaceChar
         * @return
         */
        public String replaceSensitiveWord(String txt, String replaceChar) {
            return replaceSensitiveWord(txt, maxMatchType, replaceChar);
        }
    
        /**
         * 替换文本中的敏感词
         *
         * @param txt
         * @param matchType
         * @param replaceChar
         * @return
         */
        public String replaceSensitiveWord(String txt, int matchType, String replaceChar) {
            String resultTxt = txt;
            Set<String> set = this.getSensitiveWord(txt, matchType);
            Iterator<String> iterator = set.iterator();
            String word = null;
            String replaceString = null;
            while (iterator.hasNext()) {
                word = iterator.next();
                replaceString = getReplaceChars(replaceChar, word.length());
                resultTxt = resultTxt.replaceAll(word, replaceString);
            }
            return resultTxt;
        }
    
        private String getReplaceChars(String replaceChar, int length) {
            String resultReplace = replaceChar;
            for (int i = 1; i < length; i++) {
                resultReplace += replaceChar;
            }
            return resultReplace;
        }
    
        private int checkSensitiveWord(String txt, int beginIndex, int matchType) {
            Map nowMap = sensitiveWordMap;
            boolean flag = false;
            char word = 0;
            int matchFlag = 0;
            for (int i = beginIndex; i < txt.length(); i++) {
                word = txt.charAt(i);
                nowMap = (Map) nowMap.get(word); //获取指定key
                if (nowMap == null) {
                    break;
                }
                matchFlag++;
                if (isEnd(nowMap)) {
                    flag = true;
                    if (SensitiveWordFilter.minMatchType == matchType) {
                        break;
                    }
                }
            }
            if (matchFlag < 2 || !flag) {
                matchFlag = 0;
            }
            return matchFlag;
        }
    
        /**
         * 是否为最后一个
         *
         * @param nowMap
         * @return
         */
        private boolean isEnd(Map nowMap) {
            boolean flag = false;
            if ("1".equals(nowMap.get("isEnd"))) {
                flag = true;
            }
            return flag;
        }
    
        @Override
        public void afterPropertiesSet() throws Exception {
            initSensitiveWord();
        }
    
        /**
         * 初始化敏感词
         */
        private void initSensitiveWord() {
    
            List<SensitiveWord> list = sensitiveWordService.list();
    
            Set<String> sensitiveWordSet = new HashSet<>();
    
            list.stream().forEach(l -> {
                sensitiveWordSet.add(l.getWordContent());
            });
    
            Iterator<String> iterator = sensitiveWordSet.iterator();
    
            String key;
            Map nowMap;
            Map<String, String> newWorMap;
            sensitiveWordMap = new HashMap(sensitiveWordSet.size());
    
            while (iterator.hasNext()) {
                key = iterator.next(); // 冰毒
                nowMap = sensitiveWordMap;
                for (int i = 0; i < key.length(); i++) {
    
                    char charKey = key.charAt(i); // 冰
                    Object wordMap = nowMap.get(charKey);
                    if (wordMap != null) {
                        nowMap = (Map) wordMap; //一个一个放进Map中
                    } else { //不存在,则构建一个Map,同时将isEnd设置为0,因为它不是最后一个
                        newWorMap = new HashMap<>();
                        newWorMap.put("isEnd", "0");//不是最后一个
                        nowMap.put(charKey, newWorMap);//没有这个key,就把(isEnd,0) 放在Map中
                        nowMap = newWorMap;
                    }
                    if (i == key.length() - 1) { //最后一个
                        nowMap.put("isEnd", "1");
                    }
                }
                System.out.println(sensitiveWordMap);
            }
        }
    }

    四、测试

    TestController

    package com.gane.maple.controller;
    
    import com.gane.maple.sensitiveword.SensitiveWordFilter;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.web.bind.annotation.GetMapping;
    import org.springframework.web.bind.annotation.RestController;
    
    import java.util.Set;
    
    /**
     * @author ODC-WHB
     * @date 2021/3/8
     */
    @RestController
    public class TestController {
    
        @Autowired
        private SensitiveWordFilter sensitiveWordFilter;
    
        @GetMapping("/test")
        public Set<String> test(String text) {
    
            System.out.println("原文为:" + text);
    
            boolean sensitive = sensitiveWordFilter.isSensitive(text);
            System.out.println(sensitive ? "原文中有敏感词" : "原文中没有敏感词");
    
            Set<String> sensitiveWord = sensitiveWordFilter.getSensitiveWord(text);
            System.out.println("敏感词有:");
            sensitiveWord.forEach(System.out::println);
    
            String replaceSensitiveWord = sensitiveWordFilter.replaceSensitiveWord(text, "*");
            System.out.println("把敏感词替换成*为:" + replaceSensitiveWord);
    
            return sensitiveWord;
        }
    }
    

    启动项目,访问 localhost:8080/test?text=张三是个大坏蛋,他竟然吸食白粉和冰毒

     

    展开全文
  • 敏感词过滤DFA算法

    2021-03-10 09:28:17
    敏感词过滤DFA算法用处DFA 算法原理算法实现demo 用处 政府相关网站项目的新闻一般会有一些敏感词不能出现, 这个时候就需要做一个AOP进行拦截,对所有提交的新闻字段进行过滤 常见的过滤方法 直接将敏感词组织成 ...

    用处

    政府相关网站项目的新闻一般会有一些敏感词不能出现, 这个时候就需要做一个AOP进行拦截,对所有提交的新闻字段进行过滤

    常见的过滤方法

    1. 直接将敏感词组织成 String 后, 利用 indexOf 方法来查询
    2. 传统的敏感词入库后SQL查询
    3. 利用 Lucene 建立分词索引查询
    4. 利用 DFA 算法

    在敏感词和扫描字段不多的情况下, 1 和 2 可以满足需求, 在高性能下不足以满足需求, 效率太低
    3 方法分词后可能会有的敏感词语不会变为敏感词, 方法复杂, 效率也低
    目前大多数过滤系统采用的都是 DFA 算法

    DFA 算法原理

    DFA 即 Deterministic Finite Automaton 也就是确定有穷自动机, 他是通过 event 和当前的 state 得到下一个 state, 即 event + state = nextState. 下图展示了其状态的转换

    在这里插入图片描述
    <图片来源见水印>

    构建规则原理

    以 日本人, 日本鬼子 为例

    1. 在 hashMap 中查询 “日” 看其是否在 hashMap 中, 如果不存在, 则证明以 “日” 开头的敏感词还不存在, 则我们直接构建这样的一颗树. 跳至 3.
    2. 如果hashMap中查找到了, 表明存在以"日"开头的敏感词, 设置hashMap = hashMap.get(“日”), 跳至 1, 依次匹配 “本”, “人”
    3. 判断该字是否为该词中的最后一个字, 若是敏感词结束,则设置标志位 isEnd = 1, 否则设置标志位 isEnd = 0.

    在这里插入图片描述
    <图片来源见水印>

    最终敏感词形成的 hashMap 树结构为
    {日=
    {本=
    {人={isEnd=1},
    鬼=
    {子={isEnd=1},
    isEnd=0},
    isEnd=0},
    isEnd=0},

      大=
     	{汉=
      		{民={isEnd=0,
      			族={isEnd=1}
      			},
      		isEnd=0},
      	isEnd=0,
      	中={isEnd=0,
      		华={isEnd=1,
      			帝={isEnd=0,
      				国={isEnd=1}}}}}}
    

    初始化中可以结合正则排除字典中的特殊字符

    检索扫描原理

    假如我们匹配 “中国人民万岁”

    1. 第一个字"中", 我们在hashMap中可以找到, 得到一个新的map= hashMap.get(“中”)
    2. 如果 map == null, 则表示不是敏感词, 否则跳至 3
    3. 获取map中的isEnd, 通过isEnd == 1 来判定该词是否为最后一个, 如果 isEnd == 1 则表示该词为敏感词, 否则跳至 1

    通过这个步骤我们可以判定 “中国人民” 为敏感词, 但是如果我们输入"中国女人" 则不是敏感词了

    扫描过程也需要结合正则排除跳过特殊字符

    算法实现demo

    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Set;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;
    
    /**
     * @Author Yzx
     * @Date 2020/4/23 0023 15:34
     * @Version 1.0
     */
    public class DFAUtil {
    
        HashMap<String, Object> dfaMap;
    
        public static final int minMatchType = 1;
    
        public static final int maxMatchType = 2;
        /**
         * 忽略特殊字符的正则表达式
         */
        private final String IGNORE_SPECIAL_CHAR_REGEX = "[`~!@#$%^&*()+=|{}':;',\\\\[\\\\].<>/?~!@#¥%……&*()——+|{}【】‘;:”“’。,、?]|\\s*";
    
        /**
         * 忽略特殊字符的正则表达式MATCHER
         */
        private final Matcher IGNORE_MATCHER = Pattern.compile(IGNORE_SPECIAL_CHAR_REGEX).matcher("");
    
        /*{日=
         *     {本=
         *        {人={isEnd=1},
         *        鬼=
         *           {子={isEnd=1},
         *           isEnd=0},
         *        isEnd=0},
         *     isEnd=0},
         *
         * 大=
         *     {汉=
         *        {民={isEnd=0,
         *           族={isEnd=1}},
         *        isEnd=0},
         *     isEnd=0,
         *     中={isEnd=0,
         *        华={isEnd=1,
         *           帝={isEnd=0,
         *              国={isEnd=1}}}}}}*/
    
        /**
         * set作为敏感词,创建出对应的dfa的Map,以供检验敏感词
         *
         * @param set
         */
        public void createDFAHashMap(Set<String> set) {
            HashMap<String, Object> nowMap;
            //根据set的大小,创建map的大小
            dfaMap = new HashMap<>(set.size());
            //对set里的字符串进行循环
            for (String key : set) {
                //对每个字符串最初,nowMap就是dfaMap
                nowMap = dfaMap;
                for (int i = 0; i < key.length(); i++) {
                    if (isIgnore(key.charAt(i))){
                        continue;
                    }
                    //一个个字符循环
                    String nowChar = String.valueOf(key.charAt(i));
                    //根据nowChar得到nowMap里面对应的value
                    HashMap<String, Object> map = (HashMap<String, Object>) nowMap.get(nowChar);
                    //如果map为空,则说明nowMap里面没有以nowChar开头的东西,则创建一个新的hashmap,
                    //以nowChar为key,新的map为value,放入nowMap
                    if (map == null) {
                        map = new HashMap<String, Object>();
                        nowMap.put(nowChar, map);
                    }
                    //nowMap=map,就是nowChar对应的对象
                    nowMap = map;
                    //最后在nowMap里设置isEnd
                    //如果nowMap里面已经有isEnd,并且为1,说明以前已经有关键字了,就不再设置isEnd
                    //因为如果没有这一步,大中华和大中华帝国,先设置大中华
                    //在大中华帝国设置的时候,华对应的map有isEnd=1,如果这时对它覆盖,就会isEnd=0,导致大中华这个关键字失效
                    if (nowMap.containsKey("isEnd") && nowMap.get("isEnd").equals("1")) {
                        continue;
                    }
                    if (i != key.length() - 1) {
                        nowMap.put("isEnd", "0");
                    } else {
                        nowMap.put("isEnd", "1");
                    }
                }
            }
            System.out.println(dfaMap);
        }
    
    
        /**
         * 用创建的dfaMap,根据matchType检验字符串string是否包含敏感词,返回包含所有对于敏感词的set
         *
         * @param string    要检查是否有敏感词在内的字符串
         * @param matchType 检查类型,如大中华帝国牛逼对应大中华和大中华帝国两个关键字,1为最小检查,会检查出大中华,2位最大,会检查出大中华帝国
         * @return
         */
        public Set<String> getSensitiveWordByDFAMap(String string, int matchType) {
            Set<String> set = new HashSet<>();
            for (int i = 0; i < string.length(); i++) {
                //matchType是针对同一个begin的后面,在同一个begin匹配最长的还是最短的敏感词
                int length = getSensitiveLengthByDFAMap(string, i, matchType);
                if (length > 0) {
                    set.add(string.substring(i, i + length));
                    //这个对应的是一个敏感词内部的关键字(不包括首部),如果加上,大中华帝国,对应大中华和中华两个敏感词,只会对应大中华而不是两个
                    //i=i+length-1;//减1的原因,是因为for会自增
                }
            }
            return set;
        }
    
        /**
         * 如果存在,则返回敏感词字符的长度,不存在返回0
         *
         * @param string
         * @param beginIndex
         * @param matchType  1:最小匹配规则,2:最大匹配规则
         * @return
         */
        public int getSensitiveLengthByDFAMap(String string, int beginIndex, int matchType) {
            //当前匹配的长度
            int nowLength = 0;
            //最终匹配敏感词的长度,因为匹配规则2,如果大中华帝,对应大中华,大中华帝国,在华的时候,nowLength=3,因为是最后一个字,将nowLenth赋给resultLength
            //然后在帝的时候,now=4,result=3,然后不匹配,resultLength就是上一次最大匹配的敏感词的长度
            int resultLength = 0;
            HashMap<String, Object> nowMap = dfaMap;
            for (int i = beginIndex; i < string.length(); i++) {
                if (isIgnore(string.charAt(i))){
                    nowLength++;
                    continue;
                }
                String nowChar = String.valueOf(string.charAt(i));
                //根据nowChar得到对应的map,并赋值给nowMap
                nowMap = (HashMap<String, Object>) nowMap.get(nowChar);
                //nowMap里面没有这个char,说明不匹配,直接返回
                if (nowMap == null) {
                    break;
                } else {
                    nowLength++;
                    //如果现在是最后一个,更新resultLength
                    if ("1".equals(nowMap.get("isEnd"))) {
                        resultLength = nowLength;
                        //如果匹配模式是最小,直接匹配到,退出
                        //匹配模式是最大,则继续匹配,resultLength保留上一次匹配到的length
                        if (matchType == minMatchType) {
                            break;
                        }
                    }
                }
            }
            return resultLength;
        }
    
        /**
         * 判断是否是要忽略的字符(忽略所有特殊字符以及空格)
         *
         * @param specificChar 指定字符
         * @return 特殊字符或空格true否则false
         */
        private boolean isIgnore(char specificChar) {
            return IGNORE_MATCHER.reset(String.valueOf(specificChar)).matches();
        }
    
        public static void main(String[] args) {
            Set set = new HashSet();
            set.add("傻逼");
            set.add("操你妈");
            set.add("垃圾");
            set.add("憨逼");
            set.add("傻屌");
            set.add("吃屎");
            set.add("三.级片");
            set.add("傻屌说");
            set.add("傻叼");
            DFAUtil dfaUtil = new DFAUtil();
            dfaUtil.createDFAHashMap(set);
            String str = "私房钱无法猜你妹操你妈我放弃我过去傻屌说废弃物垃圾太多的伤感情怀也许只局限于饲养基地 荧幕中的情节,主人公尝试着去用某种方式渐渐的很潇洒地释自杀指南怀那些自己经历的伤感。\"\n" +
                    "                        + \"然后法.轮.功 我们的扮演的角色就是跟随着主人公的喜红客联盟 怒哀乐而过于牵强的把自己的情感也附加于银幕情节中,然后感动就流泪,\"\n" +
                    "                        + \"难过就躺在某一个人的怀傻叼尽情的阐述心扉或者手机卡复制器一个人一杯红酒一部电影在夜三.级.片 深人静的晚上,关上电话静静的发呆着。";
            long beginTime = System.currentTimeMillis();
            Set<String> dfaMap = dfaUtil.getSensitiveWordByDFAMap(str, 1);
            long endTime = System.currentTimeMillis();
            System.out.println(dfaMap.toString());
            System.out.println("总共消耗时间为:" + (endTime - beginTime));
        }
    
    }
    
    

    耗时毫秒

    在这里插入图片描述

    展开全文
  • 基于DFA的低俗广告过滤算法:识别低俗广告,传销类信息,多个连续地名的数据
  • 敏感词过滤算法DFA

    2021-01-19 19:00:10
    4 DFA算法,确定有穷自动机。本项目采用这种方案 DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中...

    DFA

    敏感词过滤方案

    1 使用数据库模糊查询,效率太低

    2 使用String.indexOf("")查找,数据库量大的话也是比较慢

    3 把敏感词和内容使用全文检索(solr,ElasticSearche)技术进行分词再匹配,也是可以的,但是这种方案比较麻烦。

    4 DFA算法,确定有穷自动机。本项目采用这种方案

    DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的有限自动机,DFA中不会有从同一状态出发的两条边标志有相同的符号。

    • 一次性的把所有的敏感词存储到了多个map中,就是下图表示这种结构

    敏感词:冰毒、大麻、大坏蛋

    在这里插入图片描述

    • 检索的过程,就是hashMap的get实现

    1、第一个字“冰”,我们在hashMap中可以找到。得到一个新的map = hashMap.get("")。

    2、如果map == null,则不是敏感词。否则跳至3

    3、获取map中的isEnd,通过isEnd是否等于1来判断该词是否为最后一个。如果isEnd == 1表示该词为敏感词,否则跳至1。

    通过这个步骤我们可以判断“冰毒”为敏感词,但是如果我们输入“冰箱”则不是敏感词了。

    工具类:

    
    import java.util.*;
    
    public class SensitiveWordUtil {
    
        public static Map<String, Object> dictionaryMap = new HashMap<>();
    
    
        /**
         * 生成关键词字典库
         * @param words
         * @return
         */
        public static void initMap(Collection<String> words) {
            if (words == null) {
                System.out.println("敏感词列表不能为空");
                return ;
            }
    
            // map初始长度words.size(),整个字典库的入口字数(小于words.size(),因为不同的词可能会有相同的首字)
            Map<String, Object> map = new HashMap<>(words.size());
            // 遍历过程中当前层次的数据
            Map<String, Object> curMap = null;
            Iterator<String> iterator = words.iterator();
    
            while (iterator.hasNext()) {
                String word = iterator.next();
                curMap = map;
                int len = word.length();
                for (int i =0; i < len; i++) {
                    // 遍历每个词的字
                    String key = String.valueOf(word.charAt(i));
                    // 当前字在当前层是否存在, 不存在则新建, 当前层数据指向下一个节点, 继续判断是否存在数据
                    Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key);
                    if (wordMap == null) {
                        // 每个节点存在两个数据: 下一个节点和isEnd(是否结束标志)
                        wordMap = new HashMap<>(2);
                        wordMap.put("isEnd", "0");
                        curMap.put(key, wordMap);
                    }
                    curMap = wordMap;
                    // 如果当前字是词的最后一个字,则将isEnd标志置1
                    if (i == len -1) {
                        curMap.put("isEnd", "1");
                    }
                }
            }
    
            dictionaryMap = map;
        }
    
        /**
         * 搜索文本中某个文字是否匹配关键词
         * @param text
         * @param beginIndex
         * @return
         */
        private static int checkWord(String text, int beginIndex) {
            if (dictionaryMap == null) {
                throw new RuntimeException("字典不能为空");
            }
            boolean isEnd = false;
            int wordLength = 0;
            Map<String, Object> curMap = dictionaryMap;
            int len = text.length();
            // 从文本的第beginIndex开始匹配
            for (int i = beginIndex; i < len; i++) {
                String key = String.valueOf(text.charAt(i));
                // 获取当前key的下一个节点
                curMap = (Map<String, Object>) curMap.get(key);
                if (curMap == null) {
                    break;
                } else {
                    wordLength ++;
                    if ("1".equals(curMap.get("isEnd"))) {
                        isEnd = true;
                    }
                }
            }
            if (!isEnd) {
                wordLength = 0;
            }
            return wordLength;
        }
    
        /**
         * 获取匹配的关键词和命中次数
         * @param text
         * @return
         */
        public static Map<String, Integer> matchWords(String text) {
            Map<String, Integer> wordMap = new HashMap<>();
            int len = text.length();
            for (int i = 0; i < len; i++) {
                int wordLength = checkWord(text, i);
                if (wordLength > 0) {
                    String word = text.substring(i, i + wordLength);
                    // 添加关键词匹配次数
                    if (wordMap.containsKey(word)) {
                        wordMap.put(word, wordMap.get(word) + 1);
                    } else {
                        wordMap.put(word, 1);
                    }
    
                    i += wordLength - 1;
                }
            }
            return wordMap;
        }
    
        public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("冰毒");
            initMap(list);
            String content="我是一个好人,买卖冰毒是违法的";
            Map<String, Integer> map = matchWords(content);
            System.out.println(map);
        }
    }
    
    展开全文
  • 前段时间,公司的IM SDK想做敏感词过滤,但是后端的小伙伴《比较忙》,在开产品需求会的时候想把敏感词过滤放到前端,让iOS、安卓自己搞,但是前端小伙伴写了一个方法来检测一段文本,耗时一两秒钟而且比较耗CPU,...

    在这里插入图片描述

    前言

    前段时间,公司的IM SDK想做敏感词过滤,但是后端的小伙伴《比较忙》,在开产品需求会的时候想把敏感词过滤放到前端,让iOS、安卓自己搞,但是前端小伙伴写了一个方法来检测一段文本,耗时【一两秒】钟而且比较耗CPU,这样肯定不行的,最后后端小伙伴妥协了,把敏感词过滤放到后端了。

    一般的思路可能是遍历敏感词库,然后把一段文字的敏感词过滤掉,但是针对比较大的词库时(比如我们的敏感词库10万),这样非常耗时和耗内存,在电脑上还能跑跑,但是在手机上分分钟钟被系统杀死掉,这样肯定是不行的,这里就用到一种DFA算法。

    但是使用了DFA算法,十万的敏感词库过滤一句话只需要【0.434510秒】!

    2019-10-23 14:34:08.230918+0800 DFAFilterDemo[4728:4650502] message == 小明骂小王是个王八蛋,小王骂小明是个王八羔子!
    2019-10-23 14:34:08.232972+0800 DFAFilterDemo[4728:4650502] result == 小明骂小王是个***,小王骂小明是个王八羔子!
    2019-10-23 14:34:08.316380+0800 DFAFilterDemo[4728:4650502] 总共耗时: 0.434510 
    

    DFA算法

    简介

    何谓DFA,它的全称是Deterministic Finite Automaton,即确定有穷自动机;其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的有限自动机,DFA中不会有从同一状态出发的两条边标志有相同的符号;DFA算法的核心是建立了以敏感词为基础的许多敏感词树。

    描述

    我们先把敏感词库拆分解析成一个”敏感词树“,我们以敏感词”王八蛋“和”王八羔子“为例:
    在这里插入图片描述
    拆成的敏感词树如下:
    在这里插入图片描述

    代码

    OC代码

    //
    //  DFAFilter.m
    //  DFAFilterDemo
    //
    //  Created by 张福杰 on 2019/10/22.
    //  Copyright © 2019 张福杰. All rights reserved.
    //
    
    #import "DFAFilter.h"
    
    @interface DFAFilter ()
    
    @property (nonatomic,strong) NSMutableDictionary *keyword_chains;
    @property (nonatomic,  copy) NSString *delimit;
    
    @end
    
    @implementation DFAFilter
    
    - (instancetype)init{
        if(self == [super init]){
            _delimit = @"\x00";
        }
        return self;
    }
    
    /// 读取解析敏感词
    - (void)parseSensitiveWords:(NSString *)path{
        if(path == nil){
            path = [[NSBundle mainBundle] pathForResource:@"sensitive_words" ofType:@"txt"];
        }
        NSString *content = [[NSString alloc] initWithContentsOfFile:path encoding:NSUTF8StringEncoding error:nil];
        NSArray *keyWordList = [content componentsSeparatedByString:@","];
        for (NSString *keyword in keyWordList) {
            [self addSensitiveWords:keyword];
        }
        
        NSLog(@"keyword_chains == %@",self.keyword_chains);
    }
    
    - (void)addSensitiveWords:(NSString *)keyword{
        keyword = keyword.lowercaseString;
        keyword = [keyword stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
        
        NSMutableDictionary *node = self.keyword_chains;
        for (int i = 0; i < keyword.length; i ++) {
            NSString *word = [keyword substringWithRange:NSMakeRange(i, 1)];
            if (node[word] == nil) {
                node[word] = [NSMutableDictionary dictionary];
            }
            node = node[word];
        }
        //敏感词最后一个字符标识
        [node setValue:@0 forKey:self.delimit];
    }
    
    - (NSString *)filterSensitiveWords:(NSString *)message replaceKey:(NSString *)replaceKey{
        replaceKey = replaceKey == nil ? @"*" : replaceKey;
        message = message.lowercaseString;
        NSMutableArray *retArray = [[NSMutableArray alloc] init];
        NSInteger start = 0;
        while (start < message.length) {
            NSMutableDictionary *level = self.keyword_chains.mutableCopy;
            NSInteger step_ins = 0;
            NSString *message_chars = [message substringWithRange:NSMakeRange(start, message.length - start)];
            for(int i = 0; i < message_chars.length; i++){
                NSString *chars_i = [message_chars substringWithRange:NSMakeRange(i, 1)];
                if([level.allKeys containsObject:chars_i]){
                    step_ins += 1;
                    NSDictionary *level_char_dict = level[chars_i];
                    if(![level_char_dict.allKeys containsObject:self.delimit]){
                        level = level_char_dict.mutableCopy;
                    }else{
                        NSMutableString *ret_str = [[NSMutableString alloc] init];
                        for(int i = 0; i < step_ins; i++){
                             [ret_str appendString:replaceKey];
                        }
                        [retArray addObject:ret_str];
                        start += (step_ins - 1);
                        break;
                    }
                }else{
                    [retArray addObject:[NSString stringWithFormat:@"%C",[message characterAtIndex:start]]];
                    break;
                }
            }
            start ++;
        }
        return [retArray componentsJoinedByString:@""];
    }
    
    - (NSMutableDictionary *)keyword_chains{
        if(_keyword_chains == nil){
            _keyword_chains = [[NSMutableDictionary alloc] initWithDictionary:@{}];
        }
        return _keyword_chains;
    }
    
    @end
    
    

    Swift代码

    //
    //  DFAFilter.swift
    //  DFAFilterDemo
    //
    //  Created by 张福杰 on 2019/10/23.
    //  Copyright © 2019 张福杰. All rights reserved.
    //
    
    import UIKit
    
    class DFAFilter: NSObject {
        lazy var keyword_chains: NSMutableDictionary = {
            let dict = NSMutableDictionary()
            return dict
        }()
        
        lazy var delimit: String = "\\x00";
        
        /// 读取敏感词
        func parseSensitiveWords() -> Void {
            let path = Bundle.main.path(forResource: "sensitive_words", ofType: "txt");
            let url = URL(fileURLWithPath: path!)
            do {
                let data = try Data(contentsOf: url)
                let content: String = String(data: data, encoding: String.Encoding.utf8)!
                let keyWordList = content.components(separatedBy: ",")
                for keyword in keyWordList {
                    addSensitiveWords(keyword)
                }
                
            } catch let error as Error? {
                print(error?.localizedDescription as Any)
            }
        }
        
        /// 添加敏感词到敏感词树
        func addSensitiveWords(_ keyword: String) -> Void {
            let keyword: String = keyword.lowercased().trimmingCharacters(in: .whitespacesAndNewlines)
            var node = self.keyword_chains
            if keyword.count <= 0{
                return
            }
            
            for index in 0...keyword.count - 1 {
                let index0 = keyword.index(keyword.startIndex, offsetBy: index)
                let index1 = keyword.index(keyword.startIndex, offsetBy: index + 1)
                let word = keyword[index0..<index1]
                if node[word] == nil{
                    node[word] = NSMutableDictionary()
                }
                node = node[word] as! NSMutableDictionary
            }
            node[self.delimit] = 0
        }
        
        /// 开始过滤敏感词
        func filterSensitiveWords(_ message: String, replaceKey: String) -> String {
            let replaceKey = replaceKey.count > 0 ? replaceKey : "*"
            let message = message.lowercased()
            let retArray: NSMutableArray = NSMutableArray()
            var start = 0
            while start < message.count {
                var level: NSMutableDictionary = self.keyword_chains.mutableCopy() as! NSMutableDictionary
                var step_ins = 0
                let message_chars = getChar(message, startIndex: start, endIndex: message.count)
                for index in 0...message_chars.count - 1 {
                    let chars_i = getChar(message_chars, startIndex: index, endIndex: index + 1)
                    if level[chars_i] != nil{
                        step_ins += 1
                        let level_char_dict: NSDictionary = level[chars_i] as! NSDictionary
                        if level_char_dict[self.delimit] == nil{
                            level = level_char_dict.mutableCopy() as! NSMutableDictionary
                        }else{
                            var ret_str = ""
                            for _ in 0...step_ins - 1 {
                                ret_str += replaceKey
                            }
                            retArray.add(ret_str)
                            start += (step_ins - 1)
                            break
                        }
                    }else{
                        let word = getChar(message, startIndex: start, endIndex: start + 1)
                        retArray.add(word)
                        break
                    }
                }
                start += 1
            }
    
            return retArray.componentsJoined(by: "")
        }
        
        func getChar(_ message: String, startIndex: NSInteger, endIndex: NSInteger) -> String {
            let index0 = message.index(message.startIndex, offsetBy: startIndex)
            let index1 = message.index(message.startIndex, offsetBy: endIndex)
            let word = message[index0..<index1]
            return String(word)
        }
    
    }
    
    

    Python代码

    # -*- coding: utf-8 -*-
    # @Author: zhangfujie
    # @Date:   2019/10/22
    # @Last Modified by:   zhangfujie
    # @Last Modified time: 2019/10/22
    # @ ---------- DFA过滤算 ---------- 
    import time
    time1 = time.time()
    
    class DFAFilter(object):
    	"""DFA过滤算法"""
    	def __init__(self):
    		super(DFAFilter, self).__init__()
    		self.keyword_chains = {}
    		self.delimit = '\x00'
    
    	# 读取解析敏感词
    	def parseSensitiveWords(self, path):
    		ropen = open(path,'r')
    		text = ropen.read()
    		keyWordList = text.split(',')
    		for keyword in keyWordList:
    			self.addSensitiveWords(str(keyword).strip())
    
    	# 生成敏感词树
    	def addSensitiveWords(self, keyword):
    		keyword = keyword.lower()
    		chars = keyword.strip()
    		if not chars:
    			return
    		level = self.keyword_chains
    		for i in range(len(chars)):
    			if chars[i] in level:
    				level = level[chars[i]]
    			else:
    				if not isinstance(level, dict):
    					break
    				for j in range(i, len(chars)):
    					level[chars[j]] = {}
    
    					last_level, last_char = level, chars[j]
    
    					level = level[chars[j]]
    				last_level[last_char] = {self.delimit: 0}
    				break
    			if i == len(chars) - 1:
    				level[self.delimit] = 0
    
    	# 过滤敏感词
    	def filterSensitiveWords(self, message, repl="*"):
    		message = message.lower()
    		ret = []
    		start = 0
    		while start < len(message):
    			level = self.keyword_chains
    			step_ins = 0
    			message_chars = message[start:]
    			for char in message_chars:
    				if char in level:
    					step_ins += 1
    					if self.delimit not in level[char]:
    						level = level[char]
    					else:
    						ret.append(repl * step_ins)
    						start += step_ins - 1
    						break
    				else:
    					ret.append(message[start])
    					break
    			start += 1
    
    		return ''.join(ret)
    
    
    if __name__ == "__main__":
    	gfw = DFAFilter()
    	gfw.parseSensitiveWords('shieldwords.txt')
    	text = "小明骂小王是个王八蛋,小王骂小明是个王八羔子!"
    	result = gfw.filterSensitiveWords(text)
    	print(result)
    	time2 = time.time()
    	print('总共耗时:' + str(time2 - time1) + 's')	
    

    结束语

    demo下载地址: https://gitee.com/zfj1128/DFAFilterDemo
    过往大佬喜欢的给个小星星吧!

    欢迎各位大神提出宝贵的意见和建议,也欢迎大家进群交流365152048!

    CSDN博客 https://zfj1128.blog.csdn.net
    GITEE主页 https://gitee.com/zfj1128
    GITHUB主页 https://github.com/zfjsyqk
    展开全文
  • 敏感词汇过滤DFA算法

    2016-03-06 12:53:08
    敏感词汇过滤DFA算法
  • DFA算法+敏感词过滤

    2018-12-26 14:38:42
    DFA算法+敏感/违禁词过滤,高效过滤,10W+词语过滤,100ms执行时效
  • 敏感词过滤-DFA算法

    千次阅读 2019-04-15 16:08:29
    Java实现DFA算法实现敏感词过滤 测试方法 创建DFAMap 根据DFAMap进行检验 完整代码 DFA算法简介 在实现文字过滤算法中,DFA是唯一比较好的实现算法DFA即Deterministic Finite Automaton,也就是确定有穷...
  • 在敏感词汇过滤这块,不同的算法所造成的性能差异是非常大的,选择一个合适的算法非常重要。因为以前做算法的时候做过类似前缀树的字符串匹配之类的算法,所以一...这个算法并不是目前最好的敏感词过滤算法,但是比.
  • 已在项目中使用,绝对是你想要的,高效的DFA算法实现的敏感词过滤功能。
  • 1、DFA过滤敏感词算法 在实现文字过滤的算法中,DFA是比较好的实现算法。DFA即Deterministic Finite Automaton,也就是确定有穷自动机。 算法核心是建立了以敏感词为基础的许多敏感词树。 python 实现DFA算法: ...
  • 敏感词文字过滤是一个网站必不可少的功能,如何设计一个好的、高效的过滤算法是非常有必要的。作为一般开发人员来说首先考虑的肯定是简单的匹配,这样是可以实现功能,但效率比较慢,在高级一点的就是正则表达式,比...
  • DFA算法敏感词过滤

    2019-04-13 17:44:00
    # coding=utf-8 import time time1 = time.time() ...# DFA算法 class DFAFilter(object): def __init__(self): self.keyword_chains = {} # 关键词链表 self.delimit = '\x00' # 限定 ...
  • 1、DFA过滤敏感词算法 在实现文字过滤的算法中,DFA是比较好的实现算法。DFA即Deterministic Finite Automaton,也就是确定有穷自动机。 算法核心是建立了以敏感词为基础的许多敏感词树。 python 实现DFA算法: ...
  • DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的...
  • java。dfa算法实现敏感词过滤
  • thinkcmfx存放目录 及用法 simplewind\Core\Library\Vendor\... // 过滤 $filterContent = SensitiveHelper::init()->setTreeByFile($path_web)->replace($content, ''); return $filterContent; } }
  • 在实现文字过滤算法中,DFA是唯一比较好的实现算法DFA即Deterministic Finite Automaton,也就是确定有穷自动机,它是是通过event和当前的state得到下一个state,即event+state=nextstate。下图展示了其状态的...
  • 一道bat面试题:快速替换10亿条标题中的5万个敏感词,有...1、DFA过滤敏感词算法 在实现文字过滤的算法中,DFA是比较好的实现算法。DFA即Deterministic Finite Automaton,也就是确定有穷自动机。 算法核心是建立了...
  • C#过滤敏感词DFA算法

    2019-09-08 18:23:09
    今天游戏正好用到需要过滤敏感词将出现的敏感词替换成*,在网上找了许久找了一片可用的java版本的DFA算法,最后费了一番功夫将其思路用C#实现,里面的注释甚至都没改动的,这里直接上代码,这里不借助任何第三方工具...
  • DFA简介 DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于...
  • DFA算法过滤敏感词

    2013-11-25 15:44:46
     * 创建DFA     * @param keywordList     * @throws UnsupportedEncodingException     */     public   void  createKeywordTree(List keywordList)  throws  ...
  • java使用dfa算法实现敏感词过滤,此算法效率最高,附带了一个敏感词库,轻松搞定论坛网站的敏感词过滤问题。

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 325
精华内容 130
关键字:

dfa过滤算法