学习笔记——搞懂FST数据结构

发布时间：2022-08-18 18:11

数据结构FST简述

FST简述及它的查询过程

从Lucence源码中看FST的结构

查看builder类(package org.apache.lucene.util.fst)

查看BlockTreeTermsWriter类(packageorg.apache.lucene.codecs.blocktree)

FST存储到文件中的存储结构(TermIndex词项索引和TermDictionary词项字典)

FST构建(读取和写入数据)

通过图解一步步搞清楚结点的添加过程。

读取FST的字符串.

首先声明图片数据来源:b站马士兵教育。

luncence源码百度云:

链接：https://pan.baidu.com/s/12EQtJ_t-P3-P_CJnHIfnEw
提取码：abcd

数据结构FST简述

了解一下trie前缀树：复用所有前缀

FSM(Finite State Machines)有限状态机: 表示有限个状态集合以及这些状态之间转移和动作的数学模型。其中一个状态被标记为开始状态，0个或更多的状态被标记为final状态

FSA：有限状态接收机

确定性:在任何给定状态下，对于任何输入，最多只能遍历一个transtion
非循环:不可能重复遍历同一个状态
Final唯一性:当且仅当有限状态机在输入序列的末尾处于最终状态时，才接受特定的输入序列
以上例子，如果输入‘wl’会怎样？其实就是可以搜索到的了。因为l指向的节点3已经是final节点了。为解决这样的问题，引出FST

FST简述及它的查询过程

FST:有限状态转化机
FST最重要的功能是可以实现key到value的映射，相当于HashMap。FST的查询速度比hashMap慢一点，但是内存消耗比hashMap小很多。FST在lucene大量使用:倒排索引的存储，同义词词典的存储，搜索关键字建议等等。
对于es来说，它是基于lucence开发，底层的数据结构使用的就是fst,它的主要优点:

查询快
极致压缩空间占用
特性:
确定性:在任何给定状态下，对于任何输入，最多只能遍历一个transtion
非循环:不可能重复遍历同一个状态
transducer: 转化器有相关的值(payload),final节点会输出一个值
比起前面的前缀树以及FSA，在存储的时候多了一个value值。
考虑以下输入字符:

此时，再输入wl试试？尽管节点3是final节点,但是由于值对不上，所以不会搜索成功的。

从Lucence源码中看FST的结构

查看builder类(package org.apache.lucene.util.fst)

节点模型:node

考虑需要输入这样一组数据

由于按照字典序排序，输入abd的时候，由于此时系统不知道后面是否还存在abde,abdc类似的数据，所以此时输入的abd就是unCompliledNode

当输入abe的时候，已经可以确定后面不会有abd这些数据了(字典序),但是无法确定ab前缀还是否存在,直到输入ac为止才确认不会有ab前缀了。此时字符’d’被移除出frontier数组，把它冻结起来 -freezeTail

描述边，也就是出度的类是Arc

label:存放那个输入的字符作为Key
output:存放对应的值也就是Value
target:简单理解为存放偏移量,如果arc描述的字符不是最后一个字符的时候，就会有这么一个偏移量。
flags:其实就是起始值，通过位运算(通用最小化算法)得来.

查看BlockTreeTermsWriter类(packageorg.apache.lucene.codecs.blocktree)

PendingEntry—PendingBlock --PendingTerm
通过输入的字符，一般的是Term，满足某种条件则会被聚合成Block

Block——根据给的阈值(min24,max48)划分成Block或者Term
简单理解:若是子节点少于24，则仍然为单独的PedingTerm,若是大于等于24，则会被聚合成一个PendingBlock.如果这个PendingBlock大于48，则会被分成多个FloorBlock

通过构建过程来理解:
1.输入abd,abe，此时还都是正常的情况。(abd和abe都是term)

2.输入abfi,abfj,abfk，此时可以看到f已经有三个出度k I j了，初步满足聚合成Block的条件

此时还都是term,没有聚合成block,虽然已经满足了条件给出的3个。但是由于输入项还没确定完.所以还不能聚合起来。

3输入abgl---->聚合成Block
由于此时已经确定f已经不会做修改了，此时由于f有三个出度，所以I j k可以聚合成pedingBlock

4.继续输入abgm,abgn,abgo,abgp,abgp,abgq,abgr。此时g已经有七个出度了！！但是没有聚合成Block

等到结束g出度的输入的时候，才会发生聚合block
5.输入abh,此时聚合成g的block,它底下还有两个floorblock

FST存储到文件中的存储结构(TermIndex词项索引和TermDictionary词项字典)

.tip: 存放Term-Index

.tim:存放Term-Dictonary

Term-index里面存放的FSTindex存放Block的前缀记录，末尾指向block..这些block具体存放在.tim文件也就是term Dictonary里面。

block具体存放的是啥?

BlockHeader:

Suffix:

states:

metaLength:

再来看看FST-Index和block更详细的内容

以这样一个词项字典

还是这张图

构建FST-Index

其中flag是标志位，代表着一个block的开始.

字符’a’以及’c’代表着以’a’开始的block和’c’开始的block

数字12，36，64等代表着在数组中的起始位置.

逐个看看:

这一块对应的是这个a有两个子节点,所以EntryCount为2

这一块对应的是这个

EntryCount为5，代表五个后缀节点

Suffix里面包含了a,b,c,d,e五个，他们所代表的属性分别是PendingTerm, PendingTerm, PendingBlock,FloorBlock, PendingTerm

这一块对应的是这个

suffix:是a,b,c三个后缀

这块对应的是这个最多后缀的d节点:

以上是FST-Index以及Block的映射情况。

FST构建(读取和写入数据)

上面的那些都是一些概念定义，对上面的知识点有了大概的认识之后，就可以真正搞懂FST这个牛x的数据结构是怎么读写数据的了。

FST的写数据过程最好是结合它的读的过程去理解，不然会感觉很懵逼。

首先，FST里面包含了两个重要的属性:

Node和Arc,分别代表结点和出度(边)

Node作为节点，其实它在这里主要起到了描述节点状态的作用，描述节点是否已经经过处理。它是一个基类，子类有UncomliedNode和CompliedNode

Arc是出度，它里面算是大有文章了。

四个属性:

label:存放输入的字符，实际存的是ASCLL码二进制

output:存放输出值,还记得前面说的FST类似于哈希表吗，可以理解为存放k-v中的v值

以上两个属性比较好理解，难点重点是下面两个:

target:存放下标值，如果当前出度指向的字符不是输入值的最后一个时，会存储index值来指向下一个字符的下标。事实上target这个属性就是在flags属性里面的BIT_TARGET_NEXT状态不存在时才会出现的。

flags:

这里面用到比特位来存储，主要作用应该是压缩占用空间。利用标志位在读的时候可以解码。想想一个数字可以存放这么多状态，有点类似于以前学计组时接触过的flag标志位。

flags里面有六个状态，除了BIT_TARGET_NEXT不好理解，其它应该比较简单。这里我也不赘述。

BIT_TARGET_NEXT这个状态一开始我去查百度，大多说的都是TARGET_NEX优化，但是都没有说这个优化是什么。这里我简单理解总结一下就是，当这个状态激活时，我们在读到这个字符的时候不需要发生跳转，只需要继续往下遍历即可。所以当这个状态激活的时候，上面说到的Target属性才会不存在。只有当这个状态没有激活的时候，我们需要在读完这个之后跳转到另一个字符，而这时target才会给出一个index值让我们去跳转。

再看看FST的源码:

这里是它的六个属性flags

这是它的构建过程(节选)

如果到这个地方还是无法理解，那也没事，后面在写到FST的构建(写)以及读的过程就会好理解很多。

下面再一步步地构建FST，通过观察构建过程和结合读过程搞懂这玩意。

初始化

new Builder()。初始化BytesStore bytes.写入一个0，用来表示FST的结束。因为读取的时候是反向读取，（先进后出）。

初始化一个长度为10的UnCompliedNode[ ] frontier

开始输入数据Builder.add方法

public void add(IntsRef input, T output)

这个方法主要干四件事情:

