HardNLPnlp-021

BPE Encode with Merges

Problem

Encode a word with a learned BPE merge list. Start by splitting the word into individual characters, then apply each merge pair in the given priority order.

For one merge, scan the current symbols left to right and replace every non-overlapping occurrence of the pair with the concatenated symbol. Return the final list of symbols.

Hint

Apply merges in rank order, each time rebuilding the symbol list.

Test cases

case 1

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

expected: ["ab","c"]

case 2

in: ["abab",[["a","b"],["ab","ab"]]]

expected: ["abab"]

case 3

in: ["hello",[["l","l"],["e","ll"],["h","ell"],["hell","o"]]]

expected: ["hello"]

case 4

in: ["abcd",[]]

expected: ["a","b","c","d"]

case 5

in: ["aab",[["a","a"],["aa","b"]]]

expected: ["aab"]

Starter codePython

def bpe_encode(word, merges):
    # Your code here
    pass

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