| Invented by | Grossi, Gupta, Vitter (2003) | |
| Idea: |
- a data structure for rank and select on a string over any alphabet, not just on a bitvector
- divide and conquer on the alphabet: halving it at every level reduces the general problem to binary rank and select on bitvectors, which are well understood
- every node remembers one bit per character — which half of its alphabet that character belongs to — and hands each child exactly the characters marked for it, in their original order
- a node covering a single symbol is a leaf; a query is a walk of \(O(\log|\Sigma|)\) levels, one rank or select per level
|
| Advantages: |
- rank and select over a large alphabet in \(O(\log|\Sigma|)\) time, using \(n\log|\Sigma|\) bits — essentially the size of the text itself
- allows a compressed representation: shaping the tree by a Huffman code instead of halving the alphabet puts frequent symbols on shorter paths, so the bitvectors shrink towards the text's entropy
- has several applications even outside of stringology
|
| Disadvantages: |
- the tree is built for one fixed text; updates are far harder than queries
|