Compute the pair counts that drive the first step of byte-pair encoding.
What to build
A program that counts neighbouring character pairs over a word-frequency list.
Requirements
- Each word is split into its characters followed by the end-of-word marker
_. Every neighbouring pair in a word adds that word's count. - Print each pair as
a b count, highest count first, ties in alphabetical order of the pair (compare the left symbols, then the right;_sorts before letters). - Finally print
best:followed by the two symbols of the first pair joined together.
Input
Line 1: n. Then n lines word count.
Output
One line per distinct pair, then the best line.
Constraints
n ≤ 1,000; words have at most 30 lowercase letters.
Example
Input:
2
low 5
lower 2
Output:
l o 7
o w 7
w _ 5
e r 2
r _ 2
w e 2
best: lo
Why it works
A pair inside a word that occurs c times in the corpus occurs c times in the text, so weighting by word counts gives the true frequency of the pair, and the most frequent pair is the one BPE merges first.
Examples
2 low 5 lower 2
l o 7 o w 7 w _ 5 e r 2 r _ 2 w e 2 best: lo
1 aaa 1
a a 2 a _ 1 best: aa
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The symbols of a word are `list(word) + ["_"]`, and its pairs are `zip(symbols, symbols[1:])`.
Hint 2
Add the word's count, not 1, for each pair; sort with `key=lambda kv: (-kv[1], kv[0])`.
Solution
Show one correct solution (try it yourself first)
counts = {}
for _ in range(int(input())):
word, c = input().split()
symbols = list(word) + ["_"]
for pair in zip(symbols, symbols[1:]):
counts[pair] = counts.get(pair, 0) + int(c)
ranked = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))
for (a, b), c in ranked:
print(a, b, c)
print("best:", ranked[0][0][0] + ranked[0][0][1])