Florian Kurpicz
Article Available in ACM Journal of Experimental Algorithmics

Practical Wavelet Tree Construction

Our article "Practical Wavelet Tree Construction" has been published in the ACM Journal of Experimental Algorithmics. Here, we present improved practical wavelet tree and wavelet matrix construction algorithm in different models of computation, i.e., RAM, shared memory, distributed memory, and external memory. The article is open-access and can be found here (DOI).

Abstract

We present new sequential and parallel algorithms for wavelet tree construction based on a new bottom-up technique. This technique makes use of the structure of the wavelet trees—refining the characters represented in a node of the tree with increasing depth—in an opposite way, by first computing the leaves (most refined), and then propagating this information upwards to the root of the tree. We first describe new sequential algorithms, both in RAM and external memory. Based on these results, we adapt these algorithms to parallel computers, where we address both shared memory and distributed memory settings. In practice, all our algorithms outperform previous ones in both time and memory efficiency, because we can compute all auxiliary information solely based on the information we obtained from computing the leaves. Most of our algorithms are also adapted to the wavelet matrix, a variant that is particularly suited for large alphabets.