DFA算法，高效实现敏感词检测与替换！

创作时间:

作者:

@小白创作中心

DFA算法，高效实现敏感词检测与替换！

引用

CSDN

https://blog.csdn.net/yangyufneg/article/details/137222768

在信息爆炸的时代，网络上充斥着大量的敏感信息，可能会产生很多的负面影响。为了应对这一挑战，一直在寻求有效的方式来替换或过滤掉敏感字词，而Java DFA（Deterministic Finite Automaton）算法正是在这方面发挥着关键作用。

什么是DFA算法？

DFA即Deterministic Finite Automaton，是一种有穷自动机，通常用于处理字符串匹配问题。在Java中，DFA算法用于搜索和替换文本中的特定模式，如敏感字词或关键词。DFA算法通过将文本逐字符逐字符地与事先定义好的敏感字列表进行比较，从而快速而高效地检测和替换敏感字。

Java DFA算法的工作原理

DFA算法基于状态转移。它首先构建一个状态转移图，其中每个状态代表算法在处理字符串时的状态。然后，算法从输入文本的开头开始，根据当前字符和当前状态，查找下一个状态，并根据状态的不同采取不同的操作。当输入文本中的字符被处理完毕时，算法会得到一个已替换敏感字的文本或者是否包含敏感词的一个状态。

例如替换文本中的敏感词：

文本：Java新视界，为你开启Java世界的大门。实用技巧，深度解析，让Java更简单，更强大！一起攀登Java技术高峰，实现编程梦想！
敏感词列表：["新视界", "新视野", "技术", "技术高峰", "编程梦想", "实现梦想"]

基于敏感词，构建森林：

基于森林，构建JSON对象：

{
    "技":{
        "isEnd":"0",
        "术":{
            "高":{
                "峰":{
                    "isEnd":"1"
                },
                "isEnd":"0"
            },
            "isEnd":"1"
        }
    },
    "新":{
        "isEnd":"0",
        "视":{
            "界":{
                "isEnd":"1"
            },
            "isEnd":"0",
            "野":{
                "isEnd":"1"
            }
        }
    },
    "编":{
        "isEnd":"0",
        "程":{
            "isEnd":"0",
            "梦":{
                "isEnd":"0",
                "想":{
                    "isEnd":"1"
                }
            }
        }
    },
    "实":{
        "现":{
            "isEnd":"0",
            "梦":{
                "isEnd":"0",
                "想":{
                    "isEnd":"1"
                }
            }
        },
        "isEnd":"0"
    }
}

DFA算法实现

import java.util.*;

/**
 * 敏感词处理工具 - DFA算法实现
 * @author Java新视界
 * @modifier Java新视界
 * @date 2023/10/25 16:58
 */
public class SensitiveWordUtil {
    /**
     * 敏感词匹配规则
     */
    public static final int MIN_MATCH_TYPE = 1;      //最小匹配规则，如：敏感词库["新视界","视界"]，语句："Java新视界"，匹配结果：Java新[视界]
    public static final int MAX_MATCH_TYPE = 2;      //最大匹配规则，如：敏感词库["新视界","视界"]，语句："Java新视界"，匹配结果：Java[新视界]

