DFA在wiki上面的解释是“确定有限状态自动机或确定有限自动机(deterministic finite automaton， DFA)是一个能实现状态转移的自动机”。这里我直白的一个自我理解就是通过一个事先维护好的状态集，自动进行一个判断转移到下一个状态。
状态转移
通过上面的图，我们来解释一个下大致的算法思路:
- Q：是一个所有的状态的集合(包含了状态A1,A2,A3,B1,B2....D3)
- I : 是我们输入数据
- transfer: 是我们通过I输入的数据，获得到起始状态之后，进行转移到下一个状态的工具。
所以，大致的思路，就是通过输入的数据I([a,b,c,d])然后进行对Q状态集查询起始的状态，由I[0] = a开始作为一个入参去Q中寻找。假设找到了A1，然后，这个时候，我们的入参I还没操作完其他数据，这个时候，我们就要将状态转移到A1的下一个状态并且和我们的I[1]进行判断，看看是否能够成功的转移到A2上。
- I[0] -> A1
- I[1] -> A2
以此类推，当我们的状态链路不能往下的时候，标明了我们的输入I中，存在一个A1....AN的这么一个状态链路(在我们进行一个敏感词的时候，这个链路就可以理解为整个敏感词)。
那么，通过上面的流程，我们把它引入到我们的敏感词的实现上:
- 首先，我们的敏感词，一个敏感词，就可以理解为一个状态的链路，然后每个节点的状态就代表为一个字。
- I 这里就代表我们输入要进行判断是否包含敏感词的目标语句
- A1，B1， C1， D1，这些都是表示一个敏感词的开始的第一个字。
- 然后我们循环从I的第一次字开始判断是否在A1到D1中存在这样一个状态
- 如果存在，就继续往下，查询下一个状态是否在链路上，如果不在链路上，这个时候就要及时的跳出，去头部开始重新的查找。
具体的代码，我们通过Java的HashMap来进行一个实现:
- 先是一个构造我们的状态集合Q的代码:
private static void init(Set<Sensitive> sensitiveWordSet) {
Iterator<Sensitive> iterator = sensitiveWordSet.iterator();
while (iterator.hasNext()) {
Sensitive sensitive = iterator.next();
char[] text = sensitive.getText().toCharArray();
Map tempMap = hashMap;
int index = 1; // 标明是第几个文字，用于遮掩敏感词的时候，进行一个回溯.
for (int i=0; i<text.length; i++) {
char item = text[i];
if (!tempMap.containsKey(item)) {
DFANode dfaNode = new DFANode();
dfaNode.setIndex(index);
dfaNode.setSub(new HashMap());
// 用于判断是否是最终文字
dfaNode.setEnd(i == (text.length-1)); // end?
tempMap.put(item, dfaNode);
tempMap = dfaNode.getSub();
} else {
DFANode subNode = (DFANode) tempMap.get(item);
tempMap = subNode.getSub();
}
index++;
}
}
}
private static void loadFile() throws IOException {
File file = new File(
DFATextFilter.class.getClassLoader().getResource("sensitive.txt").getFile());
List<String> list = Files.readLines(file, Charset.forName("utf-8"));
Set<Sensitive> sensitiveWordSet = new HashSet<>(40);
list.forEach(item -> {
sensitiveWordSet.add(Sensitive.builder().text(item).build());
});
init(sensitiveWordSet);
}
@Data
@Builder
public class Sensitive {
private String text;
}
@Data
public class DFANode {
private boolean end;
private int index; // 标明单单在敏感字中的位置
private Map sub;
}
这一部分的代码就是遍历我们的文件，然后逐行读取。
- 下面是一个过滤的代码:
private FilterResult check(String str, boolean mask) {
Map tempCheckMap = hashMap;
boolean exist = false;
char[] chars = str.toCharArray();
for (int i=0; i<chars.length; i++) {
if (tempCheckMap.containsKey(chars[i])) {
DFANode subNode = (DFANode) tempCheckMap.get(chars[i]);
if (subNode.isEnd()) {
// 遮掩敏感词
if (mask) {
int length = subNode.getIndex();
for (int j=0; j<length; j++) {
chars[i-j] = 'X';
}
}
exist = true;
str = String.valueOf(chars);
} else {
tempCheckMap = subNode.getSub();
}
} else {
// 从链路跳出从头开始，或者是第一步
tempCheckMap = hashMap;
if (tempCheckMap.containsKey(chars[i])) {
DFANode subNode = (DFANode) tempCheckMap.get(chars[i]);
if (subNode.isEnd()) {
if (mask) {
int length = subNode.getIndex();
for (int j=0; j<length; j++) {
chars[i-j] = 'X';
}
}
exist = true;
str = String.valueOf(chars);
tempCheckMap = hashMap;
} else {
tempCheckMap = subNode.getSub();
}
}
}
}
return FilterResult.builder().sensitive(exist).str(str).build();
}
@Data
@ToString
@Builder
public class FilterResult {
private String str;
private boolean sensitive;
}
整体的代码实现还是比较简单，这里也就简单的提供一个思路。完整的代码查看链接: https://github.com/songshuangkk/DFA-Filter/tree/master
