Problems
Loading...
1 / 1

Bigram Probabilities (Add-1 Smoothing)

NLP
Hard

Given a tokenized corpus, compute bigram counts and smoothed conditional probabilities with add-1 (Laplace) smoothing.

Add-1 Smoothing Formula:

P(v∣w)=count⁡(w,v)+1∑u∈Vcount⁡(w,u)+∣V∣P(v \mid w) = \frac{\operatorname{count}(w, v) + 1} {\sum_{u \in V} \operatorname{count}(w, u) + |V|}
Loading visualization...

Examples

Input: tokens = ["a", "b", "a"]

Output: counts[("a","b")] = 1, counts[("b","a")] = 1

Vocabulary: {a, b}, probs[("a","a")] ≈ 0.333, probs[("a","b")] ≈ 0.667

Input: tokens = ["i", "love", "ml", "love", "ml"]

Output: counts[("love","ml")] = 2, counts[("ml","love")] = 1

Hint 1

Build vocabulary as set(tokens), then iterate through adjacent pairs to count bigrams.

Hint 2

For each context word w1, compute denominator as sum of all counts plus |V|, then compute probabilities for all w2 in vocab.

Requirements

  • Build vocabulary V from unique tokens in the corpus
  • Count all bigrams (tokens[i], tokens[i+1]) for i=0..len(tokens)-2
  • Use add-1 smoothing over the whole vocabulary for each context word
  • probs[(w1, w2)] must exist for every pair (w1, w2) in V × V
  • Probabilities for a fixed w1 must sum to ≈ 1

Constraints

  • 1 ≤ len(tokens) ≤ 10,000
  • Python only; time limit: 300ms
Try Similar Problems
Perplexity ComputationWord Count DictBag Of WordsTfidf VectorizerBm25
PrevNext