00 · Shannon (1948) — Entropy of Language#
Dependencies: stdlib only — collections, math, re
Runtime: < 30 seconds on any CPU
In 1948, Claude Shannon published A Mathematical Theory of Communication. Among its many consequences: language has measurable entropy — a lower bound on how many bits per symbol any lossless encoding can achieve.
Why does this matter for MT? Because Shannon’s framework lets us ask:
How much information do two languages share when they describe the same event?
That question is the seed of every statistical MT system we build in Parts 3–5.
What we implement#
Character-level entropy \(H_1\) (unigram) and \(H_2\) (bigram) for EN and DE.
Word-level entropy on the same corpus.
Cross-entropy and KL divergence between the two languages.
Shannon’s perplexity — the effective vocabulary size implied by the entropy.
A “Time-machine” cell: run the corpus statistics on our 20 held-out test sentences to establish a baseline we revisit every chapter.
The corpus#
We use Multi30k EN↔DE (the training split, ~29k sentence pairs, ~300k tokens each). If the data hasn’t been downloaded yet, we fall back to a small built-in sample so the notebook runs without any network access.
# This chapter is **stdlib only** — nothing to install.
# It runs on any Python 3.8+ with no pip dependencies.
import math
import os
import re
from collections import Counter
from pathlib import Path
# ── paths ──────────────────────────────────────────────────────────────────
REPO_ROOT = Path("__file__").resolve().parents[2] if "__file__" in dir() else Path("../../")
DATA_DIR = REPO_ROOT / "data" / "multi30k"
# ── tiny fallback corpus (always available, zero dependencies) ─────────────
FALLBACK_EN = """A man in an orange hat starring at something .
A Boston Terrier is running on lush green grass in front of a white fence .
A girl in karate uniform breaking a stick with a front kick .
Five people wearing winter jackets and helmets stand in the snow .
People are near a car and one is carrying a red bag .
A man in a gray shirt is lifting weights .
Two young boys with a kite in a grassy field .
A woman in a brown dress and white shirt is talking on a cell phone .
A man is riding a bicycle on a trail through the woods .
A group of people is sitting on a set of bleachers .
Two dogs are running through the grass .
A woman in a red shirt is holding a dog on a leash .
A young boy in a blue shirt is playing in the sand .
A man in a white shirt is painting a fence .
A girl with a yellow umbrella is walking in the rain .
A dog is jumping to catch a frisbee .
Two children are playing on a swing set .
A man wearing a blue jacket is taking a photograph .
A woman is reading a book in a park .
A black and white dog is running through a field ."""
FALLBACK_DE = """Ein Mann mit einem orangefarbenen Hut starrt auf etwas .
Ein Boston Terrier läuft auf sattgrünem Gras vor einem weißen Zaun .
Ein Mädchen in Karateuniform bricht einen Stock mit einem Frontlift .
Fünf Personen in Winterjacken und Helmen stehen im Schnee .
Menschen stehen bei einem Auto und einer trägt eine rote Tasche .
Ein Mann in einem grauen Hemd hebt Gewichte .
Zwei junge Jungs mit einem Drachen auf einem Grasfeld .
Eine Frau in einem braunen Kleid und weißem Hemd telefoniert .
Ein Mann fährt auf einem Fahrrad auf einem Waldweg .
Eine Gruppe von Personen sitzt auf einem Tribünenblock .
Zwei Hunde rennen durch das Gras .
Eine Frau in einem roten Hemd hält einen Hund an der Leine .
Ein kleiner Junge in einem blauen Hemd spielt im Sand .
Ein Mann in einem weißen Hemd streicht einen Zaun .
Ein Mädchen mit einem gelben Regenschirm geht im Regen .
Ein Hund springt um eine Frisbee zu fangen .
Zwei Kinder spielen auf einem Schaukelgestell .
Ein Mann in einer blauen Jacke fotografiert .
Eine Frau liest ein Buch in einem Park .
Ein schwarz-weißer Hund rennt durch ein Feld ."""
def load_corpus(lang: str) -> list[str]:
"""Return list of sentences. Falls back to built-in sample if data absent."""
path = DATA_DIR / f"train.{lang}"
if path.exists():
with open(path, encoding="utf-8") as f:
lines = [l.strip() for l in f if l.strip()]
print(f"Loaded {len(lines):,} sentences from {path}")
return lines
fallback = FALLBACK_EN if lang == "en" else FALLBACK_DE
lines = [l.strip() for l in fallback.splitlines() if l.strip()]
print(f"[fallback] Using built-in {len(lines)}-sentence sample for '{lang}'")
return lines
en_sents = load_corpus("en")
de_sents = load_corpus("de")
1 · Character-level entropy#
Shannon’s unigram character entropy:
gives the minimum bits-per-character for a memoryless code. The bigram entropy \(H_2\) conditions on the previous character:
German has lower bigram entropy than English on the same domain — it is more predictable once you know the previous character, mainly because of long compound nouns.
def char_unigram_entropy(sentences: list[str]) -> float:
text = " ".join(sentences).lower()
counts = Counter(text)
total = sum(counts.values())
return -sum((c / total) * math.log2(c / total) for c in counts.values())
def char_bigram_entropy(sentences: list[str]) -> float:
"""Conditional entropy H(C_n | C_{n-1}) estimated from bigram counts."""
text = " ".join(sentences).lower()
unigrams: Counter = Counter()
bigrams: Counter = Counter()
for i in range(len(text) - 1):
unigrams[text[i]] += 1
bigrams[(text[i], text[i + 1])] += 1
total_bi = sum(bigrams.values())
h = 0.0
for (c1, c2), cnt in bigrams.items():
p_bi = cnt / total_bi
p_cond = cnt / unigrams[c1] # p(c2 | c1)
h -= p_bi * math.log2(p_cond)
return h
h1_en = char_unigram_entropy(en_sents)
h1_de = char_unigram_entropy(de_sents)
h2_en = char_bigram_entropy(en_sents)
h2_de = char_bigram_entropy(de_sents)
print("Character-level entropy (bits/char)")
print(f" EN H1={h1_en:.3f} H2={h2_en:.3f}")
print(f" DE H1={h1_de:.3f} H2={h2_de:.3f}")
print()
print("Bigram redundancy (1 - H2/H1):")
print(f" EN {1 - h2_en/h1_en:.1%}")
print(f" DE {1 - h2_de/h1_de:.1%}")
2 · Word-level entropy#
Moving from characters to words, entropy explodes — natural language has a vocabulary of tens of thousands of types, each with a long tail of rare tokens (Zipf’s law).
German word entropy is higher than English on the same domain because German compounds create unique word types that never repeat.
def tokenize(sentence: str) -> list[str]:
return re.findall(r"[\w']+", sentence.lower())
def word_entropy(sentences: list[str]) -> tuple[float, int, int]:
"""Returns (entropy_bits, vocab_size, token_count)."""
counts: Counter = Counter()
for s in sentences:
counts.update(tokenize(s))
total = sum(counts.values())
h = -sum((c / total) * math.log2(c / total) for c in counts.values())
return h, len(counts), total
h_w_en, v_en, n_en = word_entropy(en_sents)
h_w_de, v_de, n_de = word_entropy(de_sents)
print("Word-level statistics")
print(f" EN tokens={n_en:,} vocab={v_en:,} H={h_w_en:.3f} bits/word perplexity={2**h_w_en:.1f}")
print(f" DE tokens={n_de:,} vocab={v_de:,} H={h_w_de:.3f} bits/word perplexity={2**h_w_de:.1f}")
3 · Cross-entropy and KL divergence#
Cross-entropy \(H(P, Q)\) measures how many bits you need on average to encode symbols drawn from distribution \(P\) using a code optimised for \(Q\):
KL divergence \(D_{KL}(P \| Q) = H(P,Q) - H(P)\) is the excess cost.
Here we compute the cross-entropy of EN word distribution under the DE model and vice versa, using add-1 (Laplace) smoothing to handle unseen words.
def build_unigram(sentences: list[str]) -> tuple[Counter, int]:
counts: Counter = Counter()
for s in sentences:
counts.update(tokenize(s))
return counts, sum(counts.values())
def cross_entropy_kl(
p_counts: Counter, p_total: int,
q_counts: Counter, q_total: int,
) -> tuple[float, float]:
"""Cross-entropy H(P,Q) and KL(P||Q) in bits, with Laplace smoothing on Q."""
vocab_q = len(q_counts)
h_p = 0.0 # true entropy of P
h_pq = 0.0 # cross-entropy
for word, cnt_p in p_counts.items():
p_x = cnt_p / p_total
cnt_q = q_counts.get(word, 0)
q_x = (cnt_q + 1) / (q_total + vocab_q) # Laplace
h_p -= p_x * math.log2(p_x)
h_pq -= p_x * math.log2(q_x)
kl = h_pq - h_p
return h_pq, kl
en_counts, en_total = build_unigram(en_sents)
de_counts, de_total = build_unigram(de_sents)
hpq_en_de, kl_en_de = cross_entropy_kl(en_counts, en_total, de_counts, de_total)
hpq_de_en, kl_de_en = cross_entropy_kl(de_counts, de_total, en_counts, en_total)
print("Cross-entropy H(P, Q) and KL divergence D_KL(P||Q) [bits/word]")
print(f" H(EN, DE) = {hpq_en_de:.3f} KL(EN||DE) = {kl_en_de:.3f}")
print(f" H(DE, EN) = {hpq_de_en:.3f} KL(DE||EN) = {kl_de_en:.3f}")
print()
print("Interpretation: the KL divergence is the 'distance' between the two")
print("word distributions. An MT system must bridge this gap.")
4 · Zipf’s Law#
Shannon noted that natural language follows Zipf’s law: the \(r\)-th most frequent word has frequency \(\propto 1/r\). This power-law tail is why language entropy is so high — the long tail of rare words is hard to compress.
We visualise the rank-frequency plot for EN and DE to confirm Zipf holds on Multi30k.
def zipf_stats(counts: Counter) -> None:
"""Print the top-10 words and the fraction of tokens they cover."""
total = sum(counts.values())
top10 = counts.most_common(10)
cumulative = sum(c for _, c in top10)
print(f" Top-10 words cover {cumulative/total:.1%} of all tokens")
for rank, (word, cnt) in enumerate(top10, 1):
print(f" {rank:2d}. {word:<20s} {cnt:6,} ({cnt/total:.3%})")
print("=== English ===")
zipf_stats(en_counts)
print()
print("=== German ===")
zipf_stats(de_counts)
5 · Bilingual mutual information#
For a parallel corpus, we can ask: how much information does knowing an English sentence give us about its German translation?
We approximate this with pointwise mutual information (PMI) over aligned word pairs, using the naive bag-of-words alignment (every EN word co-occurs with every DE word in the same sentence pair).
High-PMI pairs are translation equivalents. Low-PMI pairs are noise. This is the intuition behind IBM Model 1 (Chapter 31).
def top_pmi_pairs(
en_sentences: list[str],
de_sentences: list[str],
top_n: int = 20,
min_count: int = 5,
) -> list[tuple[str, str, float]]:
"""Naive co-occurrence PMI over aligned sentence pairs."""
en_cnt: Counter = Counter()
de_cnt: Counter = Counter()
co_cnt: Counter = Counter()
n_pairs = 0
for en_s, de_s in zip(en_sentences, de_sentences):
en_toks = set(tokenize(en_s))
de_toks = set(tokenize(de_s))
en_cnt.update(en_toks)
de_cnt.update(de_toks)
for e in en_toks:
for d in de_toks:
co_cnt[(e, d)] += 1
n_pairs += 1
results = []
for (e, d), co in co_cnt.items():
if co < min_count:
continue
p_e = en_cnt[e] / n_pairs
p_d = de_cnt[d] / n_pairs
p_ed = co / n_pairs
pmi = math.log2(p_ed / (p_e * p_d))
results.append((e, d, pmi))
results.sort(key=lambda x: -x[2])
return results[:top_n]
pairs = top_pmi_pairs(en_sents, de_sents)
print("Top-20 EN↔DE word pairs by PMI (naive bag-of-words co-occurrence)")
print(f" {'EN':<18s} {'DE':<18s} PMI")
print(" " + "-" * 46)
for e, d, pmi in pairs:
print(f" {e:<18s} {d:<18s} {pmi:.2f}")
6 · Time-machine cell#
We run every chapter’s system on the same 20 held-out test sentences. Chapter 00 can only report how hard the translation problem is — entropy and PMI — not produce translations. That changes in Chapter 10.
TIME_MACHINE_EN = [
"A man is walking his dog in the park .",
"Two children are playing near a fountain .",
"A woman in a red coat is reading a book .",
"Several people are waiting at a bus stop .",
"A cyclist is riding through a crowded street .",
"A dog is chasing a ball on the beach .",
"A group of tourists is taking photographs .",
"A young girl is feeding ducks by a pond .",
"Two men are playing chess in a cafe .",
"A street musician is playing the violin .",
"Children are running through a field of flowers .",
"An old man is sitting on a bench reading a newspaper .",
"A woman is carrying groceries up a flight of stairs .",
"A boy is kicking a football against a wall .",
"A couple is dancing on an empty street .",
"A chef is preparing food in an outdoor kitchen .",
"A cat is sleeping on a warm windowsill .",
"Workers are repairing a road in the rain .",
"A small boat is sailing on a calm lake .",
"Firefighters are climbing a tall ladder .",
]
print("=== Chapter 00 · Time-Machine Output ===")
print()
print("This chapter has no translation system — only corpus statistics.")
print("Lower bound on translation difficulty (per-sentence character entropy):")
print()
for i, sent in enumerate(TIME_MACHINE_EN, 1):
h = char_unigram_entropy([sent])
print(f" {i:2d}. [{h:.2f} bits/char] {sent}")
Summary#
Quantity |
EN |
DE |
|---|---|---|
Char unigram entropy \(H_1\) |
~4.1 bits |
~4.0 bits |
Char bigram entropy \(H_2\) |
~3.3 bits |
~3.1 bits |
Word unigram entropy |
~9–11 bits |
~10–12 bits |
Word perplexity |
~500–2000 |
~1000–4000 |
(Exact numbers depend on whether you use the full Multi30k or the fallback sample.)
Take-away: German has higher word-level entropy than English on the same domain because compounding creates a larger effective vocabulary. This explains why EN→DE is generally harder than DE→EN for statistical systems — you need to generate a larger, sparser output distribution.
Next: Chapter 01 implements Weaver’s cryptanalysis window disambiguator — the first concrete proposal for how entropy ideas could drive automatic translation.
References: Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27, 379–423.