A generative model can also judge data: the model that gives a word the higher probability is the more likely source. Compare two letter models.
What to build
A program that scores words under two smoothed letter models and says which model each word most likely came from.
Requirements
- Each model is learned from its text over the alphabet a to z: P(c) = (count of c + 1) / (number of letters + 26), spaces ignored.
- A word's score is Σ ln P(c) over its letters.
- Print
WORD: A SA, B SB -> Mwith the scores to 3 decimal places and M the model with the higher score (A on a tie).
Input
Line 1: text A. Line 2: text B. Line 3: q. Then q words.
Output
One line per word.
Constraints
Texts and words use lower-case letters (and spaces in texts); 1 ≤ q ≤ 100.
Example
Input:
aaab
bbbc
2
ab
bc
Output:
ab: A -4.723, B -5.416 -> A
bc: A -6.109, B -4.723 -> B
Why it works
The probability of a word under a model is the product of its letters' probabilities, so adding logs compares the two products without them becoming too small to store; adding 1 to every count keeps unseen letters possible.
Examples
aaab bbbc 2 ab bc
ab: A -4.723, B -5.416 -> A bc: A -6.109, B -4.723 -> B
x y 1 z
z: A -3.296, B -3.296 -> A
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each text, count its letters (spaces ignored); a letter's probability is (count + 1) / (letters in the text + 26).
Hint 2
A word's score under a model is the sum of the natural logs of its letters' probabilities.
Hint 3
The higher (less negative) score wins; on a tie, A.
Solution
Show one correct solution (try it yourself first)
import math
texts = [input().replace(" ", ""), input().replace(" ", "")]
q = int(input())
def score(word, text):
return sum(math.log((text.count(c) + 1) / (len(text) + 26)) for c in word)
for _ in range(q):
word = input().strip()
sa, sb = score(word, texts[0]), score(word, texts[1])
print(f"{word}: A {sa:.3f}, B {sb:.3f} -> {'A' if sa >= sb else 'B'}")