DFA敏感词过滤算法详解

如果你不相信努力和时光,那么成果就会是第一个选择辜负你的。不要去否定你自己的过去,也不要用你的过去牵扯你现在的努力和对未来的展望。不是因为拥有希望你才去努力,而是去努力了,你才有可能看到希望的光芒。DFA敏感词过滤算法详解,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

功能简介

DFA算法模型是解决针对一段文本,过滤出其他文本。比如我们定义了三段文本a、b和c为“张三”、“程序员”、“开发”,而在文本d“我的名字叫张三,我是一名刚工作一年的程序员”的内容中,可以发现文本d是包含a和b文本的,这个过程就是DFA算法模型实现的功能。DFA算法的核心是构建出一个模型。

抛出疑问

  1. java中有contain方法进行判断a文本是否包含b文本,为什么不直接用contain进行比较呢?
  2. DFA算法用Java如何构建?
  3. DFA算法性能如何?

算法思想

举个例子,假如我们认为以下是敏感词。

 1. 我是张三
 2. 我是李四
 3. 大王八
 4. 大王来了

然后我们根据上面的敏感词构建出一个模型,该模型实际上是一颗树,或者说是森林。在java代码中实际上是多个map,为了方便观察,我转换成了json。(不完整版本)

    {
        "我": {
            "是": {
                "张": {
                    "三": {}
                },
                "李": {
                    "四": {}
                }
            }
        },
        "大": {
            "王": {
                "来": {
                    "了": {}
                },
                "八": {}
            }
        }
    }

我们通过上面构建的模型对目标文本“我是张三,我是大王”进行敏感词过滤,大致过程如下:

1. 遍历目标文本,获取到第一个字符‘我’,在我们构建的模型的第一层比较,发现第一层的字符串是‘我’和‘大’。
2. 字符‘我’能够在模型中匹配到,继续获取目标文本的下一个字符‘是’,发现第二层也是‘是’,也是匹配上了,依次是‘张’、‘三’。
3. 通过步骤2我们可以断定目标文本中“我是张三”是敏感词,记录下来。
4. 继续获取下一个字符,这里节省时间直接跳到‘大’的字符,发现可以和第一层的‘大’匹配上,然后获取目标文本中的下一个字符‘王’,也能够在模型中匹配上。
5. 这样整个匹配过程完成了,大家可能有疑问,那到底“大王”算不算敏感词呢?如果算,但是我们在定义敏感词的时候并没有“大王”;如果不算,但确实是匹配上了。

为了解决这个问题,我们在构建好的模型中加一个字段就可以解决这种摸棱两可的问题。

{
        "我": {
            "isEnd": false,
            "是": {
                "张": {
                    "三": {
                        "isEnd": true
                    },
                    "isEnd": false
                },
                "isEnd": false,
                "李": {
                    "四": {
                        "isEnd": true
                    },
                    "isEnd": false
                }
            }
        },
        "大": {
            "王": {
                "来": {
                    "了": {
                        "isEnd": true
                    },
                    "isEnd": false
                },
                "八": {
                    "isEnd": true
                },
                "isEnd": false
            },
            "isEnd": false
        }
    }

可以看到加了一个isEnd字段进行记录构建的模型,每段敏感词的结尾是true,如果不是结尾则是false,比如“我”“我是”“我是张”都为false,而“我是张三”为true。通过这个字段每次来判断敏感词校验是否到了敏感词的结尾。
回到上面的问题:“大王”到底算不算敏感词呢?
根据上面的分析,只有完整匹配上模型中的敏感词才能算敏感词,所以在比较‘王’的时候发现isEnd是false,说明“大王”只是“大王八”或者“大王来了”的一部分,并不能算敏感词。所以目标文本“我是张三,我是大王”中“我是张三”是敏感词,“大王”不是敏感词。

构建DFA模型

