资讯详情

FST 压缩算法

1 lucene字典

使用lucene查询不可避免地使用它提供的字典功能,即根据给定的字典功能term找到该term对应的倒排文件id列表等信息。实际上lucene索引文件的后缀名称tim和tip实现的文件是lucene字典功能。

如何实现字典?我们立刻想到排序数组,即term字典是一个按字母顺序排序的数组,每个数组都存储在term对应的倒排文档id列表。每次输入索引时,只需term数组载入内存,通过二分搜索。该方法的查询时间复杂Log(N),N指的是term数量占用的空间大小是O(N*str(term))。排序数组的缺点是消耗内存,即需要完全存储每个内存term,当term当数量达到数千万时,占用的内存将是不可接受的。

2 字典数据结构常用

许多数据结构可以完成字典功能,总结如下。

数据结构 优缺点
排序列表Array/List 采用二分法搜索,不平衡
HashMap/TreeMap 性能高,内存消耗大,几乎是原始数据的三倍
Skip List 跳跃表可以快速找到单词lucene、redis、Hbase均有实现。相对于TreeMap特别适用于高并发场景(Skip List介绍)
Trie 适用于英文词典。如果系统中有大量字符串,且这些字符串基本上没有公共前缀,则相应trie树将非常消耗内存(数据结构)trie树)
Double Array Trie 适用于中文词典,内存占用小,很多分词工具都采用这种算法(深入双数组Trie)
Ternary Search Tree 每一棵三叉树node有三个节点,具有节省空间和快速查询的优点(Ternary Search Tree)
Finite State Transducers (FST) 有限状态转移机,Lucene 4实现开源,广泛使用

3 FST原理简析

lucene从4开始大量使用的数据结构是FST(Finite State Transducer)。FST有两个优点:1)空间占用小。通过重复使用词典中的单词前缀和后缀,压缩存储空间;2)查询速度快。O(len(str))查询时间复杂。

下面简单描述一下FST结构工艺(工具演示:http://examples.mikemccandless.com/fst.py?terms=&cmd=Build it!)。我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs插入构建这五个单词FST(注:必须排序)。

1)插入“cat”

插入cat,每个字母形成一个边,t边指向终点。

2)插入“deep”

与前一个单词“cat最大前缀匹配,发现不匹配直接插入,P边缘指向终点。

3)插入“do”

前一个单词deep最大前缀匹配,发现是d,将新边添加到d边后面o,o边缘指向终点。

4)插入“dog”

前一个单词do”进行最大前缀匹配,发现是do,将新边添加到o边后面g,g边缘指向终点。

5)插入“dogs”

前一个单词dog最大前缀匹配,发现是dog,在g后增加新边s,s边缘指向终点。

最后,我们得到了上一个有向无环图。使用这个结构可以很容易地查询,比如给个term “dog,我们可以通过上述结构轻松查询是否存在,甚至可以在构建过程中将单词与某个数字和单词联系起来,从而实现key-value的映射。

4 FST使用和性能评价

我们可以将FST当做Key-Value数据结构来进行使用,特别在对内存开销要求少的应用场景。Lucene已经为我们提供了开源FST工具,以下代码是使用说明。

 1 public static void main(String[] args) {  2         try {  3             String inputValues[] = {"cat", "deep", "do", "dog", "dogs"};  4             long outputValues[] = {5, 7, 17, 18, 21};  5             PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);  6             Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE1, outputs);  7             BytesRef scratchBytes = new BytesRef();  8             IntsRef scratchInts = new IntsRef();  9             for (int i = 0; i < inputValues.length; i  ) { 10                 scratchBytes.copyChars(inputValues[i]); 11                 builder.add(Util.toIntsRef(scratchBytes, scratchInts), outputValues[i]); 12             } 13             FST<Long> fst = builder.finish(); 14             Long value = Util.get(fst, new BytesRef("dog")); 15             System.out.println(value); // 18 16         } catch (Exception e) { 17             ; 18         } 19     }

FST压缩率一般为3倍~相对于20倍TreeMap/HashMap膨胀3倍,内存节省9到60倍!(摘自:用自动机 Key-Value 存储),那FST性能真的能满足要求吗?

下面是苹果笔记本(i7处理器)进行了简单的测试,虽然性能不如TreeMap和HashMap,但它也很好,可以满足大多数应用程序的需求。

标签: 荔波智能电容器fst

锐单商城拥有海量元器件数据手册IC替代型号,打造 电子元器件IC百科大全!

锐单商城 - 一站式电子元器件采购平台