Medium Primitives

BLEU-1gram

Compute a single-reference unigram BLEU score: clipped token precision multiplied by a penalty for a candidate shorter than its reference. A unigram is one token. Inputs are already tokenized, so there is no text splitting or normalization to implement.

Your task

Implement bleu_1gram(reference, candidate) using Python lists of token strings. Return a Python float in [0, 1], not a percentage or a tensor. Leave both lists unchanged. Match tokens exactly, including case and punctuation.

If candidate is empty, return 0.0, even when reference is also empty. Otherwise, compute the following two parts.

Clipped precision

Count each distinct candidate token once in this sum:

matched = sum(min(candidate_count[token], reference_count[token])
              for token in distinct_candidate_tokens)
precision = matched / len(candidate)

A token absent from the reference has reference count zero. Repetitions can only match as many copies as the reference contains. Use token counts, not just set membership, and divide by the total number of candidate tokens.

Brevity penalty

Let c be the candidate length and r the reference length:

penalty = 1                         if c >= r
penalty = exp(1 - r / c)             if c < r
score = penalty * precision

Use the natural exponential. There is no smoothing or extra length penalty. A nonempty candidate with an empty reference scores zero because no tokens match.

Example

For reference=["a", "a", "b", "c"] and candidate=["a", "a", "a"], only two of the three candidate tokens match. Precision is 2/3, the brevity penalty is exp(1 - 4/3), and the score is approximately 0.477688.

For equal-length lists with the same token counts, the score is 1 even if word order differs. This unigram exercise cannot detect that difference.

What this score covers

This is a simplified score for one candidate and one reference. It does not combine longer n-grams, multiple references or counts across a corpus. Token overlap alone does not establish correct meaning or fluent language, so treat this exercise as a calculation of a specific metric, not a complete assessment of generated text quality.

Understand the ideas behind this exercise. The Problem tab contains the exact implementation requirements.

Count matching tokens without rewarding repetition

BLEU compares generated text, called the candidate, with reference text. It combines clipped n-gram precision with a penalty for an overly short candidate. An n-gram is a sequence of n tokens. The exercise uses BLEU-1, which considers single tokens only; full BLEU combines several n-gram lengths.

Clipping limits credit for each token to the number of occurrences supported by the reference. For candidate the the cat and reference the cat, only one the and one cat count. There are two credited matches among three candidate tokens, so precision is 2/3.

Penalize candidates that are too short

A candidate containing one common reference word could have perfect precision. The brevity penalty discourages this shortcut. For candidate length c and reference length r, the penalty is 1 when c >= r. For a shorter, nonempty candidate, it is exp(1 - r/c).

A one-token candidate against a two-token reference gets penalty exp(-1), about 0.368. BLEU-1 multiplies clipped unigram precision by this penalty.

Know what the score leaves out

Unigram overlap ignores word order: dog bites person and person bites dog have identical token counts. A high BLEU-1 score therefore does not establish that the meaning is correct.

Follow the task's tokenization, capitalization, and punctuation rules. Define an empty candidate's score explicitly, since the length formula would divide by zero. Corpus BLEU combines counts across examples before calculating the score; it is not generally the average of sentence BLEU scores.

Detecting runtime…