ROUGE

The problem, from first principles

Where BLEU asks "how much of what you wrote is in the reference" (precision), summarization cares more about the reverse: "how much of the reference did you cover" (recall). ROUGE is the family built around that. ROUGE-N counts overlapping n-grams. ROUGE-L uses the longest common subsequence, words that appear in the same order in both texts but not necessarily next to each other, so it rewards getting the structure right without demanding exact phrasing. Both are reported as precision, recall and F1.

From theory to code

Implement rouge_n and rouge_l.

Constraints

• Inputs are token lists. Both functions return a tuple (precision, recall, f1) of floats.
• rouge_n(candidate, reference, n): overlap is the multiset intersection of the n-gram counts. Precision is overlap / candidate n-grams, recall is overlap / reference n-grams. A side with no n-grams makes its ratio 0.0.
• rouge_l(candidate, reference): let L be the length of the longest common subsequence. Precision is L / len(candidate) and recall is L / len(reference), with 0.0 for an empty side.
• F1 is 2PR / (P + R), or 0.0 when P + R == 0.

Hints