A bitvector knows how to count.

Give it a small rank directory and it can answer:

rank1(B, i) = number of 1 bits in B[0..i)

Add select support and it can also answer:

select1(B, k) = position of the k-th 1 bit

That is enough for binary strings. The wavelet tree asks what happens when the sequence is not binary.

The trick is to refuse the large alphabet at the top level. Split the alphabet in two. Write 0 for symbols in the left half and 1 for symbols in the right half. Then recursively build the same structure on the two stable subsequences. After \(\lceil \log_2 \sigma \rceil\) levels, a symbol has been identified by a path of binary decisions.

This is not just a cute encoding. It is a query plan.

The Stored Object

Let \(S[0,n)\) be a static sequence over alphabet \(\Sigma\). A balanced wavelet tree node owns a subalphabet \(A\) and the subsequence of \(S\) whose symbols are in \(A\).

If \(A\) contains more than one symbol, split it into \(A_0\) and \(A_1\). Store a bitvector \(B_v\):

\[B_v[i] = \begin{cases} 0 & \text{if } S_v[i] \in A_0 \\ 1 & \text{if } S_v[i] \in A_1. \end{cases}\]

The left child receives the symbols of \(S_v\) in \(A_0\), in the same order. The right child receives the symbols in \(A_1\), also in the same order. That stable partition is the invariant. It is why positions can be translated from a parent bitmap to a child bitmap with rank.

Grossi, Gupta, and Vitter introduced wavelet trees inside their 2003 work on high-order entropy-compressed text indexes.1 Navarro’s survey is a good map of the structure after it escaped that original setting: it can be viewed as a sequence representation, a permutation/reordering device, or a grid of points.2

The small version in this post is the sequence view.

Three Primitive Moves

For access(i), start at the root. Read the bit at position i.

bit 0: i <- rank0(B, i), go left
bit 1: i <- rank1(B, i), go right

When the descent reaches a leaf, that leaf’s symbol is S[i].

For rank(c, i), follow the path that would lead to symbol c. At every node, translate the prefix length:

c in left half:  i <- rank0(B, i)
c in right half: i <- rank1(B, i)

At the leaf, the remaining i is the number of occurrences of c in the original prefix.

For select(c, k), do the inverse. Start at the leaf for c, where the k-th copy has local position k - 1. Walk upward. If this leaf was reached through a left edge, ask the parent bitmap for the position of the corresponding zero; if it was reached through a right edge, ask for the corresponding one.

left edge:  parent_pos <- select0(B, child_pos + 1)
right edge: parent_pos <- select1(B, child_pos + 1)

Claude and Navarro’s practical study is a useful reminder that this elegant story lives or dies on the engineering of rank/select over the node bitvectors.3 The lab here uses visible prefix arrays, not a compressed RRR or broadword implementation, so the accounting is explanatory rather than competitive.

Range Quantile Is The Same Descent

Now ask a different question:

what is the k-th smallest symbol in S[l..r)?

At a node, count how many active range items go left:

\[z = \mathrm{rank}_0(B_v, r) - \mathrm{rank}_0(B_v, l).\]

If \(k \le z\), the answer is in the left child. Translate the range to:

l <- rank0(B, l)
r <- rank0(B, r)

Otherwise, the answer is in the right child. Subtract the left count and translate with rank1:

k <- k - z
l <- rank1(B, l)
r <- rank1(B, r)

Repeat until a leaf. Gagie, Puglisi, and Turpin used this observation to support range quantile queries, including medians as the special case where k is the middle rank, in \(O(\log \sigma)\) time using a balanced wavelet tree.4

The implementation below checks that descent against naive sorting for every slice of each built-in sequence.

What The Lab Audits

The module exports the same implementation used by the browser:

