FSA
FSA:确定无环有限状态接收机（Deterministric acyclic finite state acceptor, FSA） tire-tree就是这种
（构建工具http://examples.mikemccandless.com/fst.py）
FST
fst： Finite State Transducers（有限状态传感器）
（构建工具http://examples.mikemccandless.com/fst.py）
图中输入框里面 单词代表输入 后面的数字代表状态
用单词遍历这个有向无环图，初始状态是0，遇到的数字就累加上，到达终点节点的话就是对应的结果状态，如果没有到达终点代表咱们这里不支持这个输入
红色的边代表可优化存储的边 a large reduction of the FST size(实际实现中它的到达节点就是它的下一个节点,这个和实际存储实现由很大关系 )
加粗的边代表下个节点是终结（这个地方注意 黑色的有加粗的 红色的也有 0/1 g/1 这两条边都是加粗的）
构建方法：
输入的词是有序的（有序的构建的是最小树），添加词，再添加词（锁定部分边有些是不会动的边了 可以锁定了）调整未锁定的边，同时调整里面的数值让输出是目标值。再添加的时候有些边又可以锁定了，然后调整其他未锁定的。
输出状态可以是数字大于等于0的整数：每个路，经边的值加和。
输出状态可以是文本：每个路，经过的值得合并,下面以上图为例 Lucene 的fst为例进行说明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| 目的是使用1维的byte数组将状态变化全部保存起来
上图拉伸变形后
c a t
d e e p
o g s
e g g
镜像后得到（镜像是和插入顺序相关）
c d e g g
o g s
e e p
a t
从后到前依次填入到byte里面
fst的bytes字段
#一行10个byte 10进制
0 116 15 97 6 112 15 101 6 1
115 31 1 103 23 1 111 23 8 101
0 103 15 103 6 6 101 22 20 2
100 16 4 1 99 16
#转换arc为字母 标记状态
(0) [t] 15 [a] 6 [p] 15 [e] 6 <1>
[s] 31 <1> [g] 23 <1> [o] 23 {8} [e]
0 [g] 15 [g] 6 <6> [e] 22 {20} <2>
[d] 16 {4} <1> [c] 16
lucene 的arc 标记位8个bit定义了6个标记
BIT_FINAL_ARC = 1 << 0; 表示此边的目标节点是否为可接受状态
BIT_LAST_ARC = 1 << 1; 表示此边是节点的最后一条边，此边后面的内容就是下一个节点了。一个节点的所有边按顺序写入到bytes中，只有最后一条边被标记为BIT_LAST_ARC
BIT_TARGET_NEXT = 1 << 2; 表示此边应用了target_next优化，bytes中的下一个Node就是此边的目标节点
BIT_STOP_NODE = 1 << 3; 表示此边的目标节点是-1，已经遍历到了FST的末尾。
BIT_ARC_HAS_OUTPUT = 1 << 4; 表示此边有输出
BIT_ARC_HAS_FINAL_OUTPUT = 1 << 5; 则该ARC需要存储output信息。
BIT_MISSING_ARC = 1 << 6; 表示此边的目标节点有输出(final output)
flag=16，二进制为 00010000 。
第三位为BIT_TARGET_NEXT=0，因此有目标节点target；
第五位为BIT_ARC_HAS_OUTPUT=1，因此有输出符号output
flag=22, 二进制为 00010110 。
第二位BIT_LAST_ARC=1，说明这是节点的最后一条边；
第三位BIT_TARGET_NEXT=1，因此不需要存储target，其目标节点为下一个节点 往前找就可以了；
第五位为BIT_ARC_HAS_OUTPUT=1，因此有输出符号output
用的时候从后往前查找 比如查找 do
(0) 代表结束
[] 代表arc
<> 代表输出
{} 代表目标跳转
纯数字 代表flag |
应用场景：
1.搜索功能的sug模块： tire-tree和 fst均可作为底层数据结构，实现产品效果是一样的，查询效率相同都是 o(length(queryword))。但是fst的索引构建相较tire的复杂，tire的使用的内存较多，不能共享尾部。对于中文sug来转化为拼音和拼音前缀的Tire很浪费内存。【这个地方重点是压缩率】sug不用这些结构也是可以的（提前构建好用hashmap也可以）
2.Lucene的 term和 doc id的映射就是用的fst。
3.拼写检查
lucence fst使用示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| public static void main (String[] args ) throws Exception {
/*
参考文档
http://lucene.apache.org/core/8_2_0/core/org/apache/lucene/util/fst/package-summary.html
*/
String inputValues [] = {"cat", "deep", "do", "dog", "dogs", "egg", };
long outputValues [] = {1, 2, 3, 4, 5, 6};
PositiveIntOutputs outputs = PositiveIntOutputs. getSingleton();
Builder <Long > builder = new Builder <Long >(FST. INPUT_TYPE. BYTE1, outputs );
IntsRefBuilder scratchInts = new IntsRefBuilder ();
for (int i = 0; i < inputValues. length; i ++) {
BytesRef bb = new BytesRef (inputValues [i ]);
System. out. println(bb. toString());
builder. add(Util. toIntsRef(bb, scratchInts ), outputValues [i ]);
}
FST <Long > fst = builder. finish();
System. out. println(fst. toString());
//find-----------------------------------
BytesRef xx = new BytesRef ("cat");
System. out. println("-------------");
System. out. println("search result:"+Util. get(fst, xx ));
System. out. println("-------------");
System. out. println("foreach fst:");
//foreach-------------------------------
IntsRefFSTEnum <Long > fstEnum = new IntsRefFSTEnum <Long >(fst );
IntsRefFSTEnum. InputOutput<Long > inputOutput ;
BytesRefBuilder scratch = new BytesRefBuilder ();
while ((inputOutput = fstEnum. next()) != null) {
String input = Util. toBytesRef(inputOutput. input, scratch ). utf8ToString();
System. out. println(input + "\t" + inputOutput. output);
}
//sug-------------------------------------
System. out. println("-------------\nsug result:");
String forsug = "do";
BytesRef bytesRef = new BytesRef (forsug );
IntsRef input = Util. toIntsRef(bytesRef, new IntsRefBuilder ());
FST. Arc<Long > arc = fst. getFirstArc(new FST. Arc<Long >());
FST. BytesReader fstReader = fst. getBytesReader();
for (int i = 0; i < input. length; i ++) {
if (fst. findTargetArc(input. ints[input. offset + i ], arc, arc, fstReader ) == null) {
System. out. println("can not find ...");
return;
}
}
System. out. println(arc. toString());
//"do" find top 5 shortest path
Util. TopResults<Long > results = Util. shortestPaths(fst, arc, PositiveIntOutputs. getSingleton(). getNoOutput(), new Comparator <Long >() {
@Override
public int compare (Long o1, Long o2 ) {
return o1. compareTo(o2 );
}
}, 5, false);
BytesRefBuilder bytesRefBuilder = new BytesRefBuilder ();
for (Util. Result<Long > result : results ) {
IntsRef intsRef = result. input;
System. out. println( forsug + Util. toBytesRef(intsRef, bytesRefBuilder ). utf8ToString());
}
} |
其他字典树：
Array/List 使用二分法查找，不平衡
HashMap/TreeMap 性能高，内存消耗大，几乎是原始数据的三倍
Skip List 跳跃表，可快速查找词语，在lucene、redis、Hbase等均有实现。相对于TreeMap等结构，特别适合高并发场景（Skip List介绍）
Trie 适合英文词典，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存（数据结构之trie树）
Double Array Trie 适合做中文词典，内存占用小，很多分词工具均采用此种算法（An Implementation of Double-Array Trie ： https://linux.thai.net/~thep/datrie/datrie.html）
Ternary Search Tree 三叉树，每一个node有3个节点，兼具省空间和查询快的优点（https://en.wikipedia.org/wiki/Ternary_search_tree）
Finite State Transducers (FST) 一种有限状态转移机，Lucene 4有开源实现，并大量使用
FST的开源实现
1. OpenFst, an open-source library for FST operations.
2. Stuttgart Finite State Transducer Tools, another open-source FST toolkit
3. java FST Framework, an open-source java FST Framework capable of handling OpenFst text format.
4. Vcsn, an open-source platform (C++ & IPython) platform for weighted automata and rational expressions.
5. Finite State Morphology–The Book XFST/ LEXC, a description of Xerox’s implementation of finite-state transducers intended for linguistic applications.
6. FOMA, an open-source implementation of most of the capabilities of the Xerox XFST/ LEXC implementation.
【one more thing】
利用Lucene的开源工具实现了一个小的中文sug的demo：sugdemo
参考资料：
lucene字典实现原理——FST https://www.cnblogs.com/bonelee/p/6226185.html
关于Lucene的词典FST深入剖析 http://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/
https://blog.csdn.net/zx2011302580235/article/details/88594342
fst wiki https://en.wikipedia.org/wiki/Finite-state_transducer
