Bijective encoding between finite words of level-k symbols and single symbols of level k+1, for the first three literal SUL levels.

A SUL level defines a finite alphabet [0, n) and a bijection between valid words over that alphabet and symbols of the next level. Each level's output alphabet is strictly larger than its input alphabet, so every finite sequence of bits eventually collapses to a single root symbol after enough levels.

Alphabet sizes grow rapidly. Starting from n = 2 (binary):

Level 4 and beyond are too large for integer representation; they are handled by the hash level.

See the SUL overview for the full definition. In brief, a valid word has the form [s0, s1, ..., sk, t] where s0 > s1 > ... > sk and sk <= t.

A word encodes to the integer index of that word in the lexicographic ordering defined by the level's word structure. sum(i) gives the count of valid words whose first symbol is ≤ i; it defines the offset boundaries used during both encoding and decoding.

Encoding is streaming: symbols are fed one at a time via Level.encode. The encoder returns undefined while the strictly-decreasing prefix is still being accumulated, and emits the output symbol exactly once when the terminating symbol t arrives.

const { encode } = level2
let state = emptyEncodeState
for (const s of [3n, 1n, 2n]) {
    const [out, next] = encode(state)(s)
    state = next
    if (out !== undefined) { /* out is the level-3 symbol */ }
}

Given an output symbol i, the first symbol s0 of the original word is recovered by:

const d = 2n * (n - 1n)          // = 2^(e+1)
const r = log2((i + n - 2n) / d) // estimate: r ∈ {s0-1, s0}
const s0 = sum(r) > i ? r : r + 1n

The offset n - 2 is what keeps the estimate within 1 of the true value. With it, the start of the group with first symbol s lands at j = sum(s-1) + (n-2) = d · 2^(s-1) + (s-1), so j / d always falls in [2^(s-1), 2^s) and log2(j / d) ∈ {s-1, s}. Without the offset the estimate can be off by 2 or more, breaking the single-step correction.

literal1ToVec, literal2ToVec, and literal3ToVec decode a level-k symbol all the way down to a canonical MSB bit vector by chaining the level decoders:

literal3ToVec(s) = flatten(decode3(s).map(
    t => flatten(decode2(t).map(
        u => decode1(u).map(bit => vec(1)(bit))
    ))
))

These are used by the Id module to convert level-3 symbols into fixed-width bit vectors for inline storage.

• levels.md — full encoding tables for levels 1–3 with cumulative counts
• avg.md — derivation of average word length (E → e as n → ∞)
• decode.md — decode lookup tables illustrating the n-2 offset
• SUL overview