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, thenprecision P,recall Randf1 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
the cat sat on the mat the cat is on the mat 1
matches 5 precision 0.833 recall 0.833 f1 0.833
the cat sat on the mat the cat is on the mat 2
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}")