🌳 Wavelet Tree

Explore the wavelet tree, a succinct data structure that answers access, rank, and select queries over a sequence in logarithmic time while using space close to the information-theoretic minimum.

Algorithms & AI3DModerate60 FPS

The simulator visualizes how an input sequence over a small alphabet is recursively split into a binary tree of bitvectors, and how a single access, rank, or select query travels down or up that tree using rank and select operations at each level to arrive at its answer.

🔬 What It Demonstrates

🎮 How to Use

Enter or generate a sequence over a chosen small alphabet, watch the wavelet tree build level by level as the alphabet range is halved at each node, then pick an access, rank, or select query and step through the highlighted path the query takes through the tree, with each level's bitvector and its rank or select computation shown explicitly.

💡 Did You Know?

Did you know that the FM-index used by widely deployed genome aligners like BWA and Bowtie stores the entire Burrows-Wheeler-transformed genome as a wavelet tree, letting them count how many times a DNA pattern occurs in a multi-gigabase genome using only a few dozen rank operations, without ever decompressing the sequence?

⚙ Under the hood

Explore the wavelet tree, a succinct data structure that answers access, rank, and select queries over a sequence in logarithmic time while using space close to the information-theoretic minimum.

wavelet treesuccinct data structuresrank selectbitvectorfm-indexstring algorithmscompressed indexingbioinformatics

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install