利用 DFA 算法实现文字过滤

一、DEA 算法简介

在实现文字过滤的算法中,DFA是唯一比较好的实现算法。

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

简单点说就是,它是是通过 event 和当前的 state 得到下一个 state,即 event + state= nextstate。理解为系统中有多个节点,通过传递进入的 event,来确定走哪个路由至另一个节点,而节点是有限的。

二、DEA 算法实践敏感词过滤

1. 敏感词库构造

以王八蛋和王八羔子两个敏感词来进行描述,首先构建敏感词库,该词库名称为SensitiveMap,这两个词的二叉树构造为:

用 hash 表构造为:

{
    "王":{
        "isEnd":"0",
        "八":{
            "羔":{
                "子":{
                    "isEnd":"1"
                },
                "isEnd":"0"
            },
            "isEnd":"0",
            "蛋":{
                "isEnd":"1"
            }
        }
    }
}

怎么用代码实现这种数据结构呢?

    /**
     * 读取敏感词库,将敏感词放入HashSet中,构建一个DFA算法模型
     *
     * @param keyWordSet 敏感词库
     */
    public Map<String, Object> addSensitiveWordToHashMap(Set<String> keyWordSet) {
        //初始化敏感词容器,减少扩容操作
        Map<String, Object> map = new HashMap(Math.max((int) (keyWordSet.size() / .75f) + 1, 16));
        //迭代keyWordSet
        for (String aKeyWordSet : keyWordSet) {
            Map nowMap = map;
            for (int i = 0; i < aKeyWordSet.length(); i++) {
                //转换成char型
                char keyChar = aKeyWordSet.charAt(i);
                //获取
                Object wordMap = nowMap.get(keyChar);
                //如果存在该key,直接赋值
                if (wordMap != null) {
                    nowMap = (Map) wordMap;
                } else {     //不存在则,则构建一个map,同时将isEnd设置为0
                    Map<String, String> newWorMap = new HashMap<>(3);
                    newWorMap.put("isEnd", "0");
                    nowMap.put(keyChar, newWorMap);
                    nowMap = newWorMap;
                }
                //判断最后一个
                if (i == aKeyWordSet.length() - 1) {
                    nowMap.put("isEnd", "1");
                }
            }
        }
        return map;
    }

2. 敏感词过滤

以上面例子构造出来的 SensitiveMap 为敏感词库进行示意,假设这里输入的关键字为:王八不好,流程图如下:

怎么用代码实现这个流程图逻辑呢?

    /**
     * 查找字符串中是否包含敏感字符
     *
     * @param txt 输入的字符串
     * @return 如果存在,则返回敏感字符串;不存在,则返回空字符串
     */
    public static String findSensitiveWord(String txt) {
        SensitiveWordInit sensitiveWordInit = SpringContextHolder.getBean(SensitiveWordInit.class);
        Map<String, Object> sensitiveWordMap = sensitiveWordInit.getSensitiveWordMap();
        StringBuilder sensitiveWord = new StringBuilder();
        // 敏感词结束标志位,表示匹配到了最后一位
        boolean flag = false;
        for (int i = 0; i < txt.length(); i++) {
            char word = txt.charAt(i);
            // 获取指定 key
            sensitiveWordMap = (Map) sensitiveWordMap.get(word);
            // 不存在,直接返回没有敏感词
            if (sensitiveWordMap == null) {
                break;
            }
            //存在,存储该敏感词,并判断是否为最后一个
            sensitiveWord.append(word);
            //如果为最后一个匹配规则,结束循环
            if ("1".equals(sensitiveWordMap.get("isEnd"))) {
                flag = true;
                break;
            }
        }
        // 表示匹配到了完整敏感词
        if (flag == true) {
            return sensitiveWord.toString();
        }
        return "";
    }

三、优化思路

对于“王*八&&蛋”这样的词,中间填充了无意义的字符来混淆,在我们做敏感词搜索时,同样应该做一个无意义词的过滤,当循环到这类无意义的字符时进行跳过,避免干扰。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏刷题笔记

【Leet Code】20. Valid Parentheses

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

6620
来自专栏刷题笔记

【LeetCode】 11. Container With Most Water

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

5830
来自专栏刷题笔记

2-2 学生成绩链表处理 (20 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

6320
来自专栏刷题笔记

【LeetCode第 161 场周赛】回顾

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

5630
来自专栏刷题笔记

3-2 数组元素的区间删除 (20 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

6630
来自专栏刷题笔记

2-5 Two Stacks In One Array (20 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

7320
来自专栏刷题笔记

【LeetCode】21. Merge Two Sorted Lists

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

7630
来自专栏刷题笔记

【LeetCode】5. Longest Palindromic Substring

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

6630
来自专栏刷题笔记

【Leet Code】22. Generate Parentheses

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

6220
来自专栏刷题笔记

3-9 堆栈模拟队列 (20 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

5930

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励