FST是什么,最开始我也不知道,直到我看了两篇博客,http://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/ https://blog.csdn.net/zx2011302580235/article/details/88594342 看完了之后才真的懂了什么是FST,所以建议大家先看一遍这两篇博客,然后再看我的,因为我写的不是介绍FST的,而是深入到代码层面。
在之前研究IK的时候,看了他存储词典的格式,接触到了前缀树这种数据结构,他的好处是可以共享前缀,但是并不能共享后缀,而FST就能共享后缀,实现更加高效的存储或者查找。当然FST比前缀树添加了一个要求:必须是按照字典顺序添加的,而前缀树则没有这个要求。FST除了能存东西,判断某个东西是否存在,即起到Set的功能外,还能实现Map的功能,即存储、查找key-value。在lucene的词典表、同义词的模块中都使用了FST,另外,我自己在工作中,也用到了,用来保存分词的权重,使用FST的确是能大大的降低内存,当然他的查找复杂度是要比HashMap要慢一些,他的查找复杂度是O(length(input)),查找的内容越长需要的时间也就越多,但是他得内存消耗比起Hashmap来说真的是太小了。
通过上面的两天博客,可以大概了解FST的组成包括两部分,一个是节点(Node),另一个是边(Arc),一个arc指向一个节点,在这个arc上有一个输入叫做label,还有输出(也可能没有输出),还有一个可能的finalOutput(最终输出,以后会介绍这个的作用)。一个节点可能有多个arc指向,但是一个arc只能指向一个节点。arc上的label其实就是输入的一部分,比如输入是abc,则会有三个arc,四个node,每个arc上的输出分别是a、b、,至于输出的话需要配合其他的节点才能确定。在FST的形成过程中,始终有一个叫做frontier的数组,也就是刚刚添加的一个term(或者说路线),frontier的存在就是为了做共享前缀,当下一个term过来的时候,先计算共享前缀(所以这里要求FST必须是按照排序顺序写入的),将现在的frontier中除去共享前缀以外的部分都会编译进入到fst中,然后将新的term出去共享前缀以外的部分写入到frontier,重新更新frontier,直到最后写入完成,调用Builder.finish方法将最后的frontier写入到fst中,然后再将root节点(也就是第一个节点,实际上就是所有的开头的arc)编译进fst,然后再经过压缩(不压缩也是可以用的,只是使用的内存会稍微一点)。在编译进入fst的时候,会查找共享后缀,比如之前写的是ab、现在突然来了一个bb,此时需要把aa编译进入fst,frontier中保存的是bb,等到下一个term过来时,假设来的是c,则需要把bb也编译进入,如果这里能用共享后缀的话,ab和bb就可以使用同一个边b指向结束的node了。看到这里估计会大概对fst有个初步的概念了。
FST很难以理解,但是真的很有用,理解了FST,也算是把自己的能力又提升了一个台阶。我个人用了一周的课余时间才把FST的代码看完,也算是收货颇丰,接下来我将分别介绍FST的生成、压缩、读取。先说一下我看的是lucene6.6版本的。
后续:第二篇博客,FST的生成并没有发表完全,ITEYE提示我有敏感词没法发表,所以仅仅保存了一部分,经过几个小时的努力仍然没有找到哪个词是敏感词最终放弃了,所以第二篇博客写的不全。浪费我好几个小时!
相关推荐
赠送源代码:fst-2.57-sources.jar; 赠送Maven依赖信息文件:fst-2.57.pom; 包含翻译后的API文档:fst-2.57-javadoc-API文档-中文(简体)-英语-对照版.zip; Maven坐标:de.ruedigermoeller:fst:2.57; 标签:...
描述了Lucene中如何使用FST算法构建term的内存索引,使用了很多图,直观的展现了FST图的构建流程,能够对想了解lucene内部实现机制原理的同学有帮助。
佛斯特FST-500系列变频器说明书rar,佛斯特FST-500系列变频器说明书
赠送源代码:fst-2.57-sources.jar; 赠送Maven依赖信息文件:fst-2.57.pom; 包含翻译后的API文档:fst-2.57-javadoc-API文档-中文(简体)版.zip; Maven坐标:de.ruedigermoeller:fst:2.57; 标签:ruedigermoeller...
jaque.zip,Java查询库使语言级代码表达式在运行时以表达式树的形式表示为对象,
FST610变频器说明书,包括安装,配线,接线端子图,操作说明,详细功能讲解,故障检查与排除,保养和维护,通信协议,以及功能参数简表等技术资料。
74FST3253 高速4选1数据手册, 可以用于软件无线电接收机的前端.3253 datasheet
FST650变频器说明书,包括安装,配线,接线端子图,操作说明,详细功能讲解,故障检查与排除,保养和维护,通信协议,以及功能参数简表等技术资料。
可根据seed值及dat数据,计算fst文件,可用于软件加密狗的复制等。
2019/2/20 上午10'07关于Lucene的词典FST深入剖析 | 申艳超-博客第 1 页(共 19 页)2019/2/20 上午10'07关于Luce
fst2.4及其依赖包,maven下载实在慢,还时不时无效,提供现有jar包
FST_for_Mobile_LE_1209.pdf FST_for_Mobile_LE_1209.pdf
FST - JDK兼容的高性能对象图的序列化
RC-FST 算法利用IP 地址高8 比特前缀建立Hash 压缩索引表, 将分类规则集分成多个子集, 并针对每个子集建立快速搜索树, 而这些规模相对小的本地搜索树更利于实现快速建立、查找和优化。为提高搜索树性能, 在规则分割...
Bayscan can calculate the fst value
2. FST Node , 表 示 FST 图 的 一 个 节 点 , 有 两 种 实 现 类 型 , 4. FST HashMap,一个使用探测法实现的 Ha
SITRANS FST030使用手册(英文版)
数字式变压器保护测控装置FST说明书pdf,数字式变压器保护测控装置FST说明书
FST fast-serialization 是重新实现的 Java 快速对象序列化的开发包。序列化速度更快(2-10倍)、体积更小,而且兼容 JDK 原生的序列化。要求 JDK 1.7 支持。 Maven: <groupId>de.ruedigermoeller ...
Fst_sliding_window