NLP: Count adjacent symbol pairs

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

Example 1 · Input
2
low 5
lower 2
Expected output
l o 7
o w 7
w _ 5
e r 2
r _ 2
w e 2
best: lo
Example 2 · Input
1
aaa 1
Expected output
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])

Lesson: Byte-pair encoding tokenization →