µ1 , . . . , µm with |DS (µi )| ∼ lg(1/|PS [µi ]) 1 store |µi| Elias code 2 store left subtree sizes in depth-first traversal using arithmetic coding 2a Encode sequence of outcomes as subinterval I of [0, 1) = I0 Know subtree_size(v1 ) = |µi | = 5 (from 1 ) for v1 , left subtree size ℓ1 ∈ {0, 1, 2, 3, 4} identify with subintervals of I0 of lengths p(ℓ1 , 4 − ℓ1 )|I0 | = 1 5 here ℓ1 = 3 I1 = [3 5 , 4 5 ) know subtree_size(v2 ) = ℓ1 = 3 left subtree size ℓ2 ∈ {0, 1, 2} use subintervals of I1 of lengths p(ℓ1 , 2 − ℓ1 )|I1 | = 1 3 · 1 5 here ℓ2 = 1, I2 = [3 5 + 1 15 , 3 5 + 2 15 ) = [2 3 , 11 15 ) subtree_size(v3 ) = ℓ2 = 1, so ℓ3 = 0. nothing to store! v4 and v5 same I = [2 3 , 11 15 ) v1 v2 v3 v4 v5 2b Arithmetic coding: Find interval [ m 2l , m+1 2l ) ⊆ I (l, m ∈ N) Here: [22 32 , 23 32 ) encode I by l-bit binary representation of m. Here: 10110 Always have l lg(1/|I|) + 2 Sebastian Wild Hypersuccinct Trees ESA 2021 14 / 24