论文标题
在小波树和小波矩阵结构之间翻译
Translating Between Wavelet Tree and Wavelet Matrix Construction
论文作者
论文摘要
小波树（Grossi等人[Soda，2003]）和小波矩阵（Claude等人[Inf。Syst。，2015]）是紧凑的数据结构，具有许多应用，例如文本索引或计算几何形状。通过继续Fischer等人的最新研究。 [Alenex，2018]，我们探讨了这些密切相关的数据结构的相似性和差异，重点是它们的结构。我们开发了一个数据结构，以修改小波树或矩阵的构造算法，以构建另一个。这种修饰是有效的，因为它不会使任何已知的小波树或小波矩阵结构算法的渐近时间和空间要求恶化。
The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 2015]) are compact data structures with many applications such as text indexing or computational geometry. By continuing the recent research of Fischer et al. [ALENEX, 2018], we explore the similarities and differences of these heavily related data structures with focus on their construction. We develop a data structure to modify construction algorithms for either the wavelet tree or matrix to construct instead the other. This modification is efficient, in that it does not worsen the asymptotic time and space requirements of any known wavelet tree or wavelet matrix construction algorithm.