    private static Map<String, Object> initSensitiveWordMap(Set<String> sensitiveWordSet) {
        Map<String, Object> map = new HashMap(Math.max((int) (sensitiveWordSet.size() / .75f) + 1, 16));    //初始化敏感词容器，减少扩容操作
        for (String aKeyWordSet : sensitiveWordSet) {   //迭代keyWordSet
            Map nowMap = map;
            for (int i = 0; i < aKeyWordSet.length(); i++) {
                char keyChar = aKeyWordSet.charAt(i);
                Object wordMap = nowMap.get(keyChar);
                if (wordMap != null) {
                    nowMap = (Map) wordMap;         //如果存在该key，直接赋值
                } 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;
    }

    public static Set<String> getSensitiveWord(Set<String> sensitiveWordSet,String txt, int matchType) {
        Set<String> sensitiveWordList = new HashSet<>();
        Map<String, Object> map = initSensitiveWordMap(sensitiveWordSet);
        for (int i = 0; i < txt.length(); i++) {     //判断是否包含敏感字符
            int length = checkSensitiveWord(map,txt, i, matchType);
            if (length > 0) {           //存在,加入list中
                sensitiveWordList.add(txt.substring(i, i + length));
                i = i + length - 1;     //减1的原因，是因为for会自增
            }
        }

        return sensitiveWordList;
    }

    public static String replaceSensitiveWord(Set<String> sensitiveWordSet, String txt, char replaceChar, int matchType) {
        String resultTxt = txt;
        //获取所有的敏感词
        Set<String> set = getSensitiveWord(sensitiveWordSet,txt, matchType);
        Iterator<String> iterator = set.iterator();
        String word;
        String replaceString;
        while (iterator.hasNext()) {
            word = iterator.next();
            replaceString = getReplaceChars(replaceChar, word.length());
            resultTxt = resultTxt.replaceAll(word, replaceString);
        }

        return resultTxt;
    }

    public static String replaceSensitiveWord(Set<String> sensitiveWordSet, String txt, String replaceStr, int matchType) {
        String resultTxt = txt;
        //获取所有的敏感词
        Set<String> set = getSensitiveWord(sensitiveWordSet,txt, matchType);
        Iterator<String> iterator = set.iterator();
        String word;
        while (iterator.hasNext()) {
            word = iterator.next();
            resultTxt = resultTxt.replaceAll(word, replaceStr);
        }

        return resultTxt;
    }

    private static String getReplaceChars(char replaceChar, int length) {
        String resultReplace = String.valueOf(replaceChar);
        for (int i = 1; i < length; i++) {
            resultReplace += replaceChar;
        }

        return resultReplace;
    }

    private static int checkSensitiveWord(Map<String, Object> nowMap, String txt, int beginIndex, int matchType) {
        boolean flag = false;
        int matchFlag = 0;
        char word;
        for (int i = beginIndex; i < txt.length(); i++) {
            word = txt.charAt(i);
            //获取指定key
            nowMap = (Map<String, Object>) nowMap.get(word);
            if (nowMap != null) {               //存在，则判断是否为最后一个
                matchFlag++;                    //找到相应key，匹配标识+1
                //如果为最后一个匹配规则,结束循环，返回匹配标识数
                if ("1".equals(nowMap.get("isEnd"))) {
                    flag = true;                //结束标志位为true
                    //最小规则，直接返回,最大规则还需继续查找
                    if (MIN_MATCH_TYPE == matchType) {
                        break;
                    }
                }
            } else {                            //不存在，直接返回
                break;
            }
        }
        if (matchFlag < 2 || !flag) {           //长度必须大于等于1，为词
            matchFlag = 0;
        }
        return matchFlag;
    }
}

DFA算法测试

public static void main(String[] args) {
    Set<String> sensitiveWordSet = new HashSet<>(Arrays.asList("新视界", "新视野","技术", "技术高峰", "编程梦想", "实现梦想"));
    String string = "Java新视界，为你开启Java世界的大门。实用技巧，深度解析，让Java更简单，更强大！一起攀登Java技术高峰，实现编程梦想！";
    //获取语句中的敏感词
    Set<String> set = SensitiveWordUtil.getSensitiveWord(sensitiveWordSet,string, SensitiveWordUtil.MAX_MATCH_TYPE);
    System.out.println("语句中 包含敏感词的个数为：" + set.size() + "。包含：" + set);
    set = SensitiveWordUtil.getSensitiveWord(sensitiveWordSet,string, SensitiveWordUtil.MIN_MATCH_TYPE);
    System.out.println("语句中 包含敏感词的个数为：" + set.size() + "。包含：" + set);
    //替换语句中的敏感词
    String filterStr = SensitiveWordUtil.replaceSensitiveWord(sensitiveWordSet,string, '*', SensitiveWordUtil.MAX_MATCH_TYPE);
    System.out.println(filterStr);
    filterStr = SensitiveWordUtil.replaceSensitiveWord(sensitiveWordSet,string, '*', SensitiveWordUtil.MIN_MATCH_TYPE);
    System.out.println(filterStr);
}

运行结果：