DFA的敏感词过滤实现

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来进行一个实现:

1. 先是一个构造我们的状态集合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;
}

这一部分的代码就是遍历我们的文件，然后逐行读取。

2. 下面是一个过滤的代码:

  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