今天看到一篇介绍关于lucene使用有限状态机的文章,http://www.cnblogs.com/LBSer/p/4119841.html , 刚开始觉得跟trie树很像,后发现他们是有区别的:
trie树是一个树状结构,每个子节点只有一个父节点,而FST是一个网状结构,每个子节点,可以有多个父节点,所以FST更省空间。
还看到一篇文章,里面也提到了有限状态机的应用
https://www.cnblogs.com/dreamroute/p/8484457.html
luence中有限状态机的使用方式
String inputs={"abc","abd","acf","acg"}; //keys
long outputs={1,3,5,7}; //values
FST<Long> fst=new FST<>();
for(int i=0;i<inputs.length;i++)
{
fst.add(inputs[i],outputs[i])
}
//get
Long value=fst.get("abd"); //得到3
//迭代
BytesRefFSTEnum<Long> iterator=new BytesRefFSTEnum<>(fst);
while(iterator.next!=null){...}
这里还有一个java的例子
https://blog.csdn.net/smorker/article/details/79468489
看起来很简单, 如果更简化可以使用一个map来实现,就像lucene中使用的那样。
这里还有有效状态机的一个变种,DFA,全称为:Deterministic Finite Automaton,即确定有穷自动机。可以用来过滤敏感词
代码如下:
public class All {
private Map sensitiveWordMap = null;
private Map addSensitiveWordToHashMap(Set<String> wordSet) {
// 初始化敏感词容器,减少扩容操作
Map wordMap = new HashMap(wordSet.size());
for (String word : wordSet) {
Map nowMap = wordMap;
for (int i = 0; i < word.length(); i++) {
// 转换成char型
char keyChar = word.charAt(i);
// 获取
Object tempMap = nowMap.get(keyChar);
// 如果存在该key,直接赋值
if (tempMap != null) {
nowMap = (Map) tempMap;
}
// 不存在则,则构建一个map,同时将isEnd设置为0,因为他不是最后一个
else {
// 设置标志位
Map<String, String> newMap = new HashMap<String, String>();
newMap.put("isEnd", "0");
// 添加到集合
nowMap.put(keyChar, newMap);
nowMap = newMap;
}
// 最后一个
if (i == word.length() - 1) {
nowMap.put("isEnd", "1");
}
}
}
return wordMap;
}
public Set<String> getSensitiveWord(String txt, int matchType) {
Set<String> sensitiveWordList = new HashSet<String>();
for (int i = 0; i < txt.length(); i++) {
// 判断是否包含敏感字符
int length = CheckSensitiveWord(txt, i, matchType);
// 存在,加入list中
if (length > 0) {
sensitiveWordList.add(txt.substring(i, i + length));
// 减1的原因,是因为for会自增
i = i + length - 1;
}
}
return sensitiveWordList;
}
/**
* 替换敏感字字符
*
* @param txt
* @param matchType
* @param replaceChar
* @return
*/
public String replaceSensitiveWord(String txt, int matchType, String replaceChar) {
String resultTxt = txt;
// 获取所有的敏感词
Set<String> set = getSensitiveWord(txt, matchType);
Iterator<String> iterator = set.iterator();
String word = null;
String replaceString = null;
while (iterator.hasNext()) {
word = iterator.next();
replaceString = getReplaceChars(replaceChar, word.length());
resultTxt = resultTxt.replaceAll(word, replaceString);
}
return resultTxt;
}
/**
* 获取替换字符串
*
* @param replaceChar
* @param length
* @return
*/
private String getReplaceChars(String replaceChar, int length) {
String resultReplace = replaceChar;
for (int i = 1; i < length; i++) {
resultReplace += replaceChar;
}
return resultReplace;
}
/**
* 检查文字中是否包含敏感字符,检查规则如下:<br>
* 如果存在,则返回敏感词字符的长度,不存在返回0
*
* @param txt
* @param beginIndex
* @param matchType
* @return
*/
public int CheckSensitiveWord(String txt, int beginIndex, int matchType) {
// 敏感词结束标识位:用于敏感词只有1位的情况
boolean flag = false;
// 匹配标识数默认为0
int matchFlag = 0;
Map nowMap = this.sensitiveWordMap;
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"))) {
// 结束标志位为true
flag = true;
// 最小规则,直接返回,最大规则还需继续查找
if (1 == matchType) {
break;
}
}
}
// 不存在,直接返回
else {
break;
}
}
// 长度必须大于等于1,为词
if (matchFlag < 2 || !flag) {
matchFlag = 0;
}
return matchFlag;
}
private Set<String> readSensitiveWordFile() {
Set<String> wordSet = new HashSet<String>();
wordSet.add("×××");
wordSet.add("×××");
wordSet.add("王八");
wordSet.add("王八蛋");
return wordSet;
}
public static void main(String[] args) {
All all=new All();
all.sensitiveWordMap=all.addSensitiveWordToHashMap(all.readSensitiveWordFile());
String txt = "×××";
String hou = all.replaceSensitiveWord(txt, 1, "*");
System.out.println("替换前的文字为:" + txt);
System.out.println("替换后的文字为:" + hou);
}
}
感觉这个跟以前写的trie树非常相似,DFA 貌似也是一棵树,而不是网状。
原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/186201.html