文章目录一、前言二、什么是DFA算法三、DFA算法优化关键词过滤四、java代码实现五、总结
一、前言
有一个关键字库。 在这种情况下，必须搜索文本中是否有词典关键字。 我该怎么实现？
tsdls回答：将所有关键字放入一个set集合中，然后遍历集合，逐一匹配该文本，将存在的关键字放入另一个集合中。 实现代码如下：
public class test 131 { publicstaticvoidmain (string [ ] args ) setstringwordset=newhashsetstring )； wordSet.add (产品经理)； 产品总监wordSet.add； wordSet.add (程序员)； String content='产品经理的工作内容包括需求收集、需求分析、需求落地、项目跟踪、项目上线、数据跟踪和业务人员培训，协助开展运营、销售、客户服务等； setstringhavewordset=newhashsetstring (； for (字符串word : words et ) if (content.contains (word ) ) havewordset.add (word )； } system.out.println (havewordset )； (//[产品经理]想法简单易懂，但有成千上万个关键词时，性能会急剧下降。 分析时间复杂度，扫描关键字为o(n )，从字符段落检索的时间复杂度也为o(n ) )，加起来为o ) n^2)。
还有其他更好的解决方法吗？ 有！ 是DFA算法！
二、DFA算法DFA即Deterministic Finite Automaton是什么，翻译过来就是确定性有限自动机简单的原理，在有限的集合中，其中的要素有两种状态，终止和继续(0.00
三、DFA算法优化关键词滤波应用DFA算法原理。 例如，有几个关键词。 构建产品经理、产品总监、程序员和DFA算法容器如下：
看起来像树。 现在判断单词是否在词典里。 例如，测试者只要搜索是否有以“测试”字开头的“树”，就可以马上判断出没有测试者这个词。 例如，如果搜索“产品经理”，则可以找到以“产”字开头的“树”，然后直接排除“程序员”中的该“树”。 这大大缩小了范围。
计算时间复杂度，如果从词典中匹配关键字，时间复杂度为o(1)，遍历字符段落仍然与字符的数量有关，时间复杂度最差)文本中没有一个关键字(o ) n ) 利用DFA实现关键字过滤的优化点是，检索的时间复杂度不受关键字数量的增加的影响，而只与要检索的字符的长度有关。
四、java代码实现分析数据结构，每个字符保存一个状态，可以用map实现。 如果状态没有结束却保存下一个字符的指针，也可以在map中实现。 这就是映射集映射。 如下所示，一个大map有两个key、程和产，value值又是map集map。
{程={isEnd=0，序={isEnd=0，员={isEnd=1} }，产={isEnd=0，品={isEnd=0，总={isEnd=0，鉴={ isend }
public class test 131 (publicstaticvoidmain (string [ ] args ) { String content=)产品经理的工作内容包括需求收集、需求分析、需求落地、项目setstringwordset=newhashsetstring (； wordSet.add (产品经理)； 产品总监wordSet.add； wordSet.add (程序员)； init(wordset )； system.out.println (' word map=' m _ kwwordmap )； setstringhavewords=getword (内容，MIN_MATCH_TYPE； system.out.println (have words=' have words )； }/***DFA关键字容器初始化* @par
am words */ @SuppressWarnings({ "rawtypes", "unchecked" }) public static void init(Set<String> words) { // 预先 设置初始容量，以免扩容影响性能。 Map wordMap = new HashMap(words.size()); for (String word : words) { Map nowMap = wordMap; for (int i = 0; i < word.length(); i++) { // 转换成char型 char keyChar = word.charAt(i); // 判断是否已经有一个map树，只有在一个词的首字符有用 Object tempMap = nowMap.get(keyChar); if (tempMap != null) { // 存在，则共享一个map树根 nowMap = (Map) tempMap; } // 不存在则构建一个map树， else { // 设置状态位 Map<String, String> newMap = new HashMap<String, String>(); // 判断是设置 0还是1 newMap.put("isEnd", i == word.length() - 1 ? "1" : "0"); // 给keyChar该字符设置状态位 nowMap.put(keyChar, newMap); // 将状态位map赋值给nowMap，表示下一个字符的指针和状态位在同一个map里。 nowMap = newMap; } } } // 上面始终修改的是nowMap，最后形成的是wordMap，原因是，预先wordMap赋值给了nowMap， // 使得wordMap和nowMap中的map地址值共享，更新了nowMap中的map就是更新了wordMap。 m_kwWordMap = wordMap; } /** * 检索关键词 * @param txt 被检索的文本 * @param beginIndex 被检索文本的开始位置 * @param matchType 匹配类型 * @return 返回检索到的关键词长度，用于从文本中截取 */ public static int checkWord(String txt, int beginIndex, int matchType) { // 匹配标识数默认为0 Map nowMap = m_kwWordMap; int matchFlag = 0; int matchMaxFlag = 0; for (int i = beginIndex; i < txt.length(); i++) { char word = txt.charAt(i); // 获取指定key nowMap = (Map) nowMap.get(word); // 存在，则判断是否为最后一个 if (nowMap != null) { // 找到相应key，匹配标识+1 matchFlag++; // 如果为最后一个匹配规则,结束循环，返回匹配标识数 if ("1".equals(nowMap.get("isEnd"))) { // 将matchFlag赋值给matchMaxFlag，为的是， // 后面要是继续按最大匹配原则匹配时，匹配不到则按最小匹配原则的结果为准。 matchMaxFlag = matchFlag; // 最小规则，直接返回,最大规则还需继续查找 if (MIN_MATCH_TYPE == matchType) { break; } } } // 不存在，直接返回 else { break; } } return matchMaxFlag; } /** * 从文本中检索出关键词 * @param txt 被检索的文本 * @param matchType 匹配类型 * @return */ public static Set<String> getWord(String txt, int matchType) { Set<String> set = new HashSet<String>(); for (int i = 0; i < txt.length(); i++) { // 判断是否包含关键词，length > 0 有，且是关键词长度 int length = checkWord(txt, i, matchType); // 存在,加入set中 if (length > 0) { // 从原文中截取 并放入set set.add(txt.substring(i, i + length)); // 减1的原因，因为for会自增 i = i + length - 1; } } return set; } private static Map m_kwWordMap = null; // 最小匹配原则,如果关键词中有中国和中国人，文本内容为“我是中国人”，最小匹配原则匹配出中国 public static final int MIN_MATCH_TYPE = 1; // 最大匹配原则,如果关键词中有中国和中国人，文本内容为“我是中国人”，最大匹配原则匹配出中国人 public static final int MAX_MATCH_TYPE = 2;}// wordMap={程={isEnd=0, 序={员={isEnd=1}, isEnd=0}}, 产={品={总={监={isEnd=1}, isEnd=0}, isEnd=0, 经={理={isEnd=1}, isEnd=0}}, isEnd=0}}// haveWords=[产品经理] 五、总结 DFA算法利用map套map的原理，极大程度上优化了检索性能，时间复杂度为小于等于O(n)，n是被检索文本的长度。DFA实现的关键词过滤，性能不再受限于关键词的数量，只与被检索的文本长度有关。DFA关键词过滤，是精准过滤，无法实现模糊过滤，如我是*人，*匹配单个字符，%匹配多个字符。参考：https://www.cnblogs.com/twoheads/p/11349541.html 需要注意该文章中checkWord函数最大匹配原则时是有bug的，本人的示例已加matchMaxFlag更正。
PS: 如若文章中有错误理解，欢迎批评指正，同时非常期待你的评论、点赞和收藏。我是phdmf，愿与你共同进步！