node - <<'NODE'
const lab = require("./assets/js/wavelet-tree-lab.js");
const EXPECTED_CASE_SHAPE = [
  "1:genome:all:24/5:58:24/125/24/2600:7",
  "2:genome:#:24/5:58:24/125/24/2600:7",
  "3:genome:A:24/5:58:24/125/24/2600:7",
  "4:genome:C:24/5:58:24/125/24/2600:7",
  "5:genome:G:24/5:58:24/125/24/2600:7",
  "6:genome:T:24/5:58:24/125/24/2600:7",
  "7:mississippi:all:12/5:29:12/65/12/364:7",
  "8:mississippi:#:12/5:29:12/65/12/364:7",
  "9:mississippi:i:12/5:29:12/65/12/364:7",
  "10:mississippi:m:12/5:29:12/65/12/364:7",
  "11:mississippi:p:12/5:29:12/65/12/364:7",
  "12:mississippi:s:12/5:29:12/65/12/364:7",
  "13:abracadabra:all:12/6:32:12/78/12/364:7",
  "14:abracadabra:#:12/6:32:12/78/12/364:7",
  "15:abracadabra:a:12/6:32:12/78/12/364:7",
  "16:abracadabra:b:12/6:32:12/78/12/364:7",
  "17:abracadabra:c:12/6:32:12/78/12/364:7",
  "18:abracadabra:d:12/6:32:12/78/12/364:7",
  "19:abracadabra:r:12/6:32:12/78/12/364:7",
  "20:prices:all:20/10:67:20/210/20/1540:7",
  "21:prices:0:20/10:67:20/210/20/1540:7",
  "22:prices:1:20/10:67:20/210/20/1540:7",
  "23:prices:2:20/10:67:20/210/20/1540:7",
  "24:prices:3:20/10:67:20/210/20/1540:7",
  "25:prices:4:20/10:67:20/210/20/1540:7",
  "26:prices:5:20/10:67:20/210/20/1540:7",
  "27:prices:6:20/10:67:20/210/20/1540:7",
  "28:prices:7:20/10:67:20/210/20/1540:7",
  "29:prices:8:20/10:67:20/210/20/1540:7",
  "30:prices:9:20/10:67:20/210/20/1540:7"
];
const EXPECTED_SAMPLE_SHAPE = [
  "abracadabra:7 cases/49 checks:12/6:32:84/546/84/364",
  "genome:6 cases/42 checks:24/5:58:144/750/144/2600",
  "mississippi:6 cases/42 checks:12/5:29:72/390/72/364",
  "prices:11 cases/77 checks:20/10:67:220/2310/220/1540"
];
const EXPECTED_CRITICAL_SHAPE = [
  "access agrees with the original sequence:30/30",
  "compressed bitmap entropy sums to sequence H0:30/30",
  "internal bitmaps preserve stable partition lengths:30/30",
  "range quantile agrees with sorting every slice:30/30",
  "rank agrees with naive prefix counts:30/30",
  "raw bitmap budget is bounded by fixed-width storage:30/30",
  "select agrees with naive occurrence positions:30/30"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CRITICAL_SHAPE.length;
const EXPECTED_TOTALS = {
  rows: EXPECTED_CASES,
  samples: EXPECTED_SAMPLE_SHAPE.length,
  criticalChecks: EXPECTED_CRITICAL_SHAPE.length,
  passed: EXPECTED_CASES,
  total: EXPECTED_CASES,
  checked: EXPECTED_CHECKS,
  passedChecks: EXPECTED_CHECKS,
  totalChecks: EXPECTED_CHECKS
};
const EXPECTED_CASE_ROWS = EXPECTED_CASE_SHAPE.map(
  (row) => `${row}:checks=${EXPECTED_CRITICAL_SHAPE.length}/${EXPECTED_CRITICAL_SHAPE.length}:` +
    "failed=none:passed=true"
);

function sameList(left, right) {
  return left.length === right.length &&
    left.every((value, index) => value === right[index]);
}

function sameJson(left, right) {
  return JSON.stringify(left) === JSON.stringify(right);
}

function symbolKey(symbol) {
  return symbol == null ? "all" : symbol;
}

function caseShape(row) {
  return `${row.caseId}:${row.sample}:${symbolKey(row.symbol)}:` +
    `${row.length}/${row.alphabet}:${row.waveletBits}:` +
    `${row.accessChecks}/${row.rankChecks}/` +
    `${row.selectChecks}/${row.rangeQuantileChecks}:${row.totalChecks}`;
}

function caseRow(row) {
  return `${caseShape(row)}:checks=${row.passedChecks}/${row.totalChecks}:` +
    `failed=${row.failedChecks.length ? row.failedChecks.join("|") : "none"}:` +
    `passed=${row.passed}`;
}

function rowDrifts(actual, expected) {
  return {
    missing: expected.filter((row) => !actual.includes(row)),
    extra: actual.filter((row) => !expected.includes(row))
  };
}

function hasRowDrift(drift) {
  return drift.missing.length > 0 || drift.extra.length > 0;
}

function auditShape(audit) {
  return {
    totals: {
      rows: audit.cases.length,
      samples: audit.bySample.length,
      criticalChecks: audit.criticalChecks.length,
      passed: audit.passed,
      total: audit.total,
      checked: audit.checked,
      passedChecks: audit.passedChecks,
      totalChecks: audit.totalChecks
    },
    cases: audit.cases.map(caseShape),
    caseRows: audit.cases.map(caseRow),
    bySample: audit.bySample.map(
      (row) => `${row.sample}:${row.cases} cases/${row.totalChecks} checks:` +
        `${row.length}/${row.alphabet}:${row.waveletBits}:` +
        `${row.accessChecks}/${row.rankChecks}/` +
        `${row.selectChecks}/${row.maxRangeQuantileChecks}`
    ),
    criticalChecks: audit.criticalChecks.map(
      (row) => `${row.check}:${row.passed}/${row.total}`
    )
  };
}

const audit = lab.auditWaveletTreeLab();
const shape = auditShape(audit);
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const failedCriticalChecks = audit.criticalChecks.filter(
  (row) => !row.ok || row.passed !== row.total
);
const caseRowDrifts = rowDrifts(shape.caseRows, EXPECTED_CASE_ROWS);
const shapeErrors = [
  sameJson(shape.totals, EXPECTED_TOTALS) ? null : "totals",
  sameList(shape.cases, EXPECTED_CASE_SHAPE) ? null : "cases",
  hasRowDrift(caseRowDrifts) ? "caseRows" : null,
  sameList(shape.bySample, EXPECTED_SAMPLE_SHAPE) ? null : "bySample",
  sameList(shape.criticalChecks, EXPECTED_CRITICAL_SHAPE) ? null : "criticalChecks"
].filter(Boolean);
console.table(audit.bySample);
console.table(audit.criticalChecks);
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  failed.length ||
  failedCriticalChecks.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    caseRowDrifts,
    failed,
    failedCriticalChecks,
    errors: audit.errors,
    passed: audit.passed,
    total: audit.total,
    passedChecks: audit.passedChecks,
    totalChecks: audit.totalChecks
  }, null, 2));
}
console.log(summary);
NODE

