DFA算法

DFA全称为：Deterministic Finite Automaton,即确定有穷自动机。其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。

简单点说就是，它是通过event和当前的state得到下一个state，即event+state=nextstate。理解为系统中有多个节点，通过传递进入的event，来确定走哪个路由至另一个节点，而节点是有限的。

关键字提取的DFA算法

以“工人阶级”和“工农联盟”两个关键词来进行描述，首先构建关键词库，这个词二叉树构造为：

构造成HashMap：

{
    "工": {
        "isEnd": false,
        "人": {
            "isEnd": false,
            "阶": {
                "isEnd": false,
                "级": {
                    "isEnd": true,
                    "label": "工人阶级"
                }
            }
        },
        "农": {
            "isEnd": false,
            "联": {
                "isEnd": false,
                "盟": {
                    "isEnd": true,
                    "label": "工农联盟"
                }
            }
        }
    }
}

代码实现

构造关键词

/**
 * 标签集进行哈希映射
 *
 * @param labels
 * @return
 */
public static Map<String, Map> labelsToHashMap(Set<String> labels) {
    Map<String, Map> labelHashMap = new HashMap<String, Map>(labels.size());

    // 当前映射
    Map currentMap = null;

    // 标签名称
    String label;

    // 循环标签集
    Iterator<String> labelIterator = labels.iterator();
    while (labelIterator.hasNext()) {
        label = labelIterator.next();
        currentMap = labelHashMap;
        // 循环关键字
        for (int i = 0; i < label.length(); i++) {
            // 关键词的每一个单字
            char word = label.charAt(i);

            // 关键字的映射是否存在
            boolean exist = currentMap.containsKey(word);
            // 如果关键字不存在映射中，将关键字存在映射中
            if (!exist) {
                Map newWordMap = new HashMap<String, Boolean>();
                newWordMap.put("isEnd", false); // 不是最后一个元素
                currentMap.put(word, newWordMap);
                currentMap = newWordMap;
            }
            // 如果关键字存在映射中，获取该映射
            else {
                currentMap = (Map) currentMap.get(word);
            }

            // 如果该关键字是该关键词的最后一个字，标记为关键词结束
            if (i == label.length() - 1) {
                currentMap.put("isEnd", true);
                currentMap.put("label", label);
            }
        }
    }

    return labelHashMap;
}

匹配关键词

/**
 * 解析文本内容，抽取标签
 *
 * @param content
 * @return
 */
public static Map<String, Integer> parse(String content, Map<String, Map> labelMap) {

    Map<String, Integer> labels = new HashMap<String, Integer>();

    // 按字符循环文本内容
    for (int i = 0; i < content.length(); i++) {
        // 文本字符
        char word = content.charAt(i);
        // 关键字是否存在
        boolean exist = labelMap.containsKey(word);
        // 关键字存在
        if (exist) {
            // 字符指针
            int j = i;
            // 获得关键字映射
            Map map = labelMap.get(word);
            // 关键词是否结束
            boolean isEnd = (boolean) map.get("isEnd");
            // 关键词词结束
            if (isEnd) {
                // 获得关键词计数
                int num = labels.getOrDefault(map.get("label"), 0);
                // 更新关键词计数
                labels.put((String) map.get("label"), num + 1);
            }
            // 关键词未结束
            while (!isEnd || map.size() > 2) {
                // 获得下一个文本字符
                char nextWord = ' ';
                if (++j < content.length()){
                    nextWord = content.charAt(j);
                }
                // 下一个文本字符是否是关键词
                boolean existNext = map.containsKey(nextWord);
                // 下一个字是关键字
                if (existNext) {
                    // 获得下一个关键字的映射
                    map = (Map) map.get(nextWord);
                    isEnd = (boolean) map.get("isEnd");
                    if (isEnd) {
                        // 获得关键词计数
                        int num = labels.getOrDefault(map.get("label"), 0);
                        // 更新关键词计数
                        labels.put((String) map.get("label"), num + 1);
                    }
                }
                // 下一个字不是关键字
                else {
                    break;
                }
            }
            // end of while loop
        }
        // 关键字不存在
        else {
            continue;
        }
    }
    return labels;
}