Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433738 | Theoretical Computer Science | 2016 | 7 Pages |
Abstract
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σ/logn⌉) time where n is the number of symbols and σ is the alphabet size.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J. Ian Munro, Yakov Nekrich, Jeffrey S. Vitter,