For every built-in sequence, the audit checks:

  • access(i) returns the original symbol for every position;
  • rank(c, i) equals a direct prefix scan for every symbol and prefix length;
  • select(c, k) returns the same position as a direct occurrence scan;
  • range quantile agrees with sorting every nonempty slice and taking the requested rank;
  • every internal bitmap length equals its stable partition children; and
  • the sum of zero-order entropy over node bitmaps equals the sequence’s zero-order empirical entropy.

The last check is the compression ledger. The raw balanced tree stores at most \(n \lceil \log_2 \sigma \rceil\) bitmap bits, because every original symbol contributes one bit per level on its root-to-leaf path. If each node bitmap were compressed to its own zero-order entropy while keeping rank/select, the entropy terms telescope to \(nH_0(S)\). Navarro gives the clean derivation in the survey: the root separates the alphabet into two groups; children separate those groups again; after the last split, the sum has become \(\sum_{c \in \Sigma} n_c \log_2(n/n_c)\).

Where This Toy Stops

The implementation is static and intentionally literal. It stores one prefix count per bit position, so rank is easy to inspect. A production compact sequence representation would replace those arrays with succinct rank/select structures, possibly use Huffman-shaped or multiary wavelet trees, or use a wavelet matrix to remove pointer-heavy tree navigation for large alphabets.

The important invariant survives those engineering choices:

parent range + rank on a stable bitmap = child range

Once that invariant clicks, the structure stops looking like a compression curiosity. It is a way to keep asking binary questions without forgetting where the original positions went.

  1. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter, “High-Order Entropy-Compressed Text Indexes”, SODA, 2003. Bibliographic record: KU ScholarWorks. ↩

  2. Gonzalo Navarro, “Wavelet Trees for All”, CPM, 2012. Springer record and DOI: 10.1007/978-3-642-31265-6_2. ↩

  3. Francisco Claude and Gonzalo Navarro, “Practical Rank/Select Queries over Arbitrary Sequences”, SPIRE, 2008. DOI: 10.1007/978-3-540-89097-3_18. ↩

  4. Travis Gagie, Simon J. Puglisi, and Andrew Turpin, “Range Quantile Queries: Another Virtue of Wavelet Trees”, arXiv:0903.4726, 2009/2010. DOI: 10.48550/arXiv.0903.4726. ↩