Wavelet Tree(小波树)

定义

Wavelet Tree(小波树)由 Grossi、Gupta 和 Vitter 于 2003 年提出,是压缩索引领域的核心结构:对一个字符集为 Sigma 的序列,按字符集对半划分,根节点用一个位图记录每个位置的字符属于左半还是右半,两侧字符分别递归构建子树,树高为 O(log |Sigma|)。

原理

配合支持 O(1) rank/select 的位图,小波树能在 O(log |Sigma|) 时间回答:access(i) 取第 i 个字符、rank(c, i) 统计前 i 个位置中字符 c 的出现次数、select(c, j) 找第 j 个 c 的位置;进一步可支持区间第 k 小、区间内某值域的元素计数等二维查询,空间接近序列的熵压缩下界。

应用

小波树是 FM-index 等压缩全文索引的标准组件,生物信息学的序列比对工具(基于 BWT 的短读比对)依赖其 rank 查询;它也被用作"把数字序列当作字符串"的通用查询结构,可替代主席树回答静态区间第 k 小。

优缺点

优点是功能多、空间可压缩到熵界;缺点是常数较大、动态更新困难,实现依赖高质量的位图 rank/select 支持。