The problem
Training byte-level BPE (byte-pair encoding) means running the two functions of the previous exercise in a loop: count the pairs, merge the most frequent one into a new token, repeat. The output is the list of merges, which the next exercise uses to encode and decode text. (The two functions are given in the starter code, so this exercise does not depend on your earlier solution.)
The loop
- Turn
textinto its bytes with UTF-8 (Unicode Transformation Format, 8-bit):list(text.encode("utf-8")), a list of ints from 0 to 255. - Repeat
vocab_size - 256times:- count the adjacent pairs;
- pick the most frequent pair; on ties, the one that occurs first in the current list;
- give it the next id (256 in the first round, then 257, ...) and merge it everywhere;
- record the merge.
- Return the merges as a
dictmapping(a, b) -> new_id, in the order they were learned.
If at some point no pair is left (the whole text became a single token), stop early.
Example.
train_bpe("aaabdaaabac", 259): three merges. "a" is byte 97, "b" 98, "c" 99, "d" 100.
- Bytes:
[97, 97, 97, 98, 100, 97, 97, 97, 98, 97, 99]. The most frequent pair is(97, 97), 4 times. It becomes 256:[256, 97, 98, 100, 256, 97, 98, 97, 99].- Counts now:
(256, 97)2 times,(97, 98)2 times, every other pair once. A tie:(256, 97)occurs first in the list, so it wins and becomes 257:[257, 98, 100, 257, 98, 97, 99].(257, 98)occurs 2 times, more than any other pair. It becomes 258:[258, 100, 258, 97, 99].The result is
{(97, 97): 256, (256, 97): 257, (257, 98): 258}.
What to implement
train_bpe(text, vocab_size): return the merges dict described above.
Requirements
vocab_sizeis the size of the final vocabulary: 256 byte values plus one id per merge. Sovocab_size = 256means no merges at all.- Use the tie rule exactly as in the example.
Hint
max(counts, key=counts.get) returns the pair with the largest count, and among equal counts the first one in the dict's order. get_pair_counts lists pairs by first occurrence, so that one line already applies the tie rule.