skip to content

You own a binary envelope's tag code and new field types keep arriving - how much of the Kraft budget do you leave unspent?

level: principalimportance: should knowfreq 28%

answer

  1. the code space is a budget
  2. spending all of it is final
  3. unused leaves are room to grow
  4. depth sets the price of reserving
  5. escape into a wider tag field

basics

~20 s

Enough to add tags without lengthening deployed codewords, and no more. A code whose Kraft sum is exactly 1 is closed: the next tag forces an existing codeword to grow. Reserving a leaf at depth d costs 2^-d of the budget.

solid answer

~50 s

Treat the code space as a budget of 1 with an explicit reservation. A **complete** code, sum exactly 1, is optimal today and unextendable tomorrow - adding a symbol means some existing codeword must lengthen, which changes what every already-deployed reader parses. So reserve a leaf, and put it deep: a reserved codeword at depth `d` costs `2^-d` of the budget, taken out of the frequent tags' lengths, so a depth-3 escape costs one eighth while a reservation at the root would cost half. The usual shape is one reserved codeword that means *the real tag follows in a wider field*, which converts a fixed reservation into unbounded room. The trade-off is real and has no single answer: every bit of reserved space is paid on **every message** by the tags you did not shorten, against a change cost you pay once, if the format actually grows.

go deeper

for a junior

The point to carry away is that a code with no spare leaves cannot gain a symbol without changing an existing codeword, which is a change every reader feels.

for a middle

Be able to price a reservation: a spare codeword at depth d consumes two to the minus d of the code space, and that share comes out of the lengths of the tags you actually send.

for a senior

Argue the shape rather than a number - one deep escape codeword that widens the tag field, plus a defined behaviour for unknown tags, so a new field never forces a coordinated redeploy.

for a principal

Own the asymmetry: over-reserving is a measurable tax on every message forever, under-reserving is a one-off coordinated change whose cost depends on whether the readers are yours.

## What 'the budget' means here Kraft's inequality says the codeword lengths of a prefix code satisfy the sum of `2^-li` at most 1, and its converse says any list meeting that bound is realisable. Read as a design tool rather than a theorem, it is an accounting identity: **the code space is one unit, and a codeword at depth `l` spends `2^-l` of it** by reserving the entire subtree underneath. That makes the extension question arithmetic rather than opinion: - **Sum exactly 1 - a complete code.** Every leaf is claimed. There is nowhere to put a new symbol, so adding one necessarily lengthens an existing codeword. Deployed readers hold the old lengths, so the same bits now parse differently: not a new field they can ignore, but a change to the meaning of fields they already handle. - **Sum below 1 - slack.** The shortfall is unclaimed code space, and a new symbol drops into it with **no change to any existing codeword**. Old readers still parse the tags they know and meet an unrecognised one they can skip or reject explicitly. ## The price list | reservation | budget cost | what it leaves for the live tags | |---|---|---| | one leaf at depth 1 | 0.5 | half the space - rarely defensible | | one leaf at depth 3 | 0.125 | an eighth given up, absorbed by rare tags | | one leaf at depth 6 | about 0.016 | almost nothing measurable | | none (complete code) | 0 | best expected length, no room at all | The budget is not free money: it is taken from the codeword lengths of the tags you actually send. Reserve `2^-d` and some tag somewhere gets a bit longer than it would have been, on **every message where it appears**. That is why depth matters more than count - a reservation deep in the tree is nearly free in expected length, while a shallow one competes directly with your most frequent tag. ## The shape that scales: an escape codeword A fixed reservation of `k` spare leaves buys room for exactly `k` future tags, which is a guess about a future you do not know. The better structure spends one reserved codeword as an **escape**: a codeword that does not denote a field at all, but means *the tag identifier follows in a wider field*. 1. Frequent tags keep short codewords and are unaffected. 2. One reserved deep codeword is the escape. 3. Every future tag is expressed as the escape plus an extended identifier, so the number of future tags is bounded by the extended field, not by the reservation. The cost of an escape is concentrated exactly where you want it: on rare and not-yet-invented tags, which pay the escape plus the wider identifier, while the common path pays only the sliver of budget the escape consumed. The same reasoning is why self-extending numeric encodings reserve a bit pattern to mean 'keep reading' instead of picking a final width. ## The judgement, and what it depends on There is no universally correct reservation, and an interviewer asking this wants the variables named, not a number: - **How fast does the vocabulary actually grow?** A tag set that has been stable for years justifies a smaller reservation than one that gains fields every release. - **Who are the readers, and can you redeploy them?** If every reader ships from one place with the writer, a lengthened codeword is an ordinary change and slack is close to worthless. If readers are outside your control, the reservation is buying you the ability to ship at all. - **How skewed is the tag distribution?** With heavy skew, most of the budget must go to a handful of tags and reservations should be deep. With a flat distribution, the cost of a spare leaf is easy to absorb. - **What does a reader do with an unknown tag?** A reservation is only useful if unknown tags have a defined behaviour - skip with a known length, or fail loudly. Without that rule, the spare leaf is a trap, because the new tag is decodable yet meaningless. - **What is the cost of being wrong in each direction?** Over-reserving is a permanent tax on message size that you can measure. Under-reserving is a one-off but potentially very expensive coordinated change. They are not symmetric, and which one hurts more is a property of the organisation, not of the code. ## The answer to give Say the extremes out loud: a complete code is the right choice for a closed alphabet and the wrong one for an evolving format; a large shallow reservation is almost always wrong because it competes with the frequent tags. Then land on the shape - one deep escape codeword, skip or reject semantics defined for unknown tags, and the reservation sized by how often the vocabulary really changes and by whether the readers are yours.

  • What exactly does it cost to reserve one unused codeword at depth d?
    Two to the minus d of the Kraft budget, and that share is taken from the codeword lengths of the tags you actually transmit - some tag ends up a bit longer than it needed to be. A reservation at depth 6 costs about 0.016 of the budget and is usually unmeasurable; one at depth 1 costs half the space and competes directly with your most frequent tag.
  • Why is an escape codeword better than simply reserving several spare leaves?
    Spare leaves buy room for a fixed number of future tags, which is a guess. One escape codeword means the identifier continues in a wider field, so the number of future tags is limited by that field rather than by the reservation, and the whole cost falls on rare and future tags instead of the common path.
  • When is leaving no slack at all the right call?
    When the alphabet is genuinely closed, or when every reader deploys together with the writer so lengthening a codeword is an ordinary same-change edit. A complete code has the best expected length available for the source, and slack you never use is a permanent tax on every message. The question is only whether you control every reader.

saying these in an interview costs you the question

  • Says code space can always be reclaimed later by renumbering.
  • Treats unused leaves purely as waste with no purpose.
  • Reserves a shallow codeword without counting what it costs.
  • Believes a new codeword can be appended to a complete code.
  • Assumes a reserved leaf costs the same wherever it sits in the tree.