敏感词检测算法 - DFA

之前在系统中开发过一个敏感词检测的功能，最开始我很快完成了功能的设计开发：

敏感词库：存储所有敏感词的数据库表；
校验：查出所有敏感词集合，在循环中使用String.contains()方法在目标串中进行敏感词查找，找到后抛出异常提示；
预加载：敏感词集合不用每次都查数据库，可以提前加载缓存到内存，数据量也并不大。

但是使用暴力匹配算法未免简陋了点，于是便上网查找了下，果然还有更优的解决方案。这里我们先分析下String类的contains方法，即indexOf()方法的实现。

BF算法

BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。 -- 百度百科

直接看indexOf()方法的源码：

/**
 * source：来源串（输入的文本），target：模式串（敏感词）.
 */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }
		// 取敏感词的第一个字符
        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
	    	// 从输入文本中找到匹配敏感词第一个字符的字符
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
	    	// 匹配到了第一个字符，继续向后匹配
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end &&
		    		// 输入文本中的下一个字符是否与敏感词中的第二个字符相等，是则继续匹配
		    		// 否则终止匹配，从文本的下一个字符开始重新匹配
                     source[j] == target[k]; j++, k++);
              	
              	// j == end 说明上面这个循环走完了，即文本中完整的匹配到了敏感词，返回匹配的第一个字符处的index，代表成功
                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

记source的长度为N，target的长度为M，该算法在最坏的情况下，单个敏感词匹配需要的比较次数为M * (N - M + 1)，表示target在source的最后一段才匹配到，即时间复杂度为O(M * N)，而要检测整个敏感词库（词库总数记为S）复杂度就变为O(S * M * N)，效率太低。