Encodings and Compression

Concepts#

1. Prefix-Free Code — the property that makes a code decodable without delimiters; Kraft’s inequality says which code lengths are possible
2. Entropy — lower bound on the expected code length of any prefix-free code
3. Entropy-Optimal Code — code whose expected length equals the entropy; exists iff all $p_i = 2^{-L_i}$
4. Lagrange Multipliers — proof tool: minimising $\sum_i p_i L_i$ under the Kraft constraint gives $L_i = \log_2(1/p_i)$
5. Unary Code — simplest integer code, optimal for $\Pr(X = x) = 2^{-x}$, building block of Golomb and Elias codes
6. Golomb Code — unary quotient + binary remainder with modulus $M$, for geometrically distributed gaps
7. Elias-Gamma Code — unary length prefix + binary, no parameter, $2\lfloor \log_2 x \rfloor + 1$ bits
8. Elias-Delta Code — Elias-Gamma for the length, shorter than Gamma for large $x$
9. Gap Encoding — turns the sorted IDs of an inverted list into small numbers that the integer codes compress well
10. UTF-8 — prefix-free variable-length byte code for Unicode code points

How it fits together#

From prefix-freeness to optimality. A code is only usable without separators if it is prefix-free. Kraft’s inequality $\sum_i 2^{-L_i} \le 1$ characterises the code lengths a prefix-free code can have. Among these, the expected length $\bar L = \sum_i p_i L_i$ is bounded below by the entropy $H(X) = -\sum_i p_i \log_2 p_i$, and Shannon’s source coding theorem gives a prefix-free code with $\bar L \le H(X) + 1$. The bound $\bar L = H(X)$ is reached exactly when $L_i = \log_2(1/p_i)$ for all $i$, i.e. when every probability is a negative power of two (Entropy-Optimal Code). This gives the two standard exam proofs:

• Given a code, find the distribution for which it is optimal: set $p_i = 2^{-L_i}$, check $\sum_i p_i = 1$ and $\bar L = H(X)$.
• Prove the optimum: minimise $\sum_i p_i L_i$ subject to $\sum_i 2^{-L_i} = 1$ with Lagrange Multipliers, which yields $p_i = 2^{-L_i}$.

Integer codes as implicit distributions. Each integer code fixes a length $L(x)$, so by the rule above it is entropy-optimal for $\Pr(X = x) = 2^{-L(x)}$. Choosing a code means choosing which numbers you expect to be small:

All four build on the same idea: a self-delimiting (unary or Gamma) part that says how long the rest is, followed by plain binary digits.

Where the numbers come from. The sorted document IDs of an inverted list are large, but their differences are small, especially in the long lists of frequent words (Zipf’s law: a few words account for most occurrences). Gap Encoding turns the list into these differences, which are then written with one of the integer codes. Golomb suits gaps of roughly known size (choose $M$ from the list density), Elias codes need no parameter.

UTF-8 as a real-world prefix code. UTF-8 encodes Unicode code points with 1–4 bytes. The leading bits of the first byte (0, 110, 1110, 11110) play the role of the unary length prefix, and continuation bytes start with 10, so the code is prefix-free and self-synchronising. Exam tasks convert code points to bytes and count valid byte sequences (shortest-form rule).

Key Formulas#

• Kraft: $\sum_i 2^{-L_i} \le 1$ (Prefix-Free Code)
• Entropy: $H(X) = -\sum_i p_i \log_2 p_i$ (Entropy)
• Optimality: $\bar L = H(X) \iff p_i = 2^{-L_i}$ for all $i$ (Entropy-Optimal Code)
• Elias-Gamma length: $2\lfloor \log_2 x \rfloor + 1$ (Elias-Gamma Code)

Exercises & Exam Questions#

Exam occurrences#

Recurring patterns:

• Every exam includes an encoding task (usually Task 2, worth 20–25 points)
• Entropy-optimality proofs appear in nearly every exam – either proving a given code is optimal or finding the distribution that makes it optimal
• UTF-8 encoding/decoding appears alongside encodings starting from WS 15/16
• Coding tasks (implement encode/decode functions) appear in most exams, typically ~5pts and limited to 10–15 lines

Lectures#

• DBIS_VL01 > Tokenization — encoding errors in raw text (wrongly decoded UTF-8)
• DBIS_VL10 > Unicode — code points, UTF-8 in detail, URL encoding
• Prefix-free codes, entropy and the integer codes were not lectured in WS 25/26; they come from the past exams of the predecessor course Information Retrieval.

Related Topics#

• Inverted Index and Ranking — gap-encoded inverted lists are what the integer codes compress
• Web Applications — UTF-8 and URL encoding in HTTP and HTML