下面用java代码构建一个DFA模型

    /**
     * @param keyWordSet 敏感词库
     */
    private Map addSensitiveWordToHashMap(Set<String> keyWordSet) {
        // 初始化敏感词容器,减少扩容操作
        Map sensitiveWordMap = new HashMap(keyWordSet.size());
        String key;
        Map nowMap;
        Map<String, String> newWordMap;
        // 遍历keyWordSet
        for (String aKeyWordSet : keyWordSet) {
            // 关键字
            key = aKeyWordSet;
            nowMap = sensitiveWordMap;
            for (int i = 0; i < key.length(); i++) {
                // 转换成char型
                char keyChar = key.charAt(i);
                // 65279是一个空格,遇到空格直接跳过即可
                if ((int) keyChar == 65279) {
                    continue;
                }
                // 获取
                Object wordMap = nowMap.get(keyChar);

                if (wordMap != null) {
                    // 如果存在该key,直接赋值
                    nowMap = (Map) wordMap;
                } else {
                    // 不存在则,则构建一个map,同时将isEnd设置为0,因为他不是最后一个
                    newWordMap = new HashMap<>();
                    // 不是最后一个
                    newWordMap.put("isEnd", "0");
                    nowMap.put(keyChar, newWordMap);
                    nowMap = newWordMap;
                }

                if (i == key.length() - 1) {
                    // 最后一个
                    nowMap.put("isEnd", "1");
                }
            }
        }
        return sensitiveWordMap;
    }

构建好模型之后,通过下面方法进行判断是否存在敏感词。

    /**
     * 过滤出敏感词
     *
     * @param txt        目标文本
     * @param matchType  匹配模式  1、最小匹配模式  2、最大匹配模式
     */
public Set<String> getSensitiveWordSets(String txt, int matchType) {
        Set<String> sensitiveWordSets = new HashSet<>();
        for (int n = 0; n < txt.length(); n++) {
            // 判断是否包含敏感字符
            int length = judgeSensitiveWithIndex(txt, n, matchType);
            if (length > 0) {
                // 存在,加入list中
                sensitiveWordSets.add(txt.substring(n, n + length));
                // 减1的原因,是因为for会自增
                n = n + length - 1;
            }
        }
        return sensitiveWordSets;
    }

    /**
     * 根据指定位置是否是敏感词的开始
     *
     * @param txt        文本
     * @param beginIndex 开始位置
     * @param matchType  匹配模式  1、最小匹配模式  2、最大匹配模式
     * @return int
     */
    private int judgeSensitiveWithIndex(String txt, int beginIndex, int matchType) {
        // 匹配标识数默认为0
        int matchFlag = 0;
        char word;
        boolean isEnd = false;
        Map nowMap = sensitiveWordMap;
        for (int i = beginIndex; i < txt.length(); i++) {
            word = txt.charAt(i);
            // 获取指定key
            nowMap = (Map) nowMap.get(word);
            // 存在,则判断是否为最后一个
            if (nowMap != null) {
                // 找到相应key,匹配标识+1
                matchFlag++;
                if ((boolean) nowMap.get("isEnd")) {
                    // 如果为最后一个匹配规则,结束循环,返回匹配标识数
                    isEnd = true;
                    break;
                }
            } else {
                // 不存在,直接返回
                break;
            }
        }

        if (1 == matchType) {
            // 最小匹配模式
            return matchFlag;
        }
        // 最大匹配模式
        if (isEnd) {
            return matchFlag;
        }
        return 0;
    }

解答疑问

1. java中有contain方法进行判断a文本是否包含b文本,为什么不直接用contain进行比较呢?
可以从两方面考虑:
功能方面,contain只能进行最大匹配模式进行匹配,比如目标文本“我是张三,我是大王”,针对敏感词“大王八”,目标文本中的“大王”正常来说是不算敏感词的,但是要是有这么个需求就认为“大王”是敏感词,那么contain就不能满足这个需求了。而DFA可以设置最小匹配模式,可以过滤出“大王”是敏感词。
性能方面,contain是针对每次比对一个敏感词,尽管有containAny,但底层还是对每个敏感词进行比对,也就意味着,有一万个敏感词,就要比对一万次,性能相对很低;而DFA算法不管有多少敏感词,只需要对目标文本遍历一次,便可以获取目标文本涉及到的所有敏感词。
2. DFA算法用Java如何构建?
用java实现实际上就是一层层map的嵌套,核心思想就是通过遍历文本的每个字符,然后去map中找到对应的key一层层进行比对,具体实现如上。
3. DFA算法性能如何?
DFA算法的性能取决于目标文本的长度,遍历一次目标文本即可获取所有涉及到的敏感词,尤其适合针对于实时聊天软件的敏感词过滤;假设目标文本的长度为n,它的时间复杂度为O(n)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/192063.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!