lucene是一个常用的并发处理时的全局搜索引擎，它和目前搜索引擎采取的处理大量查询数据的思路都是，事先把跟关键词相匹配数据存储起来,查找的时候直接把存储好的数据进行返回。
lucene也对内部的数据结构和算法进行优化，著名的有内嵌FST数据结构，在索引生成方面的应用。LZ4的实时压缩算法。
lucene对基本数据结构压缩优化
- 普通的 Int 和 Long 存储一个整数,必须用 32 位和 64 位,哪怕该整数的值为 1 。这样 就带来了存储空间的浪费。
首先lucene在进行存储时，文档id,词频等一定是非负整数。
Vint: 由不超过 4 个 Byte 组成,Byte 的最高位表示是否需要再读取一个 Byte,剩下的 7 位存 储数值。这样当数值范围在[0,127]之间用一个 Byte 就够了,数值范围在[128, 16383]之间用 两个 Byte 就够了,有效节约了存储空间。
VLong: 由不超过 8 个 Byte 组成,存储方式与 VInt 相同。
String: 存储一个 VInt 表示字符串的长度,然后用 UTF8 编码存储字符串。
- Zigzag 编码主要在于对负数的压缩,比如-1(1111 1111 1111 1111 1111 1111 1111 1111), 经过转码后,变成了 1(0000 0000 0000 0000 0000 0000 0000 0001),节约了很多符号位。
- Lucene 中用到的一项技术就是位压缩(bit-packing).这意味着整型数组的类型从固定大小 (8,16,32,64 位)4 种类型,扩展到了[1-64]位共 64 种类型。这样的话，在lucene中的整型数组实际上变为了变长。
FST数据结构
FST本质上是一种有限状态自动机。FST在 Lucene 中的应用多以 FST<Key,Value>的形式出现,其功能与 Map 类似,支持用 Key 来查询 Value;同时 FST 也支持用 Value 来查找最优 Key,这是 Map 做不到的。
其复杂度为O(len(key)),空间利用率高，普通有状态机,如 Trie 树就已经能够实现 O(len(Key))的时间复杂度,然而空间利用率却 低得可怜。
FST 正 是一个最小的、有向的、无环的最小自动机。
但是FST方法有一个局限条件:为了保证最小自动机,给定的 List 必须是有序的。
假设有{w1,w2....,wn} n 个有序的字符串集。 a、先构造一个除 w1 外,最小的 FST。(此时 FST 中有 w1 一个字符串) b、构造一个除 w2 外,最小的 FST。(此时 FST 中有 w1,w2 两个字符串) c、构造一个除 w3 外,最小的 FST。(此时 FST 中有 w1,w2,w3 三个字符串)其实就是一种迭代的思想,通过对字符串后缀和前缀的重复利用以实现状态的压缩, 这也是为什么需要一个排序的 List。
FST实现类map查询
首先我们来看看常用的map字典效率
数据结构 | 优缺点 |
|---|---|
排序列表Array/List | 使用二分法查找，不平衡 |
HashMap/TreeMap | 性能高，内存消耗大，几乎是原始数据的三倍 |
Skip List | 跳跃表，可快速查找词语，相对于TreeMap等结构，特别适合高并发场景 |
Trie树 | 适合英文词典，如果系统中存在大量字符串基本没有公共前缀，则相应的trie树将非常消耗内存 |
public static void main(String[] args) throws IOException {
String inputValues[] = {"cat","deep","do","dog","dogs"};
Long outputValues[] = {5L,7L,17L,18L,21L};
//lucene中的int输出
PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
//构建FST,并配置输入类型，按byte优化数据存储大小，以及数据的输出类型
Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE1,outputs);
IntsRefBuilder scratchInts = new IntsRefBuilder();
for (int i = 0; i < inputValues.length; i ) {
BytesRef scratchBytes = new BytesRef(inputValues[i].getBytes());
scratchInts.copyUTF8Bytes(scratchBytes);
//build添加的key只能为int
builder.add(scratchInts.toIntsRef(),outputValues[i]);
}
FST<Long> fst = builder.finish();
Long value = Util.get(fst, new BytesRef("dog"));
System.out.println(value); // 18
}FST压缩率一般在3倍~20倍之间，相对于TreeMap/HashMap的膨胀3倍，内存节省就有9倍到60倍！
我们看到input是经过排序的，也就是ordered。否则生成的就不是最小的FST。另外如果NO_OUTPUT就退化为FSA了，不用执行第4步重新分配output了。
其中freezeTail 方法就是将不再变化的部分进行冰冻，又叫compile，把UnCompileNode，给构建进FST里。进入到FST是先进行compileNode, 然后addNode进去的。
总结以下，加入节点过程：
1)新插入input放入frontier，这里还没有加入FST 2)依据当前input, 对上次插入数据进行freezeTail操作, 放入FST内 3)构建input的转移（Arc）关系 4)解决Output冲突，重新分配output，保证路径统一(NO_OUTPUT,不执行) 最后在finish方法里，执行freezeTail(0), 把所有的input构建进FST内。
