MediumNLPnlp-020

BPE Merge Step

Problem

Perform one BPE merge step over a list of words, where each word is a list of symbols. Count every adjacent symbol pair across all words, pick the most frequent pair, and break ties by lexicographic order.

Merge left-to-right non-overlapping occurrences of that pair in every word. Return a dictionary with key 'pair' holding the two symbols as a list and key 'merged' holding the rewritten words. If there are no pairs, return an empty pair list and the words unchanged.

Hint

Use a tuple as the dictionary key for each symbol pair, then sort keys to break ties.

Test cases

case 1

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

expected: {"pair":["a","b"],"merged":[["ab","ab"],["ab"]]}

case 2

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

expected: {"pair":["a","b"],"merged":[["ab"],["b","a"]]}

case 3

in: [[["l","o","w"],["l","o","w","e","r"]]]

expected: {"pair":["l","o"],"merged":[["lo","w"],["lo","w","e","r"]]}

case 4

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

expected: {"pair":[],"merged":[["a"],["b"]]}

case 5

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

expected: {"pair":["x","y"],"merged":[["xy","xy","x"]]}

Starter codePython

def bpe_merge_step(words):
    # Your code here
    pass

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