有限状态机FST
今天看到一篇介绍关于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 fst=new FST<>();
for(int i=0;i 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 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 newMap = new HashMap();
newMap.put("isEnd", "0");
// 添加到集合
nowMap.put(keyChar, newMap);
nowMap = newMap;
}
// 最后一个
if (i == word.length() - 1) {
nowMap.put("isEnd", "1");
}
}
}
return wordMap;
}
public Set getSensitiveWord(String txt, int matchType) {
Set sensitiveWordList = new HashSet();
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 set = getSensitiveWord(txt, matchType);
Iterator 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;
}
/**
* 检查文字中是否包含敏感字符，检查规则如下：
* 如果存在，则返回敏感词字符的长度，不存在返回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 readSensitiveWordFile() {
Set wordSet = new HashSet();
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 貌似也是一棵树，而不是网状。
网页名称：有限状态机FST
链接URL：http://6mz.cn/article/gcjogo.html