N-gram precision and recall

N-gram overlap scores such as BLEU and ROUGE start from the same counts: how many n-grams match.

What to build

A program that prints the clipped n-gram matches of a candidate against a reference, with precision, recall and F1.

Requirements

  • Lower-case both texts and split them into words.
  • Print matches M, then precision P, recall R and f1 F, each to three decimal places.
  • Precision is M over the candidate's n-gram count and recall is M over the reference's n-gram count; F1 is 2PR/(P+R), or 0 when P + R is 0.

Input

Line 1: the candidate. Line 2: the reference. Line 3: n.

Output

Four lines.

Constraints

1 ≤ n ≤ 5. Each text has 1 to 50 words.

Example

Input:

the cat sat on the mat
the cat is on the mat
1

Output:

matches 5
precision 0.833
recall 0.833
f1 0.833

Why it works

Clipping means a reference n-gram can be matched only as often as it occurs, so repeating a phrase cannot raise the score, and precision and recall show the two ways a text can differ from its reference.

Examples

Example 1 · Input
the cat sat on the mat
the cat is on the mat
1
Expected output
matches 5
precision 0.833
recall 0.833
f1 0.833
Example 2 · Input
the cat sat on the mat
the cat is on the mat
2
Expected output
matches 3
precision 0.600
recall 0.600
f1 0.600

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Build the n-grams of both texts as strings of n words joined by spaces.

Hint 2

Count the reference n-grams in a dictionary, and use one up for every candidate n-gram that matches (clipping).

Hint 3

If a text has no n-grams, its share is 0.

Solution

Show one correct solution (try it yourself first)
cand = input().lower().split()
ref = input().lower().split()
n = int(input())


def grams(w):
    return [" ".join(w[i : i + n]) for i in range(len(w) - n + 1)]


cg, rg = grams(cand), grams(ref)
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
p = m / len(cg) if cg else 0.0
r = m / len(rg) if rg else 0.0
f = 2 * p * r / (p + r) if p + r else 0.0
print(f"matches {m}")
print(f"precision {p:.3f}")
print(f"recall {r:.3f}")
print(f"f1 {f:.3f}")

Lesson: Evaluating generative models →