Module quadwt 

This module implements a Quad Wavelet Tree, providing efficient implementations of AccessUnsigned, RankUnsigned, and SelectUnsigned for a vector of unsigned integers.

The Quad Wavelet Tree indexes a sequence of unsigned integers and facilitates the following three operations:

• get(i): Accesses the i-th symbol of the indexed sequence.
• rank(s, i): Counts the number of occurrences of symbol s up to position i, excluding i.
• select(s, i): Returns the position of the i+1-th occurrence of symbol s.

We have four aliases types for a Quad Wavelet Tree: QWT256<T>, QWT512<T>, QWT256Pfs<T>, and QWT512Pfs<T>. The generic type T is the type of the indexed unsigned integer values. The values 256 and 512 are the employed block sizes in the internal representation. A block size of 256 has a faster query time at the cost of slightly larger space overhead. The prefix Pfs indicates that the wavelet tree uses additional data structures to speed up the rank queries with prefetching. Refer to the paper for more details.

Performance

All operations run in $$\Theta(\log \sigma)$$ time, where $$\sigma$$ is the alphabet size, i.e., one plus the largest symbol in the sequence. The space usage is $$n \log \sigma + o(n \log \sigma )$$ bits.

To optimize query time and space usage, it’s advisable to compact the alphabet and remove “holes,” if any.

Limitations

This data structure can efficiently index vectors of lengths up to 2^{43} symbols.

Examples

use qwt::{QWT256Pfs,AccessUnsigned, RankUnsigned, SelectUnsigned};

// Example usage of Quad Wavelet Tree
// Constructing a Qwt256Pfs for u32 integers
let qwt = QWT256Pfs::from(vec![1_u32, 2, 3, 4, 5, 6, 7, 8]);

// Querying operations
assert_eq!(qwt.get(3), Some(4));  // Accesses the 3rd symbol (0-indexed), should return 4
assert_eq!(qwt.rank(3, 7), Some(1));  // Counts the occurrences of symbol 3 up to position 7, should return 1
assert_eq!(qwt.select(3, 0), Some(2));  // Finds the position of the 1st occurrence of symbol 3, should return Some(2)

Modules

huffqwt

Structs

OccsRangeIter

QWaveletTree

The generic RS is the data structure we use to index a quaternary sequence to support access, rank, and select` queries.

Traits

RSforWT

Alias for the trait bounds to be satisfied by a data structure to support rank and select queries at each level of the wavelet tree. We need an alias to avoid repeating a lot of bounds here and there.

WTIndexable

Alias for the trait bounds of the type T to be indexable in the wavelet tree.