2.1，计算当前字符串和上一个字符串的公共前缀

2.2，调用freezeTail方法，从尾部一直到公共前缀的节点，将已确定的状态节点冻结

2.3，将当前字符串形成状态节点加入到frontier数组中

2.4，调整每条边的输出值

看看源码:

public void add(IntsRef input, T output) throws IOException {
		//2.1，计算当前字符串和上一个字符串的公共前缀
        if (output.equals(this.NO_OUTPUT)) {
            output = this.NO_OUTPUT;
        }

        assert this.lastInput.length() == 0 || input.compareTo(this.lastInput.get()) >= 0 : "inputs are added out of order lastInput=" + this.lastInput.get() + " vs input=" + input;

        assert this.validOutput(output);

        if (input.length == 0) {
            ++this.frontier[0].inputCount;
            this.frontier[0].isFinal = true;
            this.fst.setEmptyOutput(output);
        } else {
            int pos1 = 0;
            int pos2 = input.offset;
            int pos1Stop = Math.min(this.lastInput.length(), input.length);

            while(true) {
                ++this.frontier[pos1].inputCount;
                if (pos1 >= pos1Stop || this.lastInput.intAt(pos1) != input.ints[pos2]) {
                    int prefixLenPlus1 = pos1 + 1;
                    int idx;
                    if (this.frontier.length < input.length + 1) {
                        Builder.UnCompiledNode[] next = (Builder.UnCompiledNode[])ArrayUtil.grow(this.frontier, input.length + 1);

                        for(idx = this.frontier.length; idx < next.length; ++idx) {
                            next[idx] = new Builder.UnCompiledNode(this, idx);
                        }

                        this.frontier = next;
                    }

				

					//2.2，调用freezeTail方法，从尾部一直到公共前缀的节点，将已确定的状态节点冻结
                    this.freezeTail(prefixLenPlus1);

					//2.3，将当前字符串形成状态节点加入到frontier数组中
                    for(int idx = prefixLenPlus1; idx <= input.length; ++idx) {
                        this.frontier[idx - 1].addArc(input.ints[input.offset + idx - 1], this.frontier[idx]);
                        ++this.frontier[idx].inputCount;
                    }

                    Builder.UnCompiledNode lastNode = this.frontier[input.length];
                    if (this.lastInput.length() != input.length || prefixLenPlus1 != input.length + 1) {
                        lastNode.isFinal = true;
                        lastNode.output = this.NO_OUTPUT;
                    }

					//2.4，调整每条边的输出值
                    for(idx = 1; idx < prefixLenPlus1; ++idx) {
                        Builder.UnCompiledNode node = this.frontier[idx];
                        Builder.UnCompiledNode parentNode = this.frontier[idx - 1];
                        T lastOutput = parentNode.getLastOutput(input.ints[input.offset + idx - 1]);

                        assert this.validOutput(lastOutput);

                        Object commonOutputPrefix;
                        if (lastOutput != this.NO_OUTPUT) {
                            commonOutputPrefix = this.fst.outputs.common(output, lastOutput);

                            assert this.validOutput(commonOutputPrefix);

                            T wordSuffix = this.fst.outputs.subtract(lastOutput, commonOutputPrefix);

                            assert this.validOutput(wordSuffix);

                            parentNode.setLastOutput(input.ints[input.offset + idx - 1], commonOutputPrefix);
                            node.prependOutput(wordSuffix);
                        } else {
                            commonOutputPrefix = this.NO_OUTPUT;
                        }

                        output = this.fst.outputs.subtract(output, commonOutputPrefix);

                        assert this.validOutput(output);
                    }

                    if (this.lastInput.length() == input.length && prefixLenPlus1 == 1 + input.length) {
                        lastNode.output = this.fst.outputs.merge(lastNode.output, output);
                    } else {
                        this.frontier[prefixLenPlus1 - 1].setLastOutput(input.ints[input.offset + prefixLenPlus1 - 1], output);
                    }

                    this.lastInput.copyInts(input);
                    return;
                }

                ++pos1;
                ++pos2;
            }
        }
}