Fast construction of wavelet trees

作者：Munro J Ian; Nekrich Yakov^*; Vitter Jeffrey S

来源：Theoretical Computer Science, 2016, 638: 91-97.

DOI：10.1016/j.tcs.2015.11.011

• Wavelet trees
• Compressed data structures
• Compressed sequences

In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in O(n [log sigma/root logn]) time where n is the number of symbols and a is the alphabet size.

• 出版日期2016-7-25