SuccinctStore深度解析 — CSA实现
- 前提
- SuccinctStore依靠Compressed Suffix Array这一数据结构进行构建，实际上这也是因为CSA在空间使用上会优于CST。不过，如果没有从理论上明白它的一些时空复杂度，我相信是没人刚用的。要是突然我能构造出一个异常的输入样本，导致糟糕的怎么办？所以我们先来看下它的时间空间复杂度吧。
- 时间复杂度：O(n)，实际上有很多好的CSA的构建算法都能达到这个上界，做竞赛的同学们可能会比较熟悉DC3算法。
- 空间复杂度：O(n)，这个也没什么悬念的？真的吗？对于CSA来说，我们需要更加紧的上界，这里就要提出k-th order empirical entropy了。
- zero-th order empirical entropy
- 要理解k-th order empirical entropy，首先要理解zero-th order empirical entropy。
- zero-th order empirical entropy是单独压缩每个单词最后能压缩的大小，可以看出，它并没有利用到上下文信息。
- k-th order empirical entropy，高级的压缩器能利用这一上下文并根据这一上下文选出不同的codeword，k是这个上下文的大小，k越大，当然压缩率会越高，但是这个上下文表示所需要的空间也会相应变大，一般我们需要有个empirical的选值。公式大家可以g娘一下。
- CSA的空间复杂度为O(nHk(T)) + o(n)
- 实现
- 目标
- f = compress(file)
- append(f, buffer)
- buffer = extract(f, offset, len)
- cnt = count(f, str)
- offsets = search(f, str)
- offsets = rangesearch(f, str1, str2)
- ranges = wildcardsearch(f, prefix, suffix, dist)
- offsets = regex(f, pattern)
- Flat Text To Semi-structured Data
- 一些简单的拓展就能让我们实现更加复杂的数据模型。
- Suffix Array 运用
- 我们维护两个数组AoS2Input和Input2AoS，不难看出这两个互为反函数。
- 当我们要search某Pattern p的时候，binary search p所在的两个端点，返回成区间形式即可。
- 当我们要extract的时候，利用Input2AoS，直接是一个O(1)的操作。
- 压压压
- 原先的实现会需要维护O(nlog + n^2)的空间。所以考虑引入新的数组NextCharIdx，NextCharIdx(idx) -> NextIndexInAoS。
- 这样我们只需要mark每个单词出现的首个index即刻，后面需要定位的时候follow NextCharIdx，通过binary search到对应的字符Offset即可。
- 对于AoS2Input和Input2AoS两个输出，我们采用取样的方法减小其大小。默认选择这两个数组的大小为原数组的1/32。
- 因为NextCharIdx本身是单调递增的，所以我们可以选择一些编码方式做DeltaCompression， 这里我使用的是Elias Gamma Code。