HardNLPnlp-233

BPE Merge Savings

Problem

Measure how many tokens byte-level BPE saves. Encode text as UTF-8 bytes, then apply each merge rule in order, where a rule is a pair [left, right] of current symbol ids and merged symbols receive fresh ids starting at 256.

Return [tokens, savings] where tokens is the number of symbols left and savings is the original byte length minus tokens.

Hint

Rebuild the symbol list once per rule, assigning one new id per rule and reusing it for every match.

Test cases

case 1

in: ["banana",[[98,97]]]

expected: [5,1]

case 2

in: ["banana",[[98,97],[110,97]]]

expected: [3,3]

case 3

in: ["",[]]

expected: [0,0]

case 4

in: ["é",[[195,169]]]

expected: [1,1]

case 5

in: ["abc",[]]

expected: [3,0]

Starter codePython

def bpe_merge_savings(text, merges):
    # Your code here
    pass

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