FST & tire-tree 及应用场景

by ·0评论

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

发表评论

邮箱地址不会被公开。 必填项已用*标注