利用 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 "";
    }

三、优化思路

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