一、需求背景
敏感词检测，几乎是所有博客、文章、日志等这类公开性发表的以文字形式记录的作品都绕不过去的产品需求，那么，是否有一些比较高效的方法来检测文章的敏感词呢？我想，DFA（确定性有限状态机算法）是其中的佼佼者。
DFA算法，全称为确定性有限状态自动机算法，是一种常见的字符串匹配算法。它通过构建一个状态转移来表现字符串匹配，具有高效、快速的特点。与之相对的是NFA算法，NFA算法可以匹配更加复杂的正则表达式，但是相对来说效率较低。在实际应用中，DFA算法尝尝被用于词法分析、字符串匹配等领域。
二、算法实现
DFA 2.1 算法
import com.microblog.cache.RedisTemplateService;
import com.microblog.exception.BusinessException;
import com.microblog.util.tools.FileUtils;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.util.*;
import static com.microblog.constant.Constants.SENSITIVE_WORD_FILE_URL;
/**
* 敏感词工具类 : 基于DFA（Deterministic Finite Automaton）确定性优先状态机算法的敏感词检测
* 返回结果 调用方式
* void SensiWordUtil.refreshSensiMap() 刷新、重新生成敏感词汇树
* void SensiWordUtil.isContaintSensitiveWord(String txt) 判断txt中是否存在敏感词
* String SensiWordUtil.replaceSensitiveWord(String txt,String replaceChar) 用replaceChar替换txt中的敏感词，并返回结果
* boolean SensiWordUtil.delWord(String word) 删除一个敏感词汇
* boolean SensiWordUtil.addWord(String word) 添加一个敏感词汇
*/
public class SensitiveWordUtil {
/**
* 敏感词库文件路径,一般都是配置在OSS里面
*/
private static String getPath;
//词库树
private static HashMap<String, String> sensitiveWordMap = null;
/**
* 初始化敏感词树
*
* @return
*/
public static void initKeyWord(String path) {
getPath = path;
try {
//读取敏感词库
List<String> keyWordList = readSensitiveWordFile(path);
//将敏感词库加入到HashMap中
addSensitiveWordToHashMap(keyWordList);
}
catch (Exception e) {
e.printStackTrace();
}
}
/**
* 删除一个敏感词词汇,true 删除成功
*
* @param word
* @return
*/
public static boolean delWord(String word) {
boolean flag = false;
if (null == sensitiveWordMap || sensitiveWordMap.isEmpty()) {
//没有敏感词树，直接返回false
return false;
}
if (null == word || "".endsWith(word)) {
//输入的词汇有误，返回false
return false;
}
Map curNote = sensitiveWordMap;
for (int i = 0; i < word.length(); i++) {
char wordChar = word.charAt(i);
//获取
Object wordMap = curNote.get(wordChar);
if (null == wordMap) {
//不存在当前敏感词汇
return true;
}
//判断是否最后一个词
Map temp = (Map) wordMap;
String isEndVal = temp.get("isEnd") + "";
if ("1".equals(isEndVal) && i == word.length() - 1) {
//找到了最后一个节点，删除
curNote.remove(wordChar);
return true;
}
if ("1".equals(isEndVal) && i != word.length() - 1) {
//不存在当前词汇
return true;
}
//递归当前点
curNote = (Map) wordMap;
}
return flag;
}
/**
* 添加一个新词到树
*
* @param word
* @return
*/
public static boolean addWord(String word) {
try {
if (null == sensitiveWordMap) {
//初始化敏感词容器
sensitiveWordMap = new HashMap();
}
Map curMap = sensitiveWordMap;
loadMapTree(word, curMap);
return true;
}
catch (Exception e) {
e.printStackTrace();
return false;
}
}
/**
* 读取敏感词库中的内容
*
* @return
* @throws Exception
*/
private static List<String> readSensitiveWordFile(String path) throws Exception {
List<String> list;
//File file = new File("D:\\SensitiveWord\\SensitiveWord.txt"); //读取文件
File file = new FileUtils().readFileFromNet(path);
try (InputStreamReader read = new InputStreamReader(Files.newInputStream(file.toPath()),
StandardCharsets.UTF_8)) {
if ((!file.isFile()) || (!file.exists())) {
throw new BusinessException("敏感词库文件不存在");
}
list = new ArrayList<>();
BufferedReader bufferedReader = new BufferedReader(read);
String txt = null;
while ((txt = bufferedReader.readLine()) != null) {
list.add(txt);
}
bufferedReader.close();
}
return list;
}
/**
* 读取敏感词库，将敏感词放入HashMap中（汉字作为key值，value值为hashMap 包括：isEnd节点、多个汉字子节点 ），构建一个DFA算法模型：
* @param keyWordList
*/
//公司职工管理员工薪资
// 公 = {
// isEnd = 0
// 司 = {
// isEnd = 1
// 职 = {
// isEnd = 0
// 工 = {
// isEnd = 1
// }
// }
// 管 = {
// isEnd = 0
// 理 = {
// isEnd = 1
// }
// }
// }
// }
// 员 = {
// isEnd = 0
// 工 = {
// isEnd = 0
// 薪 = {
// isEnd = 0
// 资 = {
// isEnd = 1
// }
// }
// }
// }
private static void addSensitiveWordToHashMap(List<String> keyWordList) {
if (null == keyWordList || 0 == keyWordList.size()) {
return;
}
sensitiveWordMap = new HashMap(keyWordList.size()); //初始化敏感词容器，减少扩容操作
String key;
Map nowMap;
//迭代keyWordSet
for (String s : keyWordList) {
key = s; //关键字
nowMap = sensitiveWordMap;
loadMapTree(key, nowMap);
}
}
/**
* 加载MapTree
*
* @param key
* @param nowMap
*/
private static void loadMapTree(String key, Map nowMap) {
Map<String, String> newWorMap;
for (int i = 0; i < key.length(); i++) {
char keyChar = key.charAt(i); //转换成char型
Object wordMap = nowMap.get(keyChar);
if (wordMap != null) { //如果存在该key，直接赋值
nowMap = (Map) wordMap;
} else { //不存在则，则构建一个map，同时将isEnd设置为0，因为他不是最后一个
newWorMap = new HashMap<String, String>();
newWorMap.put("isEnd", "0"); //不是最后一个
nowMap.put(keyChar, newWorMap);
nowMap = newWorMap;
}
if (i == key.length() - 1) {
nowMap.put("isEnd", "1"); //最后一个
}
}
}
/**
* 判断文字是否包含敏感字符
*
* @param txt 检测字
* @return
*/
public static boolean isContainSensitiveWord(String txt) {
int matchType = 1; //匹配规则 1：最小匹配规则，2：最大匹配规则
if (null == sensitiveWordMap || sensitiveWordMap.isEmpty()) {
//如果敏感词树不存在创建
initKeyWord(getPath);
//如果初始化之后还是null，则没有敏感词库
if (null == sensitiveWordMap) {
return false;
}
}
boolean flag = false;
for (int i = 0; i < txt.length(); i++) {
int matchFlag = CheckSensitiveWord(txt, i, matchType); //判断是否包含敏感字符
if (matchFlag > 0) { //大于0存在，返回true
flag = true;
break;
}
}
return flag;
}
/**
* 检查文字中是否包含敏感字符,如果存在，则返回敏感词字符的长度，不存在返回0
*
* @param txt
* @param beginIndex
* @param matchType
* @return
*/
private static int CheckSensitiveWord(String txt, int beginIndex, int matchType) {
boolean flag = false; //敏感词结束标识位：用于敏感词只有1位的情况
int matchFlag = 0; //匹配标识数默认为0
char word = 0;
if (sensitiveWordMap == null) {
getPath = RedisTemplateService.getRedisTemplate().opsForValue().get(SENSITIVE_WORD_FILE_URL);
initKeyWord(getPath);
}
Map nowMap = sensitiveWordMap;
for (int i = beginIndex; i < txt.length(); i++) {
word = txt.charAt(i);
nowMap = (Map) nowMap.get(word); //获取指定key
if (nowMap == null) {
break;//不存在，直接返回
}
//存在，则判断是否为最后一个
matchFlag++; //找到相应key，匹配标识+1
if ("1".equals(nowMap.get("isEnd"))) { //如果为最后一个匹配规则,结束循环，返回匹配标识数
flag = true; //结束标志位为true
//最小匹配规则
int minMatchTYpe = 1;
if (minMatchTYpe == matchType) { //最小规则，直接返回,最大规则还需继续查找
break;
}
}
}
if (!flag) {
matchFlag = 0;
}
return matchFlag;
}
/**
* 替换敏感字字符
*
* @param txt
* @param replaceChar
* @return
*/
public static String replaceSensitiveWord(String txt, String replaceChar) {
if (null == sensitiveWordMap || sensitiveWordMap.isEmpty()) {
//如果敏感词树不存在创建
initKeyWord(getPath);
//如果初始化之后还是null，则没有敏感词库
if (null == sensitiveWordMap) {
return txt;
}
}
int matchType = 1;
String resultTxt = txt;
Set<String> set = 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;
}
/**
* 获取文字中的敏感词
*
* @param txt
* @param matchType
* @return
*/
public static Set<String> getSensitiveWord(String txt, int matchType) {
Set<String> sensitiveWordList = new HashSet<String>();
for (int i = 0; i < txt.length(); i++) {
int length = CheckSensitiveWord(txt, i, matchType); //判断是否包含敏感字符
if (length > 0) { //存在,加入list中
sensitiveWordList.add(txt.substring(i, i + length));
i = i + length - 1; //减1的原因，是因为for会自增
}
}
return sensitiveWordList;
}
/**
* 获取替换字符串
*
* @param replaceChar
* @param length
* @return
*/
private static String getReplaceChars(String replaceChar, int length) {
StringBuilder resultReplace = new StringBuilder(replaceChar);
for (int i = 1; i < length; i++) {
resultReplace.append(replaceChar);
}
return resultReplace.toString();
}
/**
* 刷新敏感树
*
* @return
*/
public static boolean refreshSensitiveMap() {
try {
//清空原有的敏感词汇树
sensitiveWordMap = null;
//初始化
initKeyWord(getPath);
return true;
}
catch (Exception e) {
e.printStackTrace();
return false;
}
}
}
2.2 相关工具类
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.net.URL;
/**
* 文件工具类
*
* @author wxz
* @version 1.0.0
* @date 2023/8/14
*/
public class FileUtils {
/**
* 从网络地址读取文件
*
* @param path 网络地址
* @return 读取后的文件
*/
public File readFileFromNet(String path) throws IOException {
File temporary = File.createTempFile("SensitiveWord", ".txt");
URL url = new URL(path);
InputStream inputStream = url.openStream();
FileUtils.copyInputStreamToFile(inputStream, temporary);
return temporary;
}
private static void copyInputStreamToFile(InputStream inputStream, File file) throws IOException {
try (FileOutputStream outputStream = new FileOutputStream(file)) {
int read;
byte[] bytes = new byte[1024];
while ((read = inputStream.read(bytes)) != -1) {
outputStream.write(bytes, 0, read);
}
}
}
}
2.3 使用
public static void main(String[] args) throws Exception {
String inputContext = "xxxxxxxxxx";
System.out.println("待检测语句字数：" + inputContext.length());
long beginTime = System.currentTimeMillis();
initKeyWord(getPath);
Set<String> sts = SensitiveWordUtil.getSensitiveWord(inputContext, 2);
System.out.println("敏感词内容:" + sts);
long endTime = System.currentTimeMillis();
System.out.println("总共消耗时间为：" + (endTime - beginTime) + "ms");
}
三、总结
除了DFA算法，还有其他的自动机算法，比如KMP算法、BM算法等。这些算法在不同的场景下有着不同的应用，需要根据具体情况来选择那种算法。
在实际应用中，DFA算法的效率收到状态数的影响：状态数越多，构建状态转移表的时间和空间就越大，因此需要在实际应用中进行优化。一种常见的优化方式是使用压缩转移表，将多个状态合并成一个状态，从而减少状态数。
总的来说，DFA算法是一种高效、快速的字符串匹配算法，在实际生活中有着广泛的应用。同时，需要注意算法的优化和选择，以达到预期的效果。