HardNLPnlp-232

BPE Vocabulary Growth

Problem

Simulate greedy BPE for n_merges steps. Each step counts adjacent symbol pairs across all words, picks the most frequent pair with lexicographic tie-breaking, and merges every non-overlapping left-to-right occurrence in every word.

Start from characters, add each merged symbol to the vocabulary, stop early when no pairs remain, and return the final number of distinct symbols.

Hint

Grow a vocabulary set while rewriting the words; a step with no pairs ends the simulation.

Test cases

case 1

in: [[["a","b","a","b","a"]],2]

expected: 4

case 2

in: [[["x","y","z"]],0]

expected: 3

case 3

in: [[["a","a","a"]],5]

expected: 3

case 4

in: [[],3]

expected: 0

case 5

in: [[["a","b"]],-1]

expected: 2

Starter codePython

def bpe_vocab_growth(words, n_merges):
    # Your code here
    pass

5 test cases · run your code against them in the editor