File WaveletMatrix.h

↰ Parent directory (ADS/succinct)

The wavelet matrix of Claude, Navarro and Ordonez: a static sequence :math:` S[ 0 , n ) ` of integers of w bits, i.e., on the alphabet :math:` [ 0 , 2^w ) , in :math: n w ` bits plus the directories of rank and select [see File RankSelect.h], with access, rank and select of any symbol in O( w ) time, and the queries on a range of places that a sequence of integers needs (the k-th smallest item of a range, the items below a value), also in O( w ) time.

Definition (ADS/succinct/WaveletMatrix.h)

Detailed Description

The level :math:` ell = 0 , ldots , w - 1 ` is a vector of bits :math:` B_ell ` that holds the bit :math:` w - 1 - ell ` (from the most significant one) of each item, in the order that the levels above leave: :math:` B_0 ` is in the order of S, and the items go to the next level stably sorted by the bit, the :math:` Z_ell ` ones with a 0 first and those with a 1 after them. Hence the item at the place i of a level is at the place :math:` rank_0( i ) ` of the next one if its bit is 0, and at :math:` Z_ell + rank_1( i ) ` if it is 1, and the items equal to c, in the order of S, are consecutive at the last level, at a place that the bits of c alone determine:

  • access( i ) follows the item down, a bit and a rank per level;

  • rank( c , i ), the number of c in :math:` S[ 0 , i ) `, follows the places 0 and i down along the bits of c, and the difference at the last level is the answer;

  • select( c , k ), the place of the k-th c, goes down to the place of the k-th c at the last level and back up by select, :math:` select_0 ` or :math:` select_1 ` as the bit of c at each level;

  • quantile( i , j , k ), the k-th smallest item of :math:` S[ i , j ) `, goes down the levels with the range, to the 0s if the range has more than k of them and to the 1s otherwise, and countLess( i , j , c ) sums the 0s that the range leaves at the levels where c has a 1.

Unlike the wavelet tree of Grossi, Gupta and Vitter, whose nodes split the alphabet in halves and need a pointer or an offset each, the matrix keeps one vector of n bits per level and no tree, at the same costs: it is the form of choice for the large alphabets (Claude, Navarro and Ordonez), and the base of the compressed indices of the integers and of the r-index. A wavelet tree shaped by the code of Huffman (Makinen and Navarro) takes :math:` n ( H_0 + 1 ) ` bits instead of n w and is faster on a skewed alphabet; the matrix here is the form for the alphabets of integers with no known distribution. Each level carries the directory of RankSelect [see File RankSelect.h], so that the matrix takes about :math:` 1.5 , n w ` bits, and a query of rank 2w ranks of one load and one sideways sum each.

The contracts [see File Contract.h]: the items fit in w bits, :math:` 1 le w le 64 `, the places are in the sequence, i <= j for a range, and k counts from 1 for select and from 0 for quantile, below the number of the items; the audit of the construction is that access() gives back each item. The functions are defined in WaveletMatrix.tpp.

  1. Claude, G. Navarro, A. Ordonez, The wavelet matrix: an efficient wavelet tree for large alphabets, Information Systems 47, 15-32, 2015, doi:10.1016/j.is.2014.06.002

  1. Grossi, A. Gupta, J. S. Vitter, High-order entropy-compressed text indexes, Proc. 14th SODA, 841-850, 2003

  1. Makinen, G. Navarro, Succinct suffix arrays based on run-length encoding, Proc. 16th CPM, LNCS 3537, 45-56, 2005, doi:10.1007/11496656_5

  1. Navarro, Wavelet trees for all, Journal of Discrete Algorithms 25, 2-20, 2014, doi:10.1016/j.jda.2013.07.004

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes