A tree-shaped document, once taken apart into columns, is mostly small integers. There are child counts, string lengths, parent pointers written as differences, type tags and run lengths. The payload values (the actual numbers and strings) are a minority of the fields. In the bit-level columnar encoding studied here, every one of these structural fields is an integer, and in small documents most of them are below 16 (in the worked example at the end of this article, every structural integer is).
Byte-oriented formats spend at least 8 bits on each such integer. This article looks at what you can do at bit granularity instead. I give exact length functions for a family of 2-bit selector codes, compare them with LEB128 and Elias-γ, check prefix-freeness and the Kraft sum, and work out the expected length under a geometric source.
Two baselines
Write for the bit length of , and set .
LEB128. The integer is split into 7-bit groups, least significant first. Each group is written as a byte whose top bit is 1 if another byte follows. The length in bits is
So for , for , and so on.
Elias-γ. For , write zeros followed by the binary form of . The length is . To cover , encode .
LEB128 has a floor of 8 bits: the integer 3 needs two payload bits, and LEB128 spends one continuation bit and five zero bits on top of them. Elias-γ has no floor, but its length grows as , twice the information-theoretic rate. The selector codes below sit between the two.
A 2-bit selector code
Selector code short. A 2-bit selector picks one of four tiers:
| selector | payload | used for |
|---|---|---|
00 | 2 bits | |
01 | 3 bits | |
10 | 4 bits | |
11 | LEB128 of |
The encoder picks the first tier that fits: payload width , selector , with sent to the escape.
In Lean 4, writing codewords as strings of 0 and 1, most significant bit first:
/-- Bit length b(n), with b(0) = 1. -/
def bitLength (n : Nat) : Nat := if n < 2 then 1 else n.log2 + 1
/-- The low `w` bits of `v`, most significant first. -/
def bits (v w : Nat) : String :=
String.mk <| (List.range w).reverse.map fun i =>
if v.testBit i then '1' else '0'
/-- LEB128: 7-bit groups, least significant first, top bit = "more follows". -/
def leb128 (n : Nat) : String :=
if n < 128 then bits n 8
else bits (128 + n % 128) 8 ++ leb128 (n / 128)
decreasing_by omega
def short (n : Nat) : String :=
let d := if n < 4 then 2 else bitLength n
if d ≤ 4 then bits (d - 2) 2 ++ bits n d
else bits 3 2 ++ leb128 n
#eval short 3 -- "0011"
#eval short 5 -- "01101"
#eval short 12 -- "101100"
#eval short 200 -- "111100100000000001"
Its length function is
- selector / continuation
- payload
Proposition 1 (break-even against LEB128).
Proof. For , , so subtract 4, 5 and 6 from 8. For the escape writes exactly bits after the selector. ∎
The same statement, machine-checked for every :
-- continues the definitions above
def lenLEB (n : Nat) : Nat := 8 * ((bitLength n + 6) / 7)
/-- L_short(n) - L_LEB(n). -/
def diff (n : Nat) : Int := (short n).length - lenLEB n
/-- Proposition 1, checked for every n < 2^14. -/
example : (List.range (2^14)).all (fun n =>
diff n == if n < 4 then -4 else if n < 8 then -3
else if n < 16 then -2 else 2) := by native_decide
So the selector code never loses more than 2 bits, and that bound is reached for every . Two variants in the same format use different tier widths:
| code | tier 00 | tier 01 | tier 10 | tier 11 | difference from LEB128 |
|---|---|---|---|---|---|
short | 2-bit | 3-bit | 4-bit | LEB128 | −4 / −3 / −2 / +2 |
uint | 3-bit, | 4-bit, | 6-bit, | LEB128 | −3 / −2 / 0 / +2 |
num | 3-bit delta code | 4-bit, | 6-bit, | LEB128 | (delta) / −2 / 0 / +2 |
The 6-bit tier of uint and num costs 8 bits, the same as LEB128. It is not a saving against LEB128. It is a saving of 2 bits against the escape, which would otherwise be taken for . In num the 00 tier carries a delta from the previous number instead of a literal (see the last section). I checked all the differences above by enumerating .
Against Elias-γ
With , . Elias-γ is shorter for (1, 3, 3 bits against 4) and in two bands: (9 bits against 10) and (15 or 17 bits against 18). The two codes tie at . The selector code is shorter at , from 7 to 15, from 31 to 127, and for every . It keeps winning for large , because grows more slowly than . The selector code also has a practical advantage: the decoder reads two bits and then knows the width. It does not have to count a run of zeros.
The bands where Elias-γ wins, computed rather than read off by hand:
-- continues the definitions above
/-- Elias-γ length, encoding m = n + 1. -/
def lenGamma (n : Nat) : Nat := 2 * (n + 1).log2 + 1
/-- Maximal runs [a, b] of n < 2^14 where Elias-γ is strictly shorter. -/
def gammaWins : List (Nat × Nat) :=
let w := (List.range (2^14)).filter fun n => lenGamma n < (short n).length
w.foldr (fun n acc => match acc with
| (a, b) :: r => if n + 1 = a then (n, b) :: r else (n, n) :: acc
| [] => [(n, n)]) []
#eval gammaWins -- [(0, 2), (16, 30), (128, 510)]
Prefix-freeness and the Kraft sum
Proposition 2. The selector code is prefix-free.
Proof. The first two bits fix the tier. In tiers 00, 01 and 10 the payload width is fixed, so two codewords of the same tier have the same length and cannot be proper prefixes of each other. In tier 11, LEB128 is prefix-free: a byte with top bit 0 ends the codeword. A code built by picking a branch with a fixed-length prefix and then using a prefix-free code inside each branch is itself prefix-free. ∎
A prefix-free code satisfies the Kraft inequality . The gap measures codewords that are never produced. Count each tier’s contribution:
- Tier
00: 4 codewords of length 4, contributing . This is the full share of the selector value. - Tier
01: the 3-bit payload has 8 patterns, but only 4–7 are used. The patterns 0–3 are already in tier00. That gives out of a possible . - Tier
10: likewise only 8–15 of 16 patterns are used, giving out of . - Tier
11: canonical LEB128 has Kraft sum . The 1-byte codewords for are never used here, which removes . With the 2-bit selector this tier contributes .
The missing splits into 128 from the 3-bit tier, 128 from the 4-bit tier, 16 from the unused small LEB128 bytes, and 1 from the non-canonical LEB128 forms (a final byte of zero). In the 3-bit and 4-bit tiers, the leading payload bit is always 1, so it carries no information. For uint the same count gives . I checked both sums numerically by summing over the piecewise-constant ranges of up to 8-byte LEB128 and adding the geometric tail of the longer forms.
- selector
- payload
- never emitted
An offset variant
Subtracting each tier’s base before writing the payload makes every payload pattern name a distinct integer.
Offset selector code. Tier bases are . The code writes 00 + 2 bits of for , 01 + 3 bits of for , 10 + 4 bits of for , and 11 + LEB128 of otherwise.
All four tiers are now full, so . The only redundancy left is the non-canonical LEB128 forms. The break-even with LEB128 moves:
| range of | difference from LEB128 |
|---|---|
| −4 | |
| −3 | |
| −2 | |
| +2 | |
| −6 | |
| +2 | |
| −6 | |
| +2 |
The 3-bit tier now covers 8 values instead of 4, and the 4-bit tier covers 16 instead of 8. A new effect also appears: just above each power , the offset pulls back under the LEB128 byte boundary. That saves a whole byte, minus the 2-bit selector. The decoder pays one addition per value. What is lost is the property that the payload bits are the binary form of .
Expected length under a geometric source
Take for , so and the mean is . Each of these codes has a length that is a step function: with steps at thresholds . Taking expectations gives the tail-sum form
For the two codes:
The LEB128 tails cancel in the difference:
This is negative exactly when . Solving numerically gives , which is . For the offset variant the crossing is at , and for uint it is at . The table below gives expected lengths in bits. All were computed by direct summation, and the closed form above matches to the printed precision. is the entropy of the source. Rice is the best Golomb–Rice code with parameter , which is the right reference here, since Golomb codes are optimal for geometric sources.
| LEB128 | short | offset | uint | Elias-γ | best Rice | |||
|---|---|---|---|---|---|---|---|---|
| 0.5 | 1 | 2.000 | 8.000 | 4.066 | 4.063 | 5.004 | 2.266 | 2.000 () |
| 0.9 | 9 | 4.690 | 8.000 | 5.828 | 5.148 | 5.803 | 5.705 | 4.756 () |
| 0.97 | 32.3 | 6.480 | 8.162 | 8.288 | 7.353 | 7.459 | 8.762 | 6.592 () |
Two observations. At small means the 4-bit floor of the selector code is the main cost: at it spends twice the entropy. Near the break-even, the offset variant is about one bit better than the plain one, and that gain comes from filling the codewords the Kraft sum showed to be unused. A Rice code beats all of them on a true geometric source, but only once is fixed. Choosing needs the mean, and the selector code needs no parameter. A source that is not geometric, for example one with extra mass at 0 and 1 and a heavy tail, can be far from any single Rice parameter. Proposition 1 bounds the selector code’s penalty against LEB128 at 2 bits for every , whatever the source, and that is the case for keeping a bounded-penalty escape.
Fixed widths and delta windows
When the range of a field is known in advance, no selector is needed. The format uses a fixed 3-bit value type tag (eight codes: seven value types and the reserved code 000, which never names a value type) and a 2-bit key type (array node, object node, base64url key, other key). A fixed width of bits for equiprobable symbols has Kraft sum 1 when is a power of two. Skew in the tag distribution is handled by run-length packing instead of a variable-length tag. A run of more than 3 equal tags is written as the reserved tag 000, then short(count), then the tag. For example, five true values take bits instead of .
Parent links and numbers are often close to the previous value, so they are coded as differences inside a small window.
Delta window. For a difference with , the code is if and if . This maps to and to . The inverse is for and otherwise. Code 7 is never a delta.
/-- The delta window on [-3, 3] and its inverse. -/
def window (d : Int) : Nat := if d ≥ 0 then d.toNat else (3 - d).toNat
def unwindow (c : Nat) : Int := if c ≤ 3 then c else -((c : Int) - 3)
example : ∀ d : Fin 7, unwindow (window ((d : Int) - 3)) = (d : Int) - 3 := by
decide
#eval (List.range 7).map fun i : Nat => window ((i : Int) - 3)
-- [6, 5, 4, 0, 1, 2, 3] (d = -3 .. 3)
The unused eighth pattern is spent differently in each column. In the number column a delta is 00 followed by the 3-bit code, 5 bits in total, and 00 111 is the escape for a run of repeated values. In the link columns the 3-bit field holds and a separate 1-bit flag column marks delta against literal, so a delta link costs 4 bits. Value 0 is reserved in both fields: in the 3-bit delta field it is the run escape, and on a literal it means “widen the literal field by one bit”, which lets the literal width grow with the number of nodes without ever being sent explicitly. A worked case is the document {a:1,b:2,c:[3,4]}. Its four value links are (owner slots , plus one), so the codes are : the first link has no predecessor and is coded as its own value, the rest as differences from the previous link. Every link falls in the window. Because the codes are carried as , the four links take bits plus a 2-bit “all flags are 1” prefix.
Open questions
- Per-column tiers. The tier widths 2/3/4 are fixed. Picking tier widths per column from a cheap statistic (a quantised mean, sent in a few header bits) would approach the Rice row of the table without giving up the escape. I have not worked out the header cost.
- Wider windows. A 3-bit window covers . Whether a selector-coded window, for example 2 bits for and 4 bits for , pays for itself depends on the second-difference distribution of real link columns. That distribution I have not measured.
- Strides. A constant stride larger than 3, such as , falls outside the window and is written as literals. Delta-of-delta coding would capture it at the cost of one more state register.