关键词匹配
检查一段文本中是否包含给定的关键词。
如检查一篇文章的文本是否含有“浙江省”、“江苏省”、“安徽省”，可使用的方法有:
第一种是关键词遍历，然后检查文本中是否含有该关键词, 伪代码如下：
for (keyword in [“日本人”、“日本鬼子”、“中国人”]) {
if (text.indexOf(keyword) != -1) {
return true;
}
}
return false;
第二种可以使用正则表达式
Pattern pattern = Pattern.compile("日本人|日本鬼子|中国人");
Matcher matcher = pattern.matcher(text);
return matcher.matches();
这两种方法都当需要匹配的关键词数量越来越大的时候，效率会越来越低。
DFA算法
DFA（(Deterministic Finite automation)）确定性的有穷状态自动机: 从一个状态输入一个字符集合能到达下一个确定的状态。如图:
dfa_1.png
如上图当AB状态输入a得到状态aB,状态aB输入b得到状态ab; 状态AB输入b得到状态Ab,状态Ab输入a得到状态ab。
利用DFA匹配关键词
上面开始的几个关键词匹配可以用下图来表示:
dfa_2.png
0是开始状态，输入日、本、人会最终到达结束状态5，输入日、本、鬼、子最终到达结束状态8，输入中、国、人到达结束状态7。
以上的状态图输入字符类似树形结构，空心状态表示未结束状态(isEnd=false), 蓝色环形状态表示结束状态(isEnd=true)。用HashMap维护这个字典关系.
{
"日": {
"本": {
"人": {
"isEnd": "1"
},
"鬼": {
"子": {
"isEnd": "1"
},
"isEnd": "0"
},
"isEnd": "0"
},
"isEnd": "0"
},
"中": {
"国": {
"人": {
"isEnd": "1"
},
"isEnd": "0"
},
"isEnd": "0"
}
}
生成字典库树形结构的java代码如下:
/**
* 生成关键词字典库
* @param words
* @return
*/
private Map<String, Object> handleToMap(Collection<String> words) {
if (words == null) {
return null;
}
// map初始长度words.size()，整个字典库的入口字数(小于words.size()，因为不同的词可能会有相同的首字)
Map<String, Object> map = new HashMap<>(words.size());
// 遍历过程中当前层次的数据
Map<String, Object> curMap = null;
Iterator<String> iterator = words.iterator();
while (iterator.hasNext()) {
String word = iterator.next();
curMap = map;
int len = word.length();
for (int i =0; i < len; i++) {
// 遍历每个词的字
String key = String.valueOf(word.charAt(i));
// 当前字在当前层是否存在, 不存在则新建, 当前层数据指向下一个节点, 继续判断是否存在数据
Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key);
if (wordMap == null) {
// 每个节点存在两个数据: 下一个节点和isEnd(是否结束标志)
wordMap = new HashMap<>(2);
wordMap.put("isEnd", "0");
curMap.put(key, wordMap);
}
curMap = wordMap;
// 如果当前字是词的最后一个字，则将isEnd标志置1
if (i == len -1) {
curMap.put("isEnd", "1");
}
}
}
return map;
}
匹配文本的代码如下:
/**
* 搜索文本中某个文字是否匹配关键词
* @param text
* @param beginIndex
* @return
*/
private int checkWord(String text, int beginIndex) {
if (dictionaryMap == null) {
throw new RuntimeException("字典不能为空");
}
boolean isEnd = false;
int wordLength = 0;
Map<String, Object> curMap = dictionaryMap;
int len = text.length();
// 从文本的第beginIndex开始匹配
for (int i = beginIndex; i < len; i++) {
String key = String.valueOf(text.charAt(i));
// 获取当前key的下一个节点
curMap = (Map<String, Object>) curMap.get(key);
if (curMap == null) {
break;
} else {
wordLength ++;
if ("1".equals(curMap.get("isEnd"))) {
isEnd = true;
}
}
}
if (!isEnd) {
wordLength = 0;
}
return wordLength;
}
/**
* 获取匹配的关键词和命中次数
* @param text
* @return
*/
public Map<String, Integer> matchWords(String text) {
Map<String, Integer> wordMap = new HashMap<>();
int len = text.length();
for (int i = 0; i < len; i++) {
int wordLength = checkWord(text, i);
if (wordLength > 0) {
String word = text.substring(i, i + wordLength);
// 添加关键词匹配次数
if (wordMap.containsKey(word)) {
wordMap.put(word, wordMap.get(word) + 1);
} else {
wordMap.put(word, 1);
}
i += wordLength - 1;
}
}
return wordMap;
}
最后附上测试用例:
public class KeywordMatcherTest {
@Test
public void matchWords() {
String WHITE_AREAS = "北京市,天津市,上海市,重庆市,河北省,山西省,辽宁省,吉林省,黑龙江省,江苏省,安徽省,福建省,江西省,山东省,河南省,湖北省,湖南省,广东省,海南省,陕西省,石家庄,太原,沈阳,长春,哈尔冰,南京,合肥,福州,济南,郑州,武汉,长沙,广州,贵阳,西安,兰州,银川,南宁,杭州,成都,浙江省,湖州";
List<String> keywords = Arrays.asList(WHITE_AREAS.split(","));
KeyWordMatcher keyWordMatcher = new KeyWordMatcher(keywords);
assertThat(MapUtils.isNotEmpty(keyWordMatcher.getDictionaryMap()), is(true));
assertThat(keyWordMatcher.getDictionaryMap().size() <= keywords.size(), is(true));
assertThat(keyWordMatcher.matchWords("浙江省湖州市吴兴区").size() == 2, is(true));
}
}
