Stretch: BPE, full training loop
The problem, from first principles
[03-bpe-single-merge] implemented exactly ONE merge step: find the most frequent adjacent pair, merge it everywhere. A real BPE tokenizer's vocabulary is built by running that single step REPEATEDLY, typically tens of thousands of times for a production-scale tokenizer, each merge building on top of the results of every merge before it (so a token created by merge #500 can itself become one half of a pair merged in step #501). The full LIST of merges learned, in order, effectively IS the trained tokenizer: to encode brand new text later, you don't re-run the whole frequency-counting process from scratch, you simply replay the exact same sequence of merges, in the exact same order they were originally learned, against the new text's character-level tokens.
This ordering requirement is the subtle but essential detail this question is really about: merge #500 might only make sense to apply AFTER merges #1 through #499 have already been applied (since it might be merging two tokens that themselves only exist because of earlier merges). Applying the learned merges out of order, or in a different order than they were learned, would produce a completely different, likely broken tokenization.
From theory to code
Implement train_bpe(corpus, num_merges), calling [03-bpe-single-merge]'s bpe_single_merge_step (already provided, reused via load_solution) exactly num_merges times in a loop, feeding each step's output corpus into the NEXT step's input, and collecting every merged pair, IN ORDER, into a list. Implement apply_merges(tokens, merges), replaying a previously-learned list of merges, in the SAME order, against a fresh sequence of character-level tokens (for text the tokenizer wasn't trained on).
Constraints
train_bpemust feed each merge step's OUTPUT corpus as the NEXT step's input (this is what lets later merges build on top of earlier ones), not repeatedly re-run merges against the original, unmerged corpus.train_bpe's returnedmergeslist must be in the EXACT order the merges were learned (the orderbpe_single_merge_stepreturned them across the loop's iterations).apply_mergesmust apply the merges in that SAME order, calling[03-bpe-single-merge]'smerge_paironce per learned merge, in sequence.- If
num_mergesexceeds the number of distinct pairs still available to merge,train_bpedoesn't need to handle that edge case gracefully (assumenum_mergesis always achievable for the given corpus).
Hints
Hint 1: train_bpe
merges = [], then for _ in range(num_merges): corpus, merged_pair = bpe_single_merge_step(corpus); merges.append(merged_pair). Reassigning corpus inside the loop, to the PREVIOUS iteration's returned corpus, is what makes each merge build on the last.
Hint 2: apply_merges
for pair in merges: tokens = merge_pair([tokens], pair)[0]. merge_pair expects a CORPUS (a list of sequences), so wrap the single tokens sequence in a one-element list before calling it, and unwrap the result ([0]) afterward.
Hint 3
The loop in apply_merges must iterate merges in the exact order given (a plain for pair in merges:, no sorting or reordering), since later merges in the list were specifically learned to apply AFTER the earlier ones.
Keywords
No results yet
Run your code to check it against the examples, or submit to run every test.