FST(一)

FST(Finite State Transducer)算法的概念在这篇博客中并不涉及,网上有太多的资料啦,写的都非常的不错。这里推荐这位网友的介绍:https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/ 。如果链接失效了,可以看附件中的副本。本文中,我们基于一个例子来介绍在Lucene中如何实现FST算法及应用,感谢网友 关新全 的分享,基于他的分享使得我在看源码的时候事半功倍,在此基础上,增加一些更加贴近源码的内容。同样的关新全同学分享的文章在附件中。

准备工作

先介绍几个重要的类跟变量

Arc< T>类

每一个Arc< T>对象封封装了某个我们需要存储的数据,并且每一个Arc< T>对象属于某一个Node对象,一个Node对象可以包含多个一个Arc< T>对象,用Arc< T>[] 数组的方式存储,终止节点是没有Arc< T>对象的。Node类的子类有UnCompiledNode< T>类跟CompiledNode 类,下文中会介绍

output

output值是一个输入的附加值,比如有输入”mop”,它的附加值是100,但是对于分别封装了"m",“o”,“p”的三个arc对象,附加值100应该存放哪个arc对象的output字段呢?下面通过一个例子来说明:

处理“mop”, 100

处理“mt”, 91

BytesStore bytes;

在这里,我们只需要知道在BytesStore类中有一个current[]数组,它用来存放四种数据来描述一个arc的信息:

index
output
label
flag

UnCompiledNode< T>类;

CompiledNode类;

NodeHash< T>类

UnCompiledNode< T>[] frontier;

long lastFrozenNode;

算法基本步骤

步骤1:处理上一个输入与当前输入不相同Node节点,将Node节点中的所有arc对象的信息写入到current[]数组中,如果是第一个输入,直接执行下一个步骤。 步骤2:将当前输入写入到frontier[]数组中。 步骤3:处理上一个输入与当前输入相同的前缀值,调整output值。

例子

下面通过一个例子来介绍FST的构建跟查询,输入跟附加值如下:

注意的是输入顺序必须是有序的,才能获得一个最小FST。例子中的输入已经默认有序的

输入mop

输入moth

输入pop

处理终止节点

处理Node4 (h)

处理Node3(p -> t)

处理 “p”
处理“t”

这里有个注意点就是,当按照 p -> t的顺序处理结束后,会对刚才存储的数据执行逆置操作。所以“t”跟“p”对应的arc对象的数据在current[]数组中的位置就如下图:

处理Node2(o)

输入 star

处理终止节点

处理Node3(p)

处理Node2 (o)

输入stop

输入top

处理终止节点

处理Node4 (p)

处理Node3 (a -> o)

处理“a”
处理“o”

处理Node2 (t)

处理top

最后处理Node1节点

结语

本篇博客介绍了FST的构建过程,在随后的博客中会介绍如何使用current[]数组来恢复数据。

点击下载Markdown文件