Wavelet Trees：简介

Alex Bowe 2011年6月28日 — 阅读时长5分钟 今天我将讨论一种优雅的方法，用于回答 较大字母表 上序列的 rank 查询，这种结构称为 Wavelet Tree。在 我之前的文章 中，我介绍了一种名为 RRR 的数据结构，它用于快速回答 二进制 序列的 rank 查询，并提供隐式压缩。

Wavelet Tree 将字符串组织成位向量的层级结构。 rank 查询的时间复杂度为 $\mathcal{O}(\log_2{A})$，其中 $A$ 是字母表的大小。它由 Grossi、Gupta 和 Vitter 在他们 2003 年的论文 High-order entropy-compressed text indexes [4] 中提出（有关更多论文，请参阅 Further Reading 部分）。此后，它出现在许多论文中 [1, 2, 3, 5, 6]。

如果将位向量存储在 RRR 序列中，则可能比原始序列占用更少的空间。或者，可以将位向量存储在 Sadakane 和 Okonohara 提出的 rank 索引中 [7]。 它有不同的压缩方法。 我将在下次讨论它 ;) – 幸运的是，我将在稍后在 Sadakane-sensei 下学习（更新：现在我在东京跟随他攻读博士学位）。

在未来的另一篇文章中，我将展示如何使用 Suffix Array 通过发出 $2P$ 个 rank 查询来查找长度为 $P$ 的任意模式。如果使用 Wavelet Tree，这意味着模式搜索的时间复杂度为 $\mathcal{O}(P \log_2{A})$，也就是说，“大海捞针”的大小无关紧要，而是取决于“针”的大小和字母表的大小。

构建 Wavelet Tree

Wavelet Tree 将字符串转换为平衡的二叉树位向量，其中 $0$ 替换一半的符号，而 $1$ 替换另一半。 这会产生 歧义，但在每个级别上，此字母表都会被过滤和重新编码，因此歧义会减少，直到完全没有歧义为止。

树的定义递归如下：

1. 获取字符串的字母表，并将前半部分编码为 $0$，后半部分编码为 $1$：$\{ a, b, c, d \}$ 将变为 $\{ 0, 0, 1, 1 \}$；
2. 将每个 $0$-编码的符号，$\{ a, b \}$，分组为一个子树；
3. 将每个 $1$-编码的符号，$\{ c, d \}$，分组为一个子树；
4. 将此操作递归地应用于每个子树，直到只剩下一个或两个符号（当 $0$ 或 $1$ 只能表示一件事时）。

对于字符串 "Peter Piper picked a peck of pickled peppers"（由于文献中的约定，空格和字符串终止符分别表示为 $\$ 和 $$$），Wavelet Tree 将如下所示： 注意：字符串实际上没有存储，但为了方便起见，此处显示了字符串 它具有字母表 $\{ $, P, \, a, c, d, e, f, i, k, l, o, p, r, s, t \}$，它将映射到 $\{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 \}$。因此，例如，$$$ 将映射到 $0$，而 $r$ 将映射到 $1$。

左子树是通过仅获取 $0$-编码的符号 $\{ $, P, \_, a, c, d, e, f \}$，然后通过划分这个 新的 字母表来重新编码它们来创建的：$\{ 0, 0, 0, 0, 1, 1, 1, 1 \}$。 请注意，在第一级，$e$ 将被编码为 $0$，但现在它被编码为 $1$（它在叶节点再次变为 $0$）。

我们可以将位向量存储在 RRR 结构中，以实现快速的二进制 rank 查询（如下所述，这是需要的）和压缩 :) 实际上，由于它是一棵平衡树，我们可以连接每个级别并将其存储为单个位向量。

查询 Wavelet Tree

从 我之前的文章 回顾一下，rank 查询是到指定位置为止的 $1$ 位计数。 较大字母表的 rank 查询是类似的 – 不是 $1$，它可以是任何其他符号：

在构造树之后，可以使用 log $A$ ($A$ 是字母表大小) 个 二进制 rank 查询在位向量上完成 rank 查询 - 如果将它们存储在 RRR 或另一个二进制 rank 索引中，则为 $\mathcal{O}(1)$。 每个内部节点的编码都可能含糊不清，但当然它并非毫无用处 – 我们使用含糊不清的编码来指导我们找到合适的子树，并不断这样做，直到得到答案。

例如，如果我们想知道 $rank(5, e)$，我们使用以下过程，如下所示。 我们知道 $e$ 在此级别编码为 $0$，因此我们采用位置 $5$ 处的 $0$ 的 二进制 rank 查询：

结果是 $4$，然后我们用它来指示在 $0$-child 中进行 rank 的位置：第 $4^{th}$ 位（或位置 $3$ 处的位，由于 $0$-basing）。 我们知道要查询 $0$-child，因为那是 $e$ 在父级别中编码的方式。 然后，我们递归地重复此操作：

在叶节点，我们有了答案。 我很乐意解释为什么这有效，但是自己思考它既有趣又有意义 ;)

还有一些方法可以提供快速的 select 查询，但我再次将这留给您自己研究。 你们中好奇的人也可能对 Mäkinen 和 Navarro 描述的 Huffman-Shaped Wavelet Tree 感兴趣 [5]。

为善用你的新能力

您可以自己实现它，但是如果您想立即开始使用，那么全能聪明的 Francisco Claude 已经在他的 Compressed Data Structure Library (libcds) 中提供了一个实现。 如果您使用它创建了一些整洁的东西，请务必报告 ;)

更新：Terence Siganakis 写了一篇关于 Wavelet Tree 的博客文章，该文章登上了 Hacker News 的首页，从而引发了一场有趣的讨论。 讨论 在这里。

如果您读到这里，请考虑在 Twitter 上关注我：@alexbowe。

进一步阅读

我不想用证明和其他细节来饱和这篇博客文章，因为它本来就是一个轻松的介绍。 如果您想更深入地研究这种美丽的结构，请查看以下论文：

[1] F. Claude and G. Navarro. Practical rank/select queries over arbitrary sequences. In Proceedings of the 15th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 5280, pages 176–187. Springer, 2008. [2] P. Ferragina, R. Giancarlo, and G. Manzini. The myriad virtues of wavelet trees. Information and Computation, 207(8):849–866, 2009. [3] P. Ferragina, G. Manzini, V. M ̈akinen, and G. Navarro. Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms, 3(2):20, 2007. [4] R. Grossi, A. Gupta, and J. Vitter. High-order entropy-compressed text indexes. In Proceedings of the 14th annual ACM-SIAM symposium on Dis- crete algorithms, pages 841–850. Society for Industrial and Applied Mathematics, 2003. [5] V. Mäkinen and G. Navarro. Succinct suffix arrays based on run-length encoding. Nordic Journal of Computing, 12(1):40–66, 2005. [6] V. Mäkinen and G. Navarro. Implicit compression boosting with applications to self-indexing. In Proceedings of the 14th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 4726, pages 214–226. Springer, 2007. [7] D. Okanohara and K. Sadakane. Practical entropy-compressed rank/select dictionary. Arxiv Computing Research Repository, abs/cs/0610001, 2006. data structures