20 · Example-Based MT — Nagao (1984)#
Dependencies: stdlib only Runtime: < 1 min CPU
“Translation is done not by abstract rules but by analogy with examples of good translation.” — Makoto Nagao, 1984
Why this chapter matters#
Makoto Nagao’s 1984 paper “A Framework of a Mechanical Translation between Japanese and English by Analogy Principle” introduced a radical idea: throw away the grammar-writing, collect examples of good translations instead. When you see a new sentence, find the most similar example, and adapt its translation.
This is the direct intellectual ancestor of:
Translation memories (every professional CAT tool today)
Retrieval-augmented MT (the 2020s trend of combining retrieval with neural models)
Phrase-based SMT (the retrieval step → the phrase table)
The key insight Nagao called the analogy principle: humans translate by finding similar past sentences and substituting the new parts. We never derive everything from first principles.
What we build#
An example database loaded from Multi30k (or a 20-sentence fallback)
Three similarity measures: Jaccard, LCS ratio, edit distance
A retrieval function that returns the top-k closest examples
Fragment recombination — Nagao’s actual contribution
A full EBMT pipeline and comparison across k and measure choices
The time-machine cell on 20 held-out sentences
# This chapter is **stdlib only** — nothing to install.
# It runs on any Python 3.8+ with no pip dependencies.
import os
import math
import collections
import itertools
import time
from typing import List, Tuple, Optional
1 · The Example Database#
EBMT needs a bilingual example store. We load up to 5 000 sentence pairs from Multi30k when the data directory is present; otherwise we fall back to 20 built-in sentences so the chapter runs with zero network access.
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ßem 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 ."""
MAX_EXAMPLES = 5000
def load_corpus(data_dir: str = "../../data/multi30k") -> Tuple[List[str], List[str]]:
"""Load bilingual corpus; fall back to built-in sentences if data absent."""
en_path = os.path.join(data_dir, "train.en")
de_path = os.path.join(data_dir, "train.de")
if os.path.isfile(en_path) and os.path.isfile(de_path):
with open(en_path, encoding="utf-8") as f:
en_lines = [l.rstrip("\n") for l in f if l.strip()]
with open(de_path, encoding="utf-8") as f:
de_lines = [l.rstrip("\n") for l in f if l.strip()]
n = min(len(en_lines), len(de_lines), MAX_EXAMPLES)
print(f"Loaded {n} sentence pairs from Multi30k.")
return en_lines[:n], de_lines[:n]
else:
en_lines = [l for l in FALLBACK_EN.strip().splitlines() if l.strip()]
de_lines = [l for l in FALLBACK_DE.strip().splitlines() if l.strip()]
print(f"Multi30k not found — using built-in {len(en_lines)}-sentence fallback.")
return en_lines, de_lines
DB_EN, DB_DE = load_corpus()
print(f"Example database: {len(DB_EN)} sentence pairs")
print(f" EN[0]: {DB_EN[0]}")
print(f" DE[0]: {DB_DE[0]}")
Tokenisation#
We use a simple whitespace tokeniser (Multi30k sentences are already pre-tokenised with spaces around punctuation). We lowercase for matching but preserve the original form for output.
def tokenise(sentence: str) -> List[str]:
"""Lowercase whitespace tokenisation."""
return sentence.lower().split()
def detokenise(tokens: List[str]) -> str:
"""Join tokens; naive but fine for this demo."""
return " ".join(tokens)
# Pre-tokenise the database once
DB_EN_TOK = [tokenise(s) for s in DB_EN]
DB_DE_TOK = [tokenise(s) for s in DB_DE]
print("Token counts (first 5 EN sentences):")
for i in range(min(5, len(DB_EN_TOK))):
print(f" {len(DB_EN_TOK[i]):3d} tokens: {DB_EN[i][:60]}")
2 · Similarity Measures#
Nagao’s original proposal used sub-tree similarity in a parse tree, which requires a full parser. We implement three increasingly sophisticated surface-form measures that capture the same intuition without a parser.
a) Jaccard similarity (word overlap)#
Fast and language-agnostic. Ignores word order but captures shared vocabulary well.
def jaccard(s1_tokens: List[str], s2_tokens: List[str]) -> float:
"""Set-based Jaccard similarity between two token lists."""
s1, s2 = set(s1_tokens), set(s2_tokens)
union = s1 | s2
if not union:
return 0.0
return len(s1 & s2) / len(union)
# Quick demo
a = tokenise("A man is walking his dog in the park .")
b = tokenise("A man is riding a bicycle in the park .")
print(f"Jaccard({repr(' '.join(a))[:40]}, ...) = {jaccard(a, b):.3f}")
b) Longest Common Subsequence (LCS) ratio#
LCS captures order-preserving similarity. Two sentences that share many words in the same order are more structurally similar than two with the same bag of words in random order.
def lcs_length(s1: List[str], s2: List[str]) -> int:
"""Standard dynamic-programming LCS on token lists."""
m, n = len(s1), len(s2)
# Use two rolling rows to save memory
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev, curr = curr, [0] * (n + 1)
return prev[n]
def lcs_ratio(s1: List[str], s2: List[str]) -> float:
"""LCS length normalised by the longer sequence."""
denom = max(len(s1), len(s2))
if denom == 0:
return 0.0
return lcs_length(s1, s2) / denom
# Demo
print(f"LCS ratio = {lcs_ratio(a, b):.3f}")
print(f" (shared subsequence length: {lcs_length(a, b)})")
c) Normalised edit distance (Levenshtein)#
Edit distance counts the minimum token-level insertions, deletions and substitutions to transform one sentence into the other. We normalise to [0, 1] and flip so that 1 = identical.
def edit_distance(s1: List[str], s2: List[str]) -> int:
"""Token-level Levenshtein distance."""
m, n = len(s1), len(s2)
prev = list(range(n + 1))
curr = [0] * (n + 1)
for i in range(1, m + 1):
curr[0] = i
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = 1 + min(prev[j], # deletion
curr[j - 1], # insertion
prev[j - 1]) # substitution
prev, curr = curr, [0] * (n + 1)
return prev[n]
def edit_sim(s1: List[str], s2: List[str]) -> float:
"""Normalised edit similarity (1 = identical, 0 = maximally different)."""
denom = max(len(s1), len(s2))
if denom == 0:
return 1.0
return 1.0 - edit_distance(s1, s2) / denom
# Demo
print(f"Edit sim = {edit_sim(a, b):.3f}")
print(f" (edit distance: {edit_distance(a, b)} token ops)")
# Compare all three measures
print("\n── Comparison of the three measures ──")
pairs = [
("A man is walking his dog .", "A man is walking his cat ."),
("A man is walking his dog .", "A dog is walking a man ."),
("A man is walking his dog .", "Two children are playing football ."),
]
for s1, s2 in pairs:
t1, t2 = tokenise(s1), tokenise(s2)
print(f" {s1!r}")
print(f" {s2!r}")
print(f" Jaccard={jaccard(t1,t2):.3f} LCS={lcs_ratio(t1,t2):.3f} Edit={edit_sim(t1,t2):.3f}")
print()
3 · Retrieval#
Given an input sentence, scan the database and return the top-k most similar
examples. We support all three measures via a measure parameter.
MEASURES = {
"jaccard": jaccard,
"lcs": lcs_ratio,
"edit": edit_sim,
}
def retrieve_k(
input_sent: str,
db_en: List[str],
db_de: List[str],
k: int = 5,
measure: str = "jaccard",
) -> List[Tuple[float, str, str]]:
"""Return top-k (similarity, source_example, target_example) triples."""
sim_fn = MEASURES[measure]
input_tok = tokenise(input_sent)
scores = []
for src, tgt in zip(db_en, db_de):
src_tok = tokenise(src)
s = sim_fn(input_tok, src_tok)
scores.append((s, src, tgt))
scores.sort(key=lambda x: -x[0])
return scores[:k]
# Demo retrieval
query = "A man in a blue shirt is walking a dog ."
print(f"Query: {query!r}\n")
for measure in ["jaccard", "lcs", "edit"]:
print(f"── Top-3 by {measure} ──")
results = retrieve_k(query, DB_EN, DB_DE, k=3, measure=measure)
for rank, (sim, src, tgt) in enumerate(results, 1):
print(f" {rank}. [{sim:.3f}] {src}")
print(f" → {tgt}")
print()
4 · Fragment Recombination#
This is Nagao’s core contribution. Once we find a close example, we don’t simply return its translation verbatim. Instead:
Identify the anchor — tokens shared between the input and the example source.
Identify the gap — tokens in the input that differ from the example.
Map the anchor to the corresponding target tokens using LCS alignment.
Fill the gap by looking up each word in a bilingual dictionary.
Assemble anchor + gap translations in input order.
We need a small EN→DE dictionary for step 4. We include ~120 common Multi30k words so the chapter works with zero network access.
# Built-in EN→DE dictionary (~120 high-frequency Multi30k words)
BUILTIN_EN_DE: dict = {
# Articles / determiners
"a": "ein", "an": "ein", "the": "der", "some": "einige", "several": "mehrere",
"two": "zwei", "three": "drei", "four": "vier", "five": "fünf",
"one": "ein", "many": "viele", "few": "wenige",
# Pronouns / connectives
"and": "und", "or": "oder", "is": "ist", "are": "sind", "in": "in",
"on": "auf", "at": "an", "of": "von", "with": "mit", "by": "durch",
"near": "in der Nähe von", "through": "durch", "into": "in",
"between": "zwischen", "against": "gegen", "around": "um",
# Verbs
"walking": "geht", "running": "rennt", "playing": "spielt",
"sitting": "sitzt", "standing": "steht", "reading": "liest",
"riding": "fährt", "jumping": "springt", "climbing": "klettert",
"eating": "isst", "drinking": "trinkt", "talking": "spricht",
"holding": "hält", "carrying": "trägt", "watching": "beobachtet",
"taking": "nimmt", "feeding": "füttert", "chasing": "jagt",
"dancing": "tanzt", "sleeping": "schläft", "painting": "malt",
"kicking": "tritt", "sailing": "segelt", "repairing": "repariert",
"preparing": "bereitet", "waiting": "wartet", "swimming": "schwimmt",
"photographing": "fotografiert", "throwing": "wirft", "catching": "fängt",
# Nouns – people
"man": "Mann", "woman": "Frau", "boy": "Junge", "girl": "Mädchen",
"child": "Kind", "children": "Kinder", "people": "Menschen",
"person": "Person", "men": "Männer", "women": "Frauen", "couple": "Paar",
"group": "Gruppe", "tourist": "Tourist", "tourists": "Touristen",
"musician": "Musiker", "chef": "Koch", "worker": "Arbeiter",
"workers": "Arbeiter", "firefighter": "Feuerwehrmann",
"firefighters": "Feuerwehrleute", "cyclist": "Radfahrer",
# Nouns – animals
"dog": "Hund", "cat": "Katze", "dogs": "Hunde", "cats": "Katzen",
"duck": "Ente", "ducks": "Enten", "bird": "Vogel", "horse": "Pferd",
# Nouns – places / objects
"park": "Park", "field": "Feld", "street": "Straße", "road": "Straße",
"bench": "Bank", "fountain": "Brunnen", "pond": "Teich", "lake": "See",
"beach": "Strand", "stairs": "Treppe", "wall": "Wand", "fence": "Zaun",
"window": "Fenster", "windowsill": "Fensterbrett", "cafe": "Café",
"kitchen": "Küche", "ladder": "Leiter", "boat": "Boot",
"bus": "Bus", "stop": "Haltestelle",
# Adjectives
"red": "rot", "blue": "blau", "green": "grün", "white": "weiß",
"black": "schwarz", "yellow": "gelb", "orange": "orange",
"brown": "braun", "gray": "grau", "young": "jung", "old": "alt",
"small": "klein", "tall": "groß", "warm": "warm", "calm": "ruhig",
"crowded": "belebt", "empty": "leer", "outdoor": "im Freien",
# Colour compounds (for lookup as single tokens)
"coat": "Mantel", "jacket": "Jacke", "shirt": "Hemd", "dress": "Kleid",
"umbrella": "Regenschirm", "bag": "Tasche", "book": "Buch",
"newspaper": "Zeitung", "ball": "Ball", "frisbee": "Frisbee",
"kite": "Drachen", "football": "Fußball", "photograph": "Foto",
"photographs": "Fotos", "flower": "Blume", "flowers": "Blumen",
"food": "Essen", "groceries": "Einkäufe", "chess": "Schach",
"violin": "Geige", "rain": "Regen", "snow": "Schnee", "grass": "Gras",
"sand": "Sand", "water": "Wasser",
# Punctuation / misc
".": ".", ",": ",", "!": "!", "?": "?",
}
def build_dict(db_en: List[str], db_de: List[str]) -> dict:
"""Augment the built-in dict with word-aligned pairs from the database.
We use a simple 1-1 alignment heuristic: for sentence pairs of equal length,
align word-by-word. This is crude but adds domain coverage fast.
"""
lexicon = dict(BUILTIN_EN_DE)
for src, tgt in zip(db_en, db_de):
src_tok = tokenise(src)
tgt_tok = tokenise(tgt)
if len(src_tok) == len(tgt_tok):
for e, d in zip(src_tok, tgt_tok):
if e not in lexicon:
lexicon[e] = d
return lexicon
EN_DE_DICT = build_dict(DB_EN, DB_DE)
print(f"EN→DE dictionary size: {len(EN_DE_DICT)} entries")
# Show a sample
sample = list(EN_DE_DICT.items())[:10]
print("Sample entries:", sample)
Recombination algorithm#
We find the LCS between the input and the best example source. The LCS gives us an alignment of matched positions. We then:
For matched positions: copy the corresponding German token from the example translation (using the same LCS alignment on the target side).
For unmatched positions (the “gap”): look up the English word in our dictionary.
The result is an assembled German sentence that borrows structure from the example and fills in the new material word-by-word.
def lcs_alignment(s1: List[str], s2: List[str]) -> List[Tuple[int, int]]:
"""Return list of (i, j) index pairs forming the LCS."""
m, n = len(s1), len(s2)
# Build full DP table (small sentences, so fine)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Traceback
alignment = []
i, j = m, n
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
alignment.append((i - 1, j - 1))
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
alignment.reverse()
return alignment
def recombine(
input_tokens: List[str],
example_src: List[str],
example_tgt: List[str],
en_de_dict: dict,
) -> List[str]:
"""Assemble a German translation by analogy.
Strategy
--------
1. Align input ↔ example_src via LCS → matched_src positions.
2. Align example_src ↔ example_tgt via LCS → src_tgt mapping.
3. For each input token:
- If it was matched to example_src position p, and p maps to tgt position q,
emit example_tgt[q].
- Otherwise look up en_de_dict (fall back to the English word with '??').
"""
# Step 1: align input to example source
in_src_align = lcs_alignment(input_tokens, example_src)
in_to_src = {i: j for i, j in in_src_align} # input_idx → src_idx
# Step 2: align example source to example target
src_tgt_align = lcs_alignment(example_src, example_tgt)
src_to_tgt = {i: j for i, j in src_tgt_align} # src_idx → tgt_idx
# Step 3: for each input position emit German
output = []
used_tgt = set()
for i, tok in enumerate(input_tokens):
if i in in_to_src:
src_idx = in_to_src[i]
if src_idx in src_to_tgt:
tgt_idx = src_to_tgt[src_idx]
output.append(example_tgt[tgt_idx])
used_tgt.add(tgt_idx)
continue
# Gap: use dictionary
translated = en_de_dict.get(tok, f"[{tok}]")
output.append(translated)
return output
# Demo recombination
inp = tokenise("A woman in a red coat is reading a book .")
best_src = tokenise(DB_EN[0])
best_tgt = tokenise(DB_DE[0])
result = recombine(inp, best_src, best_tgt, EN_DE_DICT)
print("Input :", detokenise(inp))
print("Src ex :", detokenise(best_src))
print("Tgt ex :", detokenise(best_tgt))
print("Output :", detokenise(result))
5 · The Full EBMT Pipeline#
We combine retrieval and recombination. For the top-k examples we generate k candidate translations and select the one whose German tokens are most covered by the dictionary (as a simple quality proxy).
def translation_confidence(tokens: List[str], en_de_dict: dict) -> float:
"""Fraction of tokens that are not unknown-marked."""
if not tokens:
return 0.0
known = sum(1 for t in tokens if not t.startswith("["))
return known / len(tokens)
def ebmt_translate(
input_sent: str,
db_en: List[str],
db_de: List[str],
k: int = 3,
measure: str = "jaccard",
en_de_dict: Optional[dict] = None,
) -> Tuple[str, float, str, str]:
"""Translate input_sent using EBMT.
Returns
-------
translation : str
confidence : float (0–1)
best_src : str (closest example source)
best_tgt : str (closest example target)
"""
if en_de_dict is None:
en_de_dict = BUILTIN_EN_DE
results = retrieve_k(input_sent, db_en, db_de, k=k, measure=measure)
input_tok = tokenise(input_sent)
best_translation = None
best_conf = -1.0
best_src_ex = best_tgt_ex = ""
for sim, src_ex, tgt_ex in results:
src_tok = tokenise(src_ex)
tgt_tok = tokenise(tgt_ex)
candidate = recombine(input_tok, src_tok, tgt_tok, en_de_dict)
conf = translation_confidence(candidate, en_de_dict) * (0.5 + 0.5 * sim)
if conf > best_conf:
best_conf = conf
best_translation = candidate
best_src_ex = src_ex
best_tgt_ex = tgt_ex
return (
detokenise(best_translation or []),
best_conf,
best_src_ex,
best_tgt_ex,
)
# Quick end-to-end test
test_input = "A woman in a red coat is reading a book ."
translation, conf, best_src, best_tgt = ebmt_translate(
test_input, DB_EN, DB_DE, k=5, measure="jaccard", en_de_dict=EN_DE_DICT
)
print(f"Input : {test_input}")
print(f"Translation: {translation}")
print(f"Confidence : {conf:.3f}")
print(f"Best match : {best_src}")
print(f" → {best_tgt}")
6 · Analysis#
6a · Effect of k#
More candidates don’t always help. With a small database the closest example may be very similar; using k = 10 introduces noisier examples that can hurt recombination quality.
comparison_sentences = [
"A man is walking his dog in the park .",
"Two children are playing near a fountain .",
"A cyclist is riding through a crowded street .",
]
print(f"{'Input sentence':<45} k=1 k=3 k=5 k=10")
print("-" * 80)
for sent in comparison_sentences:
row = f"{sent[:44]:<45}"
for k in [1, 3, 5, 10]:
t, conf, _, _ = ebmt_translate(sent, DB_EN, DB_DE, k=k,
measure="jaccard", en_de_dict=EN_DE_DICT)
row += f" {conf:.3f}"
print(row)
print("\n(Confidence scores shown; higher = more known tokens × example similarity)")
6b · Jaccard vs LCS vs Edit distance rankings#
The three measures sometimes disagree on which example is most useful. LCS and edit distance are more sensitive to word order — important for German verb placement.
probe = "A dog is jumping to catch a frisbee ."
print(f"Probe: {probe!r}\n")
for measure in ["jaccard", "lcs", "edit"]:
top = retrieve_k(probe, DB_EN, DB_DE, k=3, measure=measure)
print(f"── {measure.upper()} top-3 ──")
for rank, (sim, src, tgt) in enumerate(top, 1):
print(f" {rank}. [{sim:.3f}] {src}")
print(f" → {tgt}")
# Translate using this measure
t, conf, _, _ = ebmt_translate(probe, DB_EN, DB_DE, k=3,
measure=measure, en_de_dict=EN_DE_DICT)
print(f" Translation: {t} (conf={conf:.3f})")
print()
6c · Similarity landscape#
Which database sentence is closest to each test sentence under each measure? We visualise this as a small heatmap using plain text (no matplotlib needed).
def text_heatmap(matrix: List[List[float]], row_labels: List[str],
col_labels: List[str], title: str = "") -> None:
"""Render a float matrix as ASCII art."""
if title:
print(title)
# Column header
col_w = 6
label_w = max(len(r) for r in row_labels)
header = " " * (label_w + 2)
for c in col_labels:
header += f"{c[:col_w]:>{col_w}} "
print(header)
# Rows
bar_chars = " ░▒▓█"
for i, row in enumerate(matrix):
line = f"{row_labels[i]:<{label_w}} "
for v in row:
idx = min(int(v * (len(bar_chars) - 1)), len(bar_chars) - 1)
cell = bar_chars[idx]
line += f"{cell*3} {v:.2f} "
print(line)
print()
probe_sentences = [
"A man is walking his dog .",
"Two children are playing .",
"A dog is running .",
"A woman is reading .",
]
# Use only first 8 DB examples to keep the heatmap readable
n_db = min(8, len(DB_EN))
for measure in ["jaccard", "lcs", "edit"]:
sim_fn = MEASURES[measure]
matrix = []
for p in probe_sentences:
p_tok = tokenise(p)
row = [sim_fn(p_tok, tokenise(DB_EN[j])) for j in range(n_db)]
matrix.append(row)
col_labels = [f"DB{j}" for j in range(n_db)]
row_labels = [p[:28] for p in probe_sentences]
text_heatmap(matrix, row_labels, col_labels, title=f"── {measure.upper()} similarity ──")
7 · Time-Machine Cell#
Every chapter translates the same 20 held-out test sentences so you can compare quality across the entire history of MT. Run this cell in any chapter to see where the technology stood at that historical moment.
Expected quality here: imperfect but pattern-recognising. EBMT gets sentence structure from similar examples and falls back to word-for-word lookup for the gaps. Compare with Georgetown (lookup-only) — EBMT is clearly better at novel combinations.
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("=" * 70)
print("TIME MACHINE — Chapter 20: Example-Based MT (Nagao 1984)")
print(f"Database size: {len(DB_EN)} sentence pairs")
print(f"Measure: jaccard | k=5")
print("=" * 70)
t0 = time.time()
for i, sent in enumerate(TIME_MACHINE_EN, 1):
translation, conf, best_src, _ = ebmt_translate(
sent, DB_EN, DB_DE, k=5, measure="jaccard", en_de_dict=EN_DE_DICT
)
print(f"[{i:2d}] EN: {sent}")
print(f" DE: {translation}")
print(f" (conf={conf:.2f}, matched: {best_src[:55]})")
print()
elapsed = time.time() - t0
print(f"Translated {len(TIME_MACHINE_EN)} sentences in {elapsed:.2f}s")
8 · Error Analysis#
What goes wrong? Three systematic failure modes:
Failure mode |
Example |
Root cause |
|---|---|---|
Unknown words |
|
Word not in dict |
Wrong inflection |
|
No morphology |
Wrong word order |
Verb not moved to end |
No grammar rules |
These failures motivated the move to statistical MT (Part 3), which learns both the lexicon and reordering patterns from data automatically.
Vocabulary coverage#
def vocab_coverage(sentences: List[str], en_de_dict: dict) -> dict:
"""Report what fraction of test vocabulary is in the dictionary."""
total_tokens = 0
covered = 0
unknown_words: collections.Counter = collections.Counter()
for sent in sentences:
for tok in tokenise(sent):
total_tokens += 1
if tok in en_de_dict:
covered += 1
else:
unknown_words[tok] += 1
return {
"total_tokens": total_tokens,
"covered": covered,
"coverage_pct": 100 * covered / total_tokens if total_tokens else 0,
"top_unknown": unknown_words.most_common(10),
}
stats = vocab_coverage(TIME_MACHINE_EN, EN_DE_DICT)
print(f"Vocabulary coverage on time-machine sentences:")
print(f" Tokens : {stats['total_tokens']}")
print(f" Covered: {stats['covered']} ({stats['coverage_pct']:.1f}%)")
print(f" Top unknown words: {[w for w,_ in stats['top_unknown']]}")
Micro-BLEU sanity check#
We compute a toy BLEU score against the fallback reference translations to give a rough numeric anchor. (Chapter 70 will implement BLEU properly and compare all chapters on the same footing.)
def ngrams(tokens: List[str], n: int) -> collections.Counter:
return collections.Counter(
tuple(tokens[i:i+n]) for i in range(len(tokens) - n + 1)
)
def micro_bleu(hypotheses: List[str], references: List[str], max_n: int = 4) -> float:
"""Corpus-level BLEU (no brevity penalty for simplicity)."""
clip_counts = collections.Counter()
total_counts = collections.Counter()
hyp_len = ref_len = 0
for hyp, ref in zip(hypotheses, references):
h_tok = tokenise(hyp)
r_tok = tokenise(ref)
hyp_len += len(h_tok)
ref_len += len(r_tok)
for n in range(1, max_n + 1):
h_ng = ngrams(h_tok, n)
r_ng = ngrams(r_tok, n)
for ng in h_ng:
clip_counts[n] += min(h_ng[ng], r_ng.get(ng, 0))
total_counts[n] += h_ng[ng]
log_bleu = 0.0
for n in range(1, max_n + 1):
if total_counts[n] == 0:
return 0.0
p = clip_counts[n] / total_counts[n]
log_bleu += math.log(p + 1e-10) / max_n
bp = min(1.0, math.exp(1 - ref_len / (hyp_len + 1e-10)))
return bp * math.exp(log_bleu)
# Only meaningful with the fallback corpus where we know source = reference
# Use the fallback reference translations (first 20 sentences)
hyps = []
refs = DB_DE[:20]
for sent in DB_EN[:20]:
t, _, _, _ = ebmt_translate(sent, DB_EN, DB_DE, k=5,
measure="jaccard", en_de_dict=EN_DE_DICT)
hyps.append(t)
bleu = micro_bleu(hyps, refs)
print(f"Micro-BLEU on {len(hyps)} sentences: {bleu:.4f}")
print("(Leave-one-out would be fairer; this is an optimistic upper bound)")
print("Compare: Georgetown lookup ≈ 0.10–0.20, human ≈ 1.00")
9 · Historical Context & Impact#
Why 1984?#
By the early 1980s, rule-based MT had hit a wall. The ALPAC report (1966) had devastated funding. Nagao, working on Japanese–English MT at Kyoto University, made a pragmatic observation: most text is not fully novel. Technical documents re-use the same constructions constantly. Why not exploit that?
The original proposal#
Nagao’s paper described a 3-step process:
Segmentation — parse both source and example into sub-sentential fragments using a structural analyser.
Matching — find the closest fragment in a large bilingual example base.
Recombination — combine the translated fragments into a target sentence.
Our implementation simplifies step 1 (no parser) and step 3 (LCS instead of constituent alignment), but the spirit is identical.
Descendants#
Year |
System |
Connection |
|---|---|---|
1992 |
EBMT systems proliferate (Sato & Nagao, Cranfield) |
Direct |
1995 |
Translation memories (Trados) go commercial |
Direct |
1993 |
Brown et al. phrase-based models |
Inspired by |
2003 |
Phrase extraction in Moses |
“Phrases as examples” |
2022 |
Retrieval-augmented NMT (kNN-MT) |
Same retrieval idea, neural similarity |
What we lost and regained#
Statistical MT (Part 3) replaced explicit retrieval with implicit example-based knowledge baked into phrase tables and language models. But the 2020s saw kNN-MT (Khandelwal et al. 2021) and retrieval-augmented LLMs rediscover that explicit example retrieval on top of neural models can outperform either alone — Nagao’s insight, 40 years later.
Summary#
Concept |
Implementation |
|---|---|
Example database |
Bilingual sentence pairs from Multi30k (or 20-sentence fallback) |
Similarity |
Jaccard, LCS ratio, normalised edit distance |
Retrieval |
Top-k scan with any similarity measure |
Recombination |
LCS alignment → copy matched target tokens + dict for gaps |
Pipeline |
Retrieve k → generate k candidates → pick highest confidence |
Key take-away: EBMT shows that linguistic competence isn’t the only path to translation. A large enough store of examples, plus a good similarity measure, can produce useful translations with zero explicit grammar rules. The insight is still alive in modern retrieval-augmented MT.
Next: Part 3 — Statistical MT. We’ll learn translation probabilities from data using the IBM models (1990), replacing hand-crafted dictionaries with learned alignments over millions of sentence pairs.