A BLEU-style score with a brevity penalty

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 X and bleu 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

Example 1 · Input
the cat sat on the mat
the cat sat on the mat
Expected output
p1 1.000
p2 1.000
bp 1.000
bleu 1.000
Example 2 · Input
the cat sat
the cat sat on the mat
Expected output
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}")

Lesson: Evaluating generative models →