BLEU combines n-gram precisions and punishes outputs that are too short.
What to build
A program that computes a two-gram BLEU score of a candidate against a reference.
Requirements
- Lower-case both texts and split them into words.
- P1 and P2 are the clipped unigram and bigram precisions of the candidate. If the candidate has no bigrams, P2 is 0.
- The brevity penalty BP is 1 when the candidate has at least as many words as the reference, otherwise exp(1 − r/c) for c candidate words and r reference words.
- BLEU is BP times the square root of P1 × P2.
- Print
p1 X,p2 X,bp Xandbleu X, each to three decimal places.
Input
Line 1: the candidate. Line 2: the reference.
Output
Four lines.
Constraints
Each text has 1 to 50 words.
Example
Input:
the cat sat on the mat
the cat sat on the mat
Output:
p1 1.000
p2 1.000
bp 1.000
bleu 1.000
Why it works
The precisions reward matching words and word pairs, the geometric mean makes a zero in either one pull the score to zero, and the brevity penalty stops very short outputs from winning on precision alone.
Examples
the cat sat on the mat the cat sat on the mat
p1 1.000 p2 1.000 bp 1.000 bleu 1.000
the cat sat the cat sat on the mat
p1 1.000 p2 1.000 bp 0.368 bleu 0.368
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Clipped precision for n = 1 and n = 2: count each reference n-gram and use it up as the candidate matches it.
Hint 2
The score is the brevity penalty times the square root of P1 times P2; use `round(x, 12)` on results of `math.sqrt` and `math.exp`.
Hint 3
A candidate with one word has no bigrams, so P2 is 0 and the score is 0.
Solution
Show one correct solution (try it yourself first)
import math
cand = input().lower().split()
ref = input().lower().split()
def precision(n):
cg = [" ".join(cand[i : i + n]) for i in range(len(cand) - n + 1)]
rg = [" ".join(ref[i : i + n]) for i in range(len(ref) - n + 1)]
left = {}
for g in rg:
left[g] = left.get(g, 0) + 1
m = 0
for g in cg:
if left.get(g, 0) > 0:
left[g] -= 1
m += 1
return m / len(cg) if cg else 0.0
p1, p2 = precision(1), precision(2)
c, r = len(cand), len(ref)
bp = 1.0 if c >= r else round(math.exp(1 - r / c), 12)
bleu = bp * round(math.sqrt(p1 * p2), 12)
print(f"p1 {p1:.3f}")
print(f"p2 {p2:.3f}")
print(f"bp {bp:.3f}")
print(f"bleu {bleu:.3f}")