Spec WaveletTree
A WaveletTree is a hierarchical RankDictionary.

Extends RankDictionary
All Extended RankDictionary
Defined in <seqan/index.h>
Signature template <typename TValue, typename TSpec, typename TConfig> class RankDictionary<TValue, WaveletTree<TSpec, TConfig> >;

Template Parameters

TValue The alphabet type of the wavelet tree.
TSpec A tag for specialization purposes. Default: void

Interface Function Overview

Interface Functions Inherited From RankDictionary

Detailed Description

The nodes of a wavelet tree consist of a bit string as well as a character c. In each level of the tree, characters smaller than c are represented as a 0 while character greater or equal to c are represented with a 1. The characters represented by a 0 form the string to be represented by the left subtree while characters represented by a 1 form the string of the right subtree. Therefore, only the bit string of the root node represents all characters while all other nodes represent subsets.