Wavelet Matrix Construction

This is a follow-up post to Enter the Wavelet Matrix. Compared to my previous entries this one is much more of a stream-of-consciousness that’s not really designed for anyone else to read (though hopefully on the way to a much more coherent and comprehensive explanation!)

Sidenote: This is very much an early draft, and not really understandable on its own, but I’m practicing the art of forging ahead with partial work.

The wavelet matrix can be constructed using an extremely simple algorithm, though explaining the meaning of the resulting structure will take a little bit more work.

The wavelet matrix is a way to represent a sequence of integers, which we will call symbols, by representing a sorting process – the symbols are incrementally sorted by their successive bits, from high to low, using a stable bucket sort, and the incremental results are written down into the wavelet matrix structure, and later used for reconstituting the elements or performing other algorithms such as ranged quantile queries.

Here’s an image illustrating the construction of a wavelet matrix for the sequence 1 4 2 3 7. The sequence starts out in its original order on the top layer and moves down incrementally through a series of bitwise bucket sorts that sort the elements into ‘left’ and ’right buckets based on whether the element has a 0-bit or 1-bit on that level. The

The data stored in the wavelet matrix is represented by the “pipes” in between the numbers rather than the numbers themselves.

This is what I mean when I say the wavelet matrix represents the process of sorting. It records whether each element “went left” or “went right” in the successive applications of the bucket sort.

The idea behind this picture is that all elements that go left appear before the elements that go right. So for example, the numbers 1, 2, and 3 have a zero for their top bit, and therefore appear on the left of the second row.

The numbers 4 and 7 have a 1 in that top bit, and therefore go right and appear at the end. The numbers that went left are indicated by gray pipes, and the ones right are indicated by black pipes.

The next sorting is based purely on the second bit. The numbers 2 and 3 have a 1 in that position, so they go right.

The same process occurs again on the third layer. Note how 7 was the maximal element on each row indicated and therefore went right on each level.

This is my sixth attempt to try to explain this process, and clearly it’s not working very well, but I will forge ahead, because I think this section does capture something about the practical algorithm I use for large-alphabet wavelet matrices.

I’m beginning to think it’s probably best to start with an introduction to the wavelet tree where the effects of the sort are much more salient, since the bottom row ends up with the symbols sorted by value. In the wavelet matrix, the symbols end up sorted by the bit-reversal of their value.


Actually…

Here’s a visualization of the wavelet tree representation of the sequence

7 6 5 4 3 2 1

The wavelet tree has a nice hierarchical structure where all of the children stay underneath their parent node, though this is not obvious from these matrix-style visualizations that lose the node borders.

And here’s the wavelet matrix version:

Here we can see that each layer is sorted independently of the previous – ie. other than the stability of the sort, whether the elements on each layer go either left or right purely based on the bit at that level, rather than taking into account the previous levels too (which is what gives the preceding picture its tree structure).

As a side note, the reason the wavelet matrix is an improvement over the wavelet tree is because the wavelet tree requires you to store the node offsets at each level, which scales linearly with the size of the maximum symbol. Without this information, it becomes impossible to navigate from one level of the wavelet tree to the next.

The wavelet matrix is based on this ingenious idea of ordering all of the left children before all of the right children on each level, rather than keeping the child nodes “underneath” the parent. This helps because when you’re on a particular level you can compute the number of left children that precede you and the number of right children that precede you with a simple rank query on the bit vector holding that level. Therefore, navigating to a left child involves looking at the number of zeros to your left, and jumping to that location on the next level. Navigating to the right child involves looking at the number of ones to your left and jumping to that location on the next level (plus the total number of zeros, ie. left children, since all the left children precede the right children).

It’s very clever but hard to explain. Hopefully I can find a nice way to present all of